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: hba254a06c02d3cde
Venue: PODS
Year: 1998
Pagerank: 6.3646378e-05
Overall Rank: 4,862 | 67.42%
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,514	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010391649
4,065	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.8104677e-05
7,774	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.4386896e-05
9,129	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.208561e-05
11,989	Data-Independent Space Partitionings for Summaries	2021	PODS	4.9605343e-05
12,643	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.9605343e-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
210	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024910589
324	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.00020934349
1,143	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00011810737
1,527	On the Analysis of Indexing Schemes	1997	PODS	0.00010326893
2,051	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.1080736e-05
2,069	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.0678883e-05
3,870	OODB Indexing by Class-Division	1995	SIGMOD	6.9416637e-05
4,065	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.8104677e-05
7,744	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	5.4462834e-05

Semantically Similar Papers

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