Lune

VLDB2022顶会

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

Lu Xing, Eric Lee, Tong An, Bo-Cheng Chu, Ahmed Mahmood, Ahmed M. Aly, Jianguo Wang, Walid G. Aref

摘要

Waves of misery is a phenomenon where spikes of many node splits occur over short periods of time in tree indexes. Waves of misery negatively affect the performance of tree indexes in insertion-heavy workloads. Waves of misery have been first observed in the context of the B-tree, where these waves cause unpredictable index performance. In particular, the performance of search and index-update operations deteriorate when a wave of misery takes place, but is more predictable between the waves. This paper investigates the presence or lack of waves of misery in several R-tree variants, and studies the extent of which these waves impact the performance of each variant. Interestingly, although having poorer query performance, the Linear and Quadratic R-trees are found to be more resilient to waves of misery than both the Hilbert and R*-trees. This paper presents several techniques to reduce the impact in performance of the waves of misery for the Hilbert and R*-trees. One way to eliminate waves of misery is to force node splits to take place at regular times before nodes become full to achieve deterministic performance. The other way is that upon splitting a node, do not split it evenly but rather at different node utilization factors. This allows leaf nodes not to fill at the same pace. We study the impact of two new techniques to mitigate waves of misery after the tree index has been constructed, namely Regular Elective Splits (RES, for short) and Unequal Random Splits (URS, for short). Our experimental investigation highlights the trade-offs in performance of the introduced techniques and the pros and cons of each technique.

问 Lune

几分钟读透这篇 Paper,不用再花一下午。

Lune 能读完全文,也能读引用它的顶会 Paper,讲清它的结论、证据和局限,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。

已有 2 篇顶会 Paper 引用了它。别等审稿人问起,先弄清它们发现了什么。

可以从这些问题问起

Lune 可以查阅

全文 · 引用它的顶会 Paper · 相关的 Paper

获取答案

免费开始,无需绑卡

脉络

它引用的引用它的从左到右按年份排列,引用越多,位置越高。

引用它的顶会 Paper2

  1. Towards Systematic Index DynamizationDouglas B. Rumbaugh, Dong Xie, Zhuoyue ZhaoVLDB 2024 · 6 次引用
  2. Updating an Adaptive Spatial IndexFatemeh Zardbani, Konstantinos Lampropoulos, Nikos Mamoulis, Panagiotis KarrasICDE 2025

相关 Paper

  1. Adaptive Indexing of Objects with Spatial ExtentFatemeh Zardbani, Nikos Mamoulis, Stratos Idreos, Panagiotis KarrasVLDB 2023 · 15 次引用
  2. Hybrid DRAM-NVM R-Trees with Consistency GuaranteeKaiqi Zhang, Chengyou Shen, Siyuan Zhang, Shengfei Shi 等ICDE 2025 · 2 次引用
  3. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial DataTu Gu, Kaiyu Feng, Gao Cong, Cheng Long 等SIGMOD 2023 · 62 次引用
  4. PLATON: Top-down R-tree Packing with Learned Partition PolicyJingyi Yang, Gao CongSIGMOD 2024 · 12 次引用
  5. Toward a Better Understanding and Evaluation of Tree Structures on Flash SSDsDiego Didona, Nikolas Ioannou, Radu Stoica, Kornilios KourtisVLDB 2021 · 16 次引用
黄昏的海面,两侧是细线勾勒的悬崖