Worst-Case Efficient Range Search Indexing

Summary: Survey of worst-case optimal external-memory orthogonal range indexing: covers B-tree variants for 1D, external priority search trees, range trees (B-tree I/Os but superlinear space) and linear-space kdB-/O-trees. Discusses indexability lower bounds proving optimal query/space trade-offs, extensions to higher dimensions, and R-tree variants for rectangle objects. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1488
Venue: PODS
Year: 2009
Pagerank: 5.093636e-05
Overall Rank: 12,489 | 14.32%
DOI: 10.1145/1559795.1559822

Incoming Non-self Citations Over Time

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

Authors

1. Lars Arge (Aarhus University; Center for Massive Data Algorithmics)

BibTeX Citation

@inproceedings{arge_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Worst-Case Efficient Range Search Indexing}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559822},
        doi = {10.1145/1559795.1559822},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arge, Lars},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997
3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.2750277e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
2	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
3	6,491	Two-dimensional Substring Indexing	2001	PODS
4	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
5	8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD
6	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
7	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
8	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
9	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS