Tight bounds for 2-dimensional indexing schemes

Summary: Shows the Fibonacci workload (grid rotated by the golden ratio) forces worst-case access overhead B even with storage redundancy up to c·log n, and extends this lower bound to random point sets under redundancy < c·log log n. Matches this up to constants with a universal 2D indexing scheme achieving O(log n) redundancy and constant access overhead, and connects indexability limits to fractal (Hausdorff) dimension. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1130
Venue: PODS
Year: 1998
Pagerank: 6.6518011e-05
Overall Rank: 3,900 | 72.87%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Elias Koutsoupias
2. David Scot Taylor

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 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
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-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 11 of 11 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
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031110894
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
2,974	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.789769e-05
3,795	OODB Indexing by Class-Division	1995	SIGMOD	6.7604747e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,682	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.372736e-05
6,516	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS	5.0321577e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
1,766	Indexing Moving Points (Extended Abstract)	2000	PODS	0.000106236
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
6,215	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.153674e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963