# A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments

arXiv: https://arxiv.org/abs/2103.04541 · HTML: https://mlsanity.com/paper/2103.04541/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 52 references that are in the map.
- First posted on arXiv 8 Mar 2021.

## Builds on (most cited first, 11 of 11)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [Qd-tree: Learning Data Layouts for Big Data Analytics](https://mlsanity.com/paper/2004.10898/) (2020)
- [SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning](https://mlsanity.com/paper/1901.05152/) (2019)
- [Neural Packet Classification](https://mlsanity.com/paper/1902.10319/) (2019)
- [The Case for Learned Spatial Indexes](https://mlsanity.com/paper/2008.10349/) (2020)
- [Opportunistic View Materialization with Deep Reinforcement Learning](https://mlsanity.com/paper/1903.01363/) (2019)
- [Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning](https://mlsanity.com/paper/2003.02542/) (2020)

## Built on by (most cited first, 2 of 2)

- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [Learned spatial data partitioning](https://mlsanity.com/paper/2306.04846/) (2023)

## Abstract (arXiv)

Learned indices have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. They require to replace both the indices and query processing algorithms currently deployed by the databases, and such a radical departure is likely to encounter challenges and obstacles. In contrast, we propose a fundamentally different way of using ML techniques to improve on the query performance of the classic R-Tree without the need of changing its structure or query processing algorithms. Specifically, we develop reinforcement learning (RL) based models to decide how to choose a subtree for insertion and how to split a node when building an R-Tree, instead of relying on hand-crafted heuristic rules currently used by R-Tree and its variants. Experiments on real and synthetic datasets with up to more than 100 million spatial objects clearly show that our RL based index outperforms R-Tree and its variants in terms of query processing time.