[Back]


Talks and Poster Presentations (with Proceedings-Entry):

G. Gottlob, C. Koch, R. Pichler:
"Efficient Algorithms for Processing XPath Queries";
Talk: 28th international Conference on Very Large Data Bases 2002, Hong Kong SAR, China; 2002-08-20 - 2002-08-23; in: "Proceedings of the 28th international Conference on Very Large Data Bases 2002", P. Bernstein, Y. Ioannidis, R. Ramakrishnan, D. Papadias (ed.); Morgan Kaufmann Publishers, (2002), ISBN: 1-55860-869-9; 95 - 106.



English abstract:
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We show that XPath can be processed much more efficiently, and propose main-memory algorithms for this problem with polynomial-time combined query evaluation complexity. Moreover, we present two fragments of XPath for which linear-time query processing algorithms exist.

Created from the Publication Database of the Vienna University of Technology.