| Presentation | 2008-06-16 Efficient XPath Tree Pattern Matching Algorithms over XML Data Stream Kazuhito HAGIO, Takashi OHGAMI, Masayuki TAKEDA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | XML stream / XML filtering / XPath / Tree Matching Algorithms / Streaming Algorithms |
| Paper # | COMP2008-18 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2008/6/9(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Efficient XPath Tree Pattern Matching Algorithms over XML Data Stream |
| Sub Title (in English) | |
| Keyword(1) | XML stream |
| Keyword(2) | XML filtering |
| Keyword(3) | XPath |
| Keyword(4) | Tree Matching Algorithms |
| Keyword(5) | Streaming Algorithms |
| 1st Author's Name | Kazuhito HAGIO |
| 1st Author's Affiliation | Depertment of Informatics, Kyushu University() |
| 2nd Author's Name | Takashi OHGAMI |
| 2nd Author's Affiliation | Depertment of Informatics, Kyushu University |
| 3rd Author's Name | Masayuki TAKEDA |
| 3rd Author's Affiliation | Depertment of Informatics, Kyushu University |
| Date | 2008-06-16 |
| Paper # | COMP2008-18 |
| Volume (vol) | vol.108 |
| Number (no) | 89 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |