DBScholar

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
3406
Venue
SIGMOD
Year
2002
Pagerank
0.00014642961
Overall Rank
718 | 95.08%
DOI
10.1145/564691.564707

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kaushik_sigmod02,
        title = {{Covering Indexes for Branching Path Queries}},
        author = {Kaushik, Raghav and Bohannon, Philip and Naughton, Jeffrey F and Korth, Henry F},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564707},
        url = {https://dl.acm.org/doi/10.1145/564691.564707},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
326 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00021152829
444 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00018350865
1,008 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00012688008
1,155 Projecting XML Documents 2003 VLDB 0.00011933524
1,744 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.868841e-05
1,849 ViST: A Dynamic Index Method for Querying XML Data by Tree Structures 2003 SIGMOD 9.6191884e-05
2,006 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.3190255e-05
2,658 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 8.287535e-05
3,421 Updates for Structure Indexes 2002 VLDB 7.4273213e-05
4,113 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.8941988e-05
4,360 Efficient External-Memory Bisimulation on DAGs 2012 SIGMOD 6.7443622e-05
5,100 Indexing Dataspaces 2007 SIGMOD 6.3646337e-05
5,298 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 6.2770047e-05
5,580 BLAS : An Efficient XPath Processing System 2004 SIGMOD 6.1625053e-05
5,848 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 6.0675818e-05
5,952 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 6.031089e-05
6,753 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.7836523e-05
6,808 Indexing Temporal XML Documents 2004 VLDB 5.7664516e-05
7,202 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.6755422e-05
7,460 XQuery Optimization 2003 VLDB 5.6119031e-05
7,494 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 5.6043267e-05
7,836 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.5353696e-05
8,416 Materialized View Selection for XQuery Workloads 2012 SIGMOD 5.429311e-05
8,422 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB 5.4278338e-05
9,338 Tree-Pattern Queries on a Lightweight XML Processor 2005 VLDB 5.2874872e-05
9,496 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 5.2611263e-05
9,730 Fast Optimal Twig Joins 2010 VLDB 5.2288699e-05
12,774 XSeq: An Indexing Infrastructure for Tree Pattern Queries 2004 SIGMOD 5.093636e-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
48 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00044033592
137 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029877792
341 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00020704572
430 A Fast Index for Semistructured Data 2001 VLDB 0.00018600166
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,694 Holistic Twig Joins on Indexed XML Documents 2003 VLDB
2 897 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD
3 14,003 Efficient XML Path Expression Processing Techniques 2002 VLDB
4 5,688 Incremental Maintenance of XML Structural Indexes 2004 SIGMOD
5 5,952 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB
6 7,836 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB
7 893 Accelerating XPath Location Steps 2002 SIGMOD
8 7,423 Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods 2005 VLDB
9 2,006 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD
10 430 A Fast Index for Semistructured Data 2001 VLDB