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)
Incoming Non-self Citations Over Time
Authors
- 1. Lu Xing
- 2. Eric Lee
- 3. Tong An
- 4. Bo-Cheng Chu
- 5. Ahmed Mahmood
- 6. Ahmed M. Aly
- 7. Jianguo Wang
- 8. Walid G. Aref
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,902 | Towards Systematic Index Dynamization | 2024 | VLDB | 4.2539423e-05 |
Previous
Page 1 / 1
Next
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.0032118946 |
| 6 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.0016113151 |
| 129 | The X-tree: An Index Structure for High-Dimensional Data | 1996 | VLDB | 0.00044255276 |
| 356 | Hilbert R-tree: An Improved R-tree Using Fractals | 1994 | VLDB | 0.00026091196 |
| 3,259 | A Revised R*-tree in Comparison with Related Index Structures | 2009 | SIGMOD | 7.3101573e-05 |
| 6,172 | javax.XXL: A Prototype for a Library of Query Processing Algorithms | 2000 | SIGMOD | 5.1692113e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,420 | Towards Efficient Main-Memory Use For Optimum Tree Index Update | 2008 | VLDB | 4.1905499e-05 |
| 2,847 | Utilization of B-trees with Inserts, Deletes and Modifies | 1989 | PODS | 8.0287397e-05 |
| 8,471 | Adaptive Index Structures | 2002 | VLDB | 4.4986491e-05 |
| 1,519 | A Model for the Prediction of R-tree Performance | 1996 | PODS | 0.00011535609 |
| 356 | Hilbert R-tree: An Improved R-tree Using Fractals | 1994 | VLDB | 0.00026091196 |
| 6,766 | Workload-Aware Indexing of Continuously Moving Objects | 2009 | VLDB | 4.9280867e-05 |
| 3,653 | The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree | 2004 | SIGMOD | 6.8725114e-05 |
| 9,021 | On Optimal Node Splitting for R-trees | 1998 | VLDB | 4.4049428e-05 |
| 7,046 | Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability | 2018 | VLDB | 4.8471584e-05 |
| 3,259 | A Revised R*-tree in Comparison with Related Index Structures | 2009 | SIGMOD | 7.3101573e-05 |