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
1012
Venue
PODS
Year
1994
Pagerank
9.1133971e-05
Overall Rank
2,135 | 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
889 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00013398105
1,512 On the Analysis of Indexing Schemes 1997 PODS 0.00010536001
1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010482997
1,561 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010361147
1,611 Indexing Moving Points (Extended Abstract) 2000 PODS 0.00010218339
3,972 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.9814651e-05
4,730 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS 6.5348792e-05
5,888 Clustering Techniques for Minimizing External Path Length 1996 VLDB 6.0498293e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-05
12,302 Space-Efficient Range Reporting for Categorical Data 2012 PODS 5.093636e-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.0020210012
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
96 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00034590762
2,003 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.3214272e-05
2,146 H-trees: A Dynamic Associative Search Index for OODB 1992 SIGMOD 9.0842711e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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