Efficient XPath tree pattern matching algorithms over XML data stream (コンピュテーション)

スポンサーリンク

概要

• 論文の詳細を見る

• XPath is a language for specifying the selection of element nodes within XML documents. The essential part of XPath is tree-shaped queries, referred to as the XPath trees in this paper. Formally, an XPath tree is an unordered tree whose nodes and edges are, labeled with 'node-tests' and 'navigational axes', respectively. This paper considers the tree matching problem over streaming XML data for subclasses of the XPath trees. First we present a streaming algorithm for the regular XPath trees that runs O (|Q||D|) time using O (|Q| height (D)) space, where |Q|, |D|, and height(D) are the query size, the data size, and the height of the data tree, respectively. Then, we extend the algorithm to larger subclasses with/without keeping the computational complexities.

• 社団法人電子情報通信学会の論文
• 2008-06-09

著者

• Takeda Masayuki

  Depertment Of Informatics Kyushu University

• HAGIO Kazuhito

  Depertment of Informatics, Kyushu University

• OHGAMI Takashi

  Depertment of Informatics, Kyushu University

• Ohgami Takashi

  Depertment Of Informatics Kyushu University

• Hagio Kazuhito

  Depertment Of Informatics Kyushu University

関連論文

• Efficient XPath tree pattern matching algorithms over XML data stream (コンピュテーション)

スポンサーリンク