Search Swinburne Research Bank
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/60727
|Download PDF (Accepted manuscript) (Adobe Acrobat PDF, 258 KB)|
- C-tree indexing for holistic twig joins
- Ning, Bo; Liu, Chengfei; Wang, Guoren
- With the growing importance of semi-structure data in information exchange, effort has been put in providing an effective mechanism to match a twig query in an XML database. Bruno et al. have proposed a novel algorithm TwigStack to deal with the twig query pattern by scanning the tag streams only once. In this paper, we propose a new index called C-Tree and two algorithms named NestTwigStack and ADTwigStack to speed up the processing of twig pattern queries by omitting some elements that can be processed without scanning. Using C-Tree, our algorithms can accelerate both the ancestor-descendant and parent-child edges by skipping the elements with their context in documents. We complement our research with experiments on a set of real and synthetic data, which are intended to show the significant superiority of our algorithms over the previous algorithms.
- Publication type
- Conference paper
- Research centre
- Swinburne University of Technology.
- Lecture notes in computer science: proceedings of the Joint International Conference on Advances in Data and Web Management (APWeb/WAIM 2009), Suzhou, China, 02-04 April 2009 / Qing Li, Ling Feng, Jian Pei, Sean X. Wang, Xiaofang Zhou, Qiao-Ming Zhu (eds.), Vol. 5446, pp. 76-87
- Publication year
- FOR Code(s)
- 080404 Markup Languages; 080505 Web Technologies (excl. Web Search); 080604 Database Management
- Algorithms; C-Tree; Streaming schemes; Twig query patterns; TwigStack; XML documents; XML queries
- 0302-9743 (series ISSN)
- Publisher URL
- Copyright © Springer-Verlag Berlin Heidelberg 2009. The accepted manuscript is reproduced in accordance with the copyright policy of the publisher. The definitive version of the publication is available at www.springer.com.
- Full text
- Peer reviewed