The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree

Summary: Introduces the Priority R-tree (PR-tree), the first R-tree variant that guarantees worst-case optimal window-query I/Os: O((N/B)^(1-1/d) + T/B). Establishes asymptotic optimality and demonstrates practical gains over existing R-trees, excelling on extreme data via extensive real and synthetic experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3593
Venue: SIGMOD
Year: 2004
Pagerank: 7.2750277e-05
Overall Rank: 3,593 | 75.36%
DOI: 10.1145/1007568.1007608

Incoming Non-self Citations Over Time

Authors

1. Lars Arge (Duke University)
2. Mark de Berg (Eindhoven University of Technology)
3. Herman J. Haverkort (Utrecht University)
4. Ke Yi (Duke University)

BibTeX Citation

@inproceedings{arge_sigmod04,
        title = {{The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree}},
        author = {Arge, Lars and de Berg, Mark and Haverkort, Herman J. and Yi, Ke},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007608},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007608},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,742	ArrayStore: A Storage Manager for Complex Parallel Array Processing	2011	SIGMOD	9.8748669e-05
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
4,844	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.4826356e-05
6,537	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.8478276e-05
7,632	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.5777517e-05
8,200	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.4677285e-05
12,327	Measuring Two-Event Structural Correlations on Graphs	2012	VLDB	5.093636e-05
12,489	Worst-Case Efficient Range Search Indexing	2009	PODS	5.093636e-05
12,690	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	5.093636e-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
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
726	Client-Server Paradise	1994	VLDB	0.0001460632

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,605	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
2	957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB
3	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
4	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
5	2,341	Parallel R-trees	1992	SIGMOD
6	1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
7	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
8	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
9	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
10	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB