Fast Matching of Twig Patterns

File Size Format
53080_1.pdf 325Kb Adobe PDF View
Title Fast Matching of Twig Patterns
Author Li, Jiang; Wang, Junhu
Journal Name Lecture Notes in Computer Science
Editor G Goos, J Hartmanis
Year Published 2008
Place of publication Germany
Publisher Springer
Abstract Twig pattern matching plays a crucial role in data processing. Existing twig pattern matching algorithms can be classified into two-phase algorithms and one-phase algorithms. While the two-phase algorithms (e.g., ) suffer from expensive merging cost, the one-phase algorithms (e.g., , , ) either lack efficient filtering of useless elements, or use over-complicated data structures. In this paper, we present two novel one-phase holistic twig matching algorithms, TwigMix and , which combine the efficient selection of useful elements (introduced in ) with the simple lists for storing final solutions (introduced in ). simply introduces the element selection function of into to avoid manipulation of useless elements in the stack and lists. further improves this by introducing some pointers in the lists to completely avoid the use of stacks. Our experiments show significantly and consistently outperforms and (up to several times faster), and is up to two times faster than .
Peer Reviewed Yes
Published Yes
Alternative URI
Copyright Statement Copyright 2008 Springer Berlin / Heidelberg. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at
Volume 5181
Page from 523
Page to 536
ISSN 0302-9743
Date Accessioned 2009-02-09
Language en_US
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Database Management
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice