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: 1129
Venue: PODS
Year: 1998
Pagerank: 5.7598528e-05
Overall Rank: 5,013 | 65.13%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Vasilis Samoladas
2. Daniel P. Miranker

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
7,433	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	4.7314388e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
11,434	Data-Independent Space Partitionings for Summaries	2021	PODS	4.1945683e-05
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-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
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031110894
366	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.0002552977
1,114	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00013901031
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.8126082e-05
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
3,795	OODB Indexing by Class-Division	1995	SIGMOD	6.7604747e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
7,442	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	4.7300735e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.8126082e-05
5,682	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.372736e-05
3,463	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.069675e-05
12,642	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS	4.1945683e-05
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-05
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963