An Experimental Evaluation and Investigation of Waves of Misery in R-trees

Summary: Empirical study of waves of misery in R-tree variants; insertion spikes cause volatile performance, with Linear/Quadratic more resilient than Hilbert/R*-trees. Proposes RES (Regular Elective Splits) and URS (Unequal Random Splits) to mitigate waves, yielding deterministic leaf fill at throughput cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 13112
Venue: VLDB
Year: 2022
Pagerank: 5.2419252e-05
Overall Rank: 9,657 | 33.75%
DOI: 10.14778/3494124.3494132

Incoming Non-self Citations Over Time

Authors

1. Lu Xing (Purdue University)
2. Eric Lee (Purdue University)
3. Tong An (Purdue University)
4. Bo-Cheng Chu (Purdue University)
5. Ahmed Mahmood (Purdue University)
6. Ahmed M. Aly (Meta)
7. Jianguo Wang (Purdue University)
8. Walid G. Aref (Alexandria University; Purdue University)

BibTeX Citation

@article{xing_vldb22,
        title = {{An Experimental Evaluation and Investigation of Waves of Misery in R-trees}},
        author = {Xing, Lu and Lee, Eric and An, Tong and Chu, Bo-Cheng and Mahmood, Ahmed and Aly, Ahmed M. and Wang, Jianguo and Aref, Walid G.},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {3},
        pages = {478--490},
        doi = {10.14778/3494124.3494132},
        url = {https://doi.org/10.14778/3494124.3494132},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,988	Towards Systematic Index Dynamization	2024	VLDB	5.3384135e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
6,380	javax.XXL: A Prototype for a Library of Query Processing Algorithms	2000	SIGMOD	5.8921224e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,605	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
2	2,738	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS
3	8,689	Adaptive Index Structures	2002	VLDB
4	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
5	329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB
6	6,458	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB
7	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
8	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
9	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
10	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD