Database Paper Browser

Back to papers

Covering Indexes for Branching Path Queries

Summary: Forward-and-backward index as a covering index analogue for branching path queries on XML graphs; shown to be the smallest index that covers all such expressions. Introducing restricted index-definition schemes yields dramatically smaller, practical indexes with stronger performance when queries match the index, validated on relational XML decompositions and native storage. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3345
Venue
SIGMOD
Year
2002
Pagerank
0.00016343476
Overall Rank
812 | 94.36%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
351 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00026351742
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023592024
993 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00014759406
1,261 Projecting XML Documents 2003 VLDB 0.00012985367
2,066 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.64571e-05
2,166 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.3918483e-05
2,174 ViST: A Dynamic Index Method for Querying XML Data by Tree Structures 2003 SIGMOD 9.3762595e-05
2,980 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 7.7800968e-05
3,468 Updates for Structure Indexes 2002 VLDB 7.0634268e-05
3,675 Efficient External-Memory Bisimulation on DAGs 2012 SIGMOD 6.8500291e-05
4,584 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.0599995e-05
5,391 Indexing Dataspaces 2007 SIGMOD 5.5330974e-05
5,580 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 5.4216254e-05
5,695 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.3675705e-05
5,831 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.308804e-05
5,893 BLAS : An Efficient XPath Processing System 2004 SIGMOD 5.2822731e-05
6,221 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.1446262e-05
6,876 XQuery Optimization 2003 VLDB 4.8947451e-05
6,952 Indexing Temporal XML Documents 2004 VLDB 4.8817935e-05
7,236 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 4.7877732e-05
7,362 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 4.7469116e-05
7,763 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 4.6531059e-05
8,374 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB 4.5282277e-05
8,431 Materialized View Selection for XQuery Workloads 2012 SIGMOD 4.5084372e-05
9,182 Tree-Pattern Queries on a Lightweight XML Processor 2005 VLDB 4.3788525e-05
9,315 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 4.352917e-05
9,594 Fast Optimal Twig Joins 2010 VLDB 4.3155661e-05
12,590 XSeq: An Indexing Infrastructure for Tree Pattern Queries 2004 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank Cited Paper Year Venue Pagerank
61 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00064281097
153 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00040759404
392 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00024546229
414 A Fast Index for Semistructured Data 2001 VLDB 0.00023801668
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
13,884 Benchmarking Queries over Trees: Learning the Hard Truth the Hard Way 2000 SIGMOD -
864 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00015781693
13,816 Efficient XML Path Expression Processing Techniques 2002 VLDB -
5,679 Incremental Maintenance of XML Structural Indexes 2004 SIGMOD 5.3760807e-05
5,831 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.308804e-05
7,763 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 4.6531059e-05
1,028 Accelerating XPath Location Steps 2002 SIGMOD 0.00014578947
7,299 Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods 2005 VLDB 4.7641328e-05
2,166 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.3918483e-05
414 A Fast Index for Semistructured Data 2001 VLDB 0.00023801668