From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching

Summary: Introduces Extended Dewey labeling for XML twig matching, deriving full paths from a single label. TJFast, a holistic twig join, uses only leaf labels, enabling wildcards in branches and smaller intermediates than region-encoding approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he391ebc4d79e3d5f
Venue: VLDB
Year: 2005
Pagerank: 6.6230198e-05
Overall Rank: 4,386 | 70.53%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jiaheng Lu (National University of Singapore)
2. Tok Wang Ling (National University of Singapore)
3. Chee-Yong Chan (National University of Singapore)
4. Ting Chen (National University of Singapore)

BibTeX Citation

@article{lu_vldb05,
        title = {{From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching}},
        author = {Lu, Jiaheng and Ling, Tok Wang and Chan, Chee-Yong and Chen, Ting},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {193},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.7712336e-05
7,326	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.5500332e-05
7,777	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4532403e-05
7,924	AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering	2006	VLDB	5.4238547e-05
9,686	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1406509e-05
12,213	Worst Case Optimal Joins on Relational and XML data	2018	SIGMOD	4.9769913e-05
12,795	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027241844
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020241971
374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019698564
734	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014372588
1,902	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3999798e-05
2,637	Optimizing Queries on Files	1994	SIGMOD	8.1840201e-05
2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.0587951e-05
4,201	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.7363634e-05
5,425	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.1332823e-05
5,710	BLAS : An Efficient XPath Processing System	2004	SIGMOD	6.0214073e-05
9,037	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.2317228e-05
13,094	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD
2	12,870	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB
3	1,555	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
4	12,985	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD
5	4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
6	5,425	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
7	4,201	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
8	179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD
9	2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB
10	9,908	Fast Optimal Twig Joins	2010	VLDB