A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries
Summary: General lower-bound theorem for arbitrary indexing schemes in the external-memory model, formalizing tradeoffs between storage redundancy and access overhead. Resolves prior open problem with tight 2D and d-dimensional range-query lower bounds and gives matching constructions. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
| 3,902 | Tight bounds for 2-dimensional indexing schemes | 1998 | PODS | 6.6454492e-05 |
| 7,412 | Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse | 1999 | SIGMOD | 4.7316475e-05 |
| 8,764 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS | 4.4520434e-05 |
| 11,437 | Data-Independent Space Partitionings for Summaries | 2021 | PODS | 4.1905499e-05 |
| 12,114 | Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility | 2012 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 242 | Generalized Search Trees for Database Systems (Extended Abstract) | 1995 | VLDB | 0.00031093647 |
| 368 | An Array-Based Algorithm for Simultaneous Multidimensional Aggregates | 1997 | SIGMOD | 0.00025508459 |
| 1,111 | Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension | 1994 | PODS | 0.0001389881 |
| 1,485 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011698762 |
| 2,010 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8046157e-05 |
| 2,018 | Path Caching: A Technique for Optimal External Searching (Extended Abstract) | 1994 | PODS | 9.7852268e-05 |
| 3,794 | OODB Indexing by Class-Division | 1995 | SIGMOD | 6.7556886e-05 |
| 3,902 | Tight bounds for 2-dimensional indexing schemes | 1998 | PODS | 6.6454492e-05 |
| 7,440 | Blocking for External Graph Searching (Extended Abstract) | 1993 | PODS | 4.7255744e-05 |
Previous
Page 1 / 1
Next