2006 | OriginalPaper | Buchkapitel
Faster Twig Pattern Matching Using Extended Dewey ID
verfasst von : Chung Keung Poon, Leo Yuen
Erschienen in: Database and Expert Systems Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. Recently, Lu
et al.
[7] proposed the
TJFast
algorithm that uses the
extended Dewey
labelling scheme and reported better performance compared with other
state-of-the-art
holistic twig join algorithms, both in terms of number of elements scanned and stored during the computation. In this paper, we designed an enhancement to further exploit the power of the
extended Dewey ID
. This reduces the CPU cost and also favors indexed inputs. Our algorithm can be shown analytically as efficient as
TJFast
in terms of worst case I/O, and experimentally performs significantly better.