Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility

Summary: Shows explicit external-memory lower bounds for 2D orthogonal range reporting with constant redundancy r, characterizing the query-time/storage tradeoff for every fixed r. Introduces "weak indivisibility" (bits may be split across blocks but must be retrievable) and gives nearly-tight matching upper bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1571
Venue: PODS
Year: 2012
Pagerank: 5.093636e-05
Overall Rank: 12,303 | 15.60%
DOI: 10.1145/2213556.2213577

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yufei Tao (Chinese University of Hong Kong; Korea Advanced Institute of Science and Technology)

BibTeX Citation

@inproceedings{tao_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213577},
        doi = {10.1145/2213556.2213577},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Tao, Yufei},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,172	On Top-k Range Reporting in 2D Space	2015	PODS	5.4740049e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
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
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	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
2	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
3	8,172	On Top-k Range Reporting in 2D Space	2015	PODS
4	2,443	Independent Range Sampling	2014	PODS
5	4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS
6	1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
7	6,160	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS
8	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
9	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS