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: 1129
Venue: PODS
Year: 1998
Pagerank: 6.9814651e-05
Overall Rank: 3,972 | 72.75%
DOI: 10.1145/275487.275494

Incoming Non-self Citations Over Time

Authors

1. Elias Koutsoupias (University of California Los Angeles)
2. David Scot Taylor (University of California Los Angeles)

BibTeX Citation

@inproceedings{koutsoupias_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Tight bounds for 2-dimensional indexing schemes}},
        url = {https://dl.acm.org/doi/10.1145/275487.275494},
        doi = {10.1145/275487.275494},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koutsoupias, Elias and Taylor, David Scot},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 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
4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.5348792e-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 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.0020210012
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
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
2,774	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	8.1372328e-05
3,790	OODB Indexing by Class-Division	1995	SIGMOD	7.1239529e-05
4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.5348792e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
2	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
3	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
4	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
5	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
6	6,160	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS
7	4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS
8	1,512	On the Analysis of Indexing Schemes	1997	PODS
9	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS