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)

Paper ID: 1128
Venue: PODS
Year: 1998
Pagerank: 6.5348792e-05
Overall Rank: 4,730 | 67.55%
DOI: 10.1145/275487.275493

Incoming Non-self Citations Over Time

Authors

1. Vasilis Samoladas (University of Texas)
2. Daniel P. Miranker (University of Texas)

BibTeX Citation

@inproceedings{samoladas_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries}},
        url = {https://dl.acm.org/doi/10.1145/275487.275493},
        doi = {10.1145/275487.275493},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Samoladas, Vasilis and Miranker, Daniel P.},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997
3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.9814651e-05
7,612	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.5834218e-05
8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.3483178e-05
11,632	Data-Independent Space Partitionings for Summaries	2021	PODS	5.093636e-05
12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	5.093636e-05

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
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
324	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.00021200835
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.3214272e-05
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
3,790	OODB Indexing by Class-Division	1995	SIGMOD	7.1239529e-05
3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.9814651e-05
7,581	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	5.5923369e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
2	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
3	12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS
4	3,007	Towards Robust Indexing for Ranked Queries	2006	VLDB
5	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
6	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
7	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
8	1,512	On the Analysis of Indexing Schemes	1997	PODS
9	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS