DBScholar

Back to papers

Path Caching: A Technique for Optimal External Searching (Extended Abstract)

Summary: Path caching: a method to convert internal 2D search structures (segment/interval/priority search trees) into external I/O-efficient indexes achieving optimal query I/O O(log_B n + t/B) for 2-sided searches. Small space overhead O((n/B) log_B log_2 B), supports dynamic updates in amortized O(log_B n), and extends to optimal 3-sided queries with modest extra storage/update cost. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h3f9e8cb0f46c2ff6
Venue
PODS
Year
1994
Pagerank
9.0678883e-05
Overall Rank
2,069 | 86.14%
DOI
10.1145/182591.182595

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ramaswamy_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Path Caching: A Technique for Optimal External Searching (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/182591.182595},
        doi = {10.1145/182591.182595},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ramaswamy, Sridhar and Subramanian, Sairam},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
917 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00013054852
1,514 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010391649
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010326893
1,594 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010103178
1,654 Indexing Moving Points (Extended Abstract) 2000 PODS 9.9565797e-05
4,065 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.8104677e-05
4,862 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS 6.3646378e-05
6,020 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.8934229e-05
6,427 External Memory Algorithms 1998 PODS 5.7713075e-05
10,378 AITTI: Augmented Interval Tree for Temporal Indexing 2027 SIGMOD 4.9605343e-05
12,642 Space-Efficient Range Reporting for Categorical Data 2012 PODS 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0019892478
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
102 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033850505
2,051 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.1080736e-05
2,198 H-trees: A Dynamic Associative Search Index for OODB 1992 SIGMOD 8.8681957e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,138 On Searching Compressed String Collections Cache-Obliviously 2008 PODS
2 1,106 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB
3 3,935 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD
4 7,381 Efficient Search in Very Large Databases 1988 VLDB
5 1,594 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS
6 6,597 Efficient Search of Multidimensional B-Trees 1995 VLDB
7 12,828 Worst-Case Efficient Range Search Indexing 2009 PODS
8 2,051 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS
9 6,020 Clustering Techniques for Minimizing External Path Length 1996 VLDB
10 1,514 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS