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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 620 | Constraint Programming and Database Languages: A Tutorial | 1995 | PODS | 0.00019005954 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 1,488 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011699446 |
| 1,502 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS | 0.00011643406 |
| 1,766 | Indexing Moving Points (Extended Abstract) | 2000 | PODS | 0.000106236 |
| 3,900 | Tight bounds for 2-dimensional indexing schemes | 1998 | PODS | 6.6518011e-05 |
| 5,013 | A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries | 1998 | PODS | 5.7598528e-05 |
| 5,196 | Clustering Techniques for Minimizing External Path Length | 1996 | VLDB | 5.6365164e-05 |
| 5,979 | External Memory Algorithms | 1998 | PODS | 5.2450009e-05 |
| 12,105 | Space-Efficient Range Reporting for Categorical Data | 2012 | PODS | 4.1945683e-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.0032169493 |
| 24 | The R+-Tree: A Dynamic Index For Multi-Dimensional Objects | 1987 | VLDB | 0.00083378538 |
| 76 | Spatial Query Processing in an Object-Oriented Database System | 1986 | SIGMOD | 0.00057303551 |
| 1,352 | H-trees: A Dynamic Associative Search Index for OODB | 1992 | SIGMOD | 0.00012412548 |
| 2,003 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8126082e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,660 | On Searching Compressed String Collections Cache-Obliviously | 2008 | PODS | 4.4722862e-05 |
| 1,195 | Buffering Accesses to Memory-Resident Index Structures | 2003 | VLDB | 0.00013406526 |
| 4,111 | Effective Caching of Shortest Paths for Location-Based Services | 2012 | SIGMOD | 6.4427171e-05 |
| 7,226 | Efficient Search in Very Large Databases | 1988 | VLDB | 4.7953551e-05 |
| 1,502 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS | 0.00011643406 |
| 6,480 | Efficient Search of Multidimensional B-Trees | 1995 | VLDB | 5.0475112e-05 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 2,003 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8126082e-05 |
| 5,196 | Clustering Techniques for Minimizing External Path Length | 1996 | VLDB | 5.6365164e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |