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
hf25537fa4a62d601
Venue
SIGMOD
Year
2002
Pagerank
0.00014275788
Overall Rank
744 | 95.02%
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
333 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00020712452
456 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017946233
1,027 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00012391703
1,176 Projecting XML Documents 2003 VLDB 0.00011624347
1,793 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.6149082e-05
1,912 ViST: A Dynamic Index Method for Querying XML Data by Tree Structures 2003 SIGMOD 9.3690697e-05
2,058 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.0944201e-05
2,726 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 8.0711806e-05
3,497 Updates for Structure Indexes 2002 VLDB 7.2356454e-05
4,219 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7141046e-05
4,452 Efficient External-Memory Bisimulation on DAGs 2012 SIGMOD 6.5780472e-05
5,247 Indexing Dataspaces 2007 SIGMOD 6.1985096e-05
5,443 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 6.1130037e-05
5,720 BLAS : An Efficient XPath Processing System 2004 SIGMOD 6.0015097e-05
5,985 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.9092174e-05
6,087 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.8741996e-05
6,678 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.6957209e-05
6,968 Indexing Temporal XML Documents 2004 VLDB 5.6158112e-05
7,362 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5281595e-05
7,612 XQuery Optimization 2003 VLDB 5.4677429e-05
7,655 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 5.4578901e-05
8,017 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.390745e-05
8,568 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB 5.2994373e-05
8,586 Materialized View Selection for XQuery Workloads 2012 SIGMOD 5.2939333e-05
9,552 Tree-Pattern Queries on a Lightweight XML Processor 2005 VLDB 5.1497999e-05
9,715 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 5.1236529e-05
9,943 Fast Optimal Twig Joins 2010 VLDB 5.0922518e-05
13,111 XSeq: An Indexing Infrastructure for Tree Pattern Queries 2004 SIGMOD 4.9605343e-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
50 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00042977538
141 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029191386
352 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00020179814
445 A Fast Index for Semistructured Data 2001 VLDB 0.0001815112
Previous Page 1 / 1 Next

Semantically Similar Papers

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