Name
Abstract | ||
|---|---|---|
We address the embedding existence problem (often referred to as the filtering problem) over streaming XML data for Conjunctive XPath (CXP). Ramanan (2009) considered Downward CXP, a fragment of CXP that involves downward navigational axes only, and presented a streaming algorithm which solves the problem in O(vertical bar P parallel to D vertical bar) time using only O(vertical bar P vertical bar height(D)) bits of space, where vertical bar P vertical bar and vertical bar D vertical bar are the sizes of a query P and an XML data D, respectively, and height(D) denotes the tree height of D. Unfortunately, the algorithm is lazy in the sense that it does not necessarily report the answer even after enough information has been gathered from the input XML stream. In this paper, we present an eager streaming algorithm that solves the problem with same time and space complexity. We also show the algorithm can be easily extended to Backward CXP a larger fragment of CXP. |
Year | Venue | Field |
|---|---|---|
2011 | PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2011 | Efficient XML Interchange,Programming language,Streaming XML,XML,Computer science,Filter (signal processing),XPath,XPath 2.0 |
DocType | Citations | PageRank |
Conference | 1 | 0.38 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuhito Hagio | 1 | 1 | 1.06 |
| Takashi Ohgami | 2 | 1 | 0.72 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Masayuki Takeda | 4 | 902 | 79.24 |