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
3344
Venue
SIGMOD
Year
2002
Pagerank
0.00016352717
Overall Rank
817 | 94.32%
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
350 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00026365067
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023598882
993 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00014765816
1,264 Projecting XML Documents 2003 VLDB 0.00012976407
2,069 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.6329563e-05
2,161 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.4002771e-05
2,168 ViST: A Dynamic Index Method for Querying XML Data by Tree Structures 2003 SIGMOD 9.3848723e-05
2,977 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 7.7876083e-05
3,466 Updates for Structure Indexes 2002 VLDB 7.0695018e-05
3,677 Efficient External-Memory Bisimulation on DAGs 2012 SIGMOD 6.8533416e-05
4,587 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.0658154e-05
5,385 Indexing Dataspaces 2007 SIGMOD 5.5381684e-05
5,574 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 5.4268403e-05
5,682 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.372736e-05
5,820 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.3135144e-05
5,889 BLAS : An Efficient XPath Processing System 2004 SIGMOD 5.2873528e-05
6,224 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.1495715e-05
6,872 XQuery Optimization 2003 VLDB 4.8991822e-05
6,954 Indexing Temporal XML Documents 2004 VLDB 4.8864906e-05
7,240 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 4.792172e-05
7,367 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 4.7514687e-05
7,763 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 4.6575679e-05
8,397 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB 4.527474e-05
8,440 Materialized View Selection for XQuery Workloads 2012 SIGMOD 4.5127636e-05
9,178 Tree-Pattern Queries on a Lightweight XML Processor 2005 VLDB 4.3828426e-05
9,310 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 4.3570863e-05
9,594 Fast Optimal Twig Joins 2010 VLDB 4.3197044e-05
12,581 XSeq: An Indexing Infrastructure for Tree Pattern Queries 2004 SIGMOD 4.1945683e-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.00064329285
153 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00040784455
391 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00024564567
415 A Fast Index for Semistructured Data 2001 VLDB 0.00023814619
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,120 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 7.5295938e-05
869 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00015788339
13,802 Efficient XML Path Expression Processing Techniques 2002 VLDB -
5,663 Incremental Maintenance of XML Structural Indexes 2004 SIGMOD 5.3832923e-05
5,820 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.3135144e-05
7,763 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 4.6575679e-05
1,027 Accelerating XPath Location Steps 2002 SIGMOD 0.0001458865
7,302 Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods 2005 VLDB 4.7687064e-05
2,161 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.4002771e-05
415 A Fast Index for Semistructured Data 2001 VLDB 0.00023814619