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
8.9120272e-05
Overall Rank
2,179 | 85.36%
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 10 of 10 citing papers.

Rank Citing Paper Year Venue Pagerank
914 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00013104061
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010350889
1,559 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010252232
1,589 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010139591
1,646 Indexing Moving Points (Extended Abstract) 2000 PODS 9.9929961e-05
4,060 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.8250997e-05
4,834 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS 6.3883011e-05
6,007 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.9155532e-05
6,413 External Memory Algorithms 1998 PODS 5.7931958e-05
12,593 Space-Efficient Range Reporting for Categorical Data 2012 PODS 4.9793485e-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.001992968
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045337853
101 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033937215
2,047 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.123147e-05
2,191 H-trees: A Dynamic Associative Search Index for OODB 1992 SIGMOD 8.8826647e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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