Faster twig pattern matching using extended dewey ID

Chung Keung Poon; Leo Yuen

doi:10.1007/11827405_29

Faster twig pattern matching using extended dewey ID

Chung Keung Poon
, Leo Yuen

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

3 Citations (Scopus)

Abstract

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. © Springer-Verlag Berlin Heidelberg 2006.

Original language	English
Title of host publication	Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings
Publisher	Springer Verlag
Pages	297-306
Volume	4080 LNCS
ISBN (Print)	3540378715, 9783540378716
DOIs	https://doi.org/10.1007/11827405_29
Publication status	Published - 2006
Event	17th International Conference on Database and Expert Systems Applications, DEXA 2006 - Krakow, Poland Duration: 4 Sept 2006 → 8 Sept 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4080 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Conference on Database and Expert Systems Applications, DEXA 2006
Place	Poland
City	Krakow
Period	4/09/06 → 8/09/06

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This research was fully supported by a grant from the Research Grants Council of the Hong Kong SAR, China [Project No. 9040906 (RGC Ref. No. CityU 1164/04E)].

RGC Funding Information

RGC-funded

Access Output

10.1007/11827405_29

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Poon, C. K., & Yuen, L. (2006). Faster twig pattern matching using extended dewey ID. In Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings (Vol. 4080 LNCS, pp. 297-306). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4080 LNCS). Springer Verlag. https://doi.org/10.1007/11827405_29

Poon, Chung Keung ; Yuen, Leo. / Faster twig pattern matching using extended dewey ID. Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Vol. 4080 LNCS Springer Verlag, 2006. pp. 297-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{afcf6bcee3f54035a84716b66a28f113,

title = "Faster twig pattern matching using extended dewey ID",

abstract = "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. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",

author = "Poon, \{Chung Keung\} and Leo Yuen",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; 17th International Conference on Database and Expert Systems Applications, DEXA 2006 ; Conference date: 04-09-2006 Through 08-09-2006",

year = "2006",

doi = "10.1007/11827405\_29",

language = "English",

isbn = "3540378715",

volume = "4080 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "297--306",

booktitle = "Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings",

address = "Germany",

}

Poon, CK & Yuen, L 2006, Faster twig pattern matching using extended dewey ID. in Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. vol. 4080 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4080 LNCS, Springer Verlag, pp. 297-306, 17th International Conference on Database and Expert Systems Applications, DEXA 2006, Krakow, Poland, 4/09/06. https://doi.org/10.1007/11827405_29

Faster twig pattern matching using extended dewey ID. / Poon, Chung Keung; Yuen, Leo.
Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Vol. 4080 LNCS Springer Verlag, 2006. p. 297-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4080 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Faster twig pattern matching using extended dewey ID

AU - Poon, Chung Keung

AU - Yuen, Leo

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2006

Y1 - 2006

N2 - 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. © Springer-Verlag Berlin Heidelberg 2006.

AB - 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. © Springer-Verlag Berlin Heidelberg 2006.

UR - https://www.scopus.com/pages/publications/33749420085

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33749420085&origin=recordpage

U2 - 10.1007/11827405_29

DO - 10.1007/11827405_29

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540378715

SN - 9783540378716

VL - 4080 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 297

EP - 306

BT - Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings

PB - Springer Verlag

T2 - 17th International Conference on Database and Expert Systems Applications, DEXA 2006

Y2 - 4 September 2006 through 8 September 2006

ER -

Poon CK, Yuen L. Faster twig pattern matching using extended dewey ID. In Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Vol. 4080 LNCS. Springer Verlag. 2006. p. 297-306. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11827405_29

Faster twig pattern matching using extended dewey ID

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this