The RLR-tree: a reinforcement learning based R-tree for spatial data
Learned indexes have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. They require to replace both the indexes and query processing algorithms currently deployed by the databases, and such a radical departure is likely to encounter challenges and obsta...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/166210 https://2023.sigmod.org/ |
| _version_ | 1811686233161596928 |
|---|---|
| author | Gu, Tu Feng, Kaiyu Cong, Gao Long, Cheng Wang, Zheng Wang, Sheng |
| author2 | Interdisciplinary Graduate School (IGS) |
| author_facet | Interdisciplinary Graduate School (IGS) Gu, Tu Feng, Kaiyu Cong, Gao Long, Cheng Wang, Zheng Wang, Sheng |
| author_sort | Gu, Tu |
| collection | NTU |
| description | Learned indexes have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. They require to replace both the indexes 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 build a better R-Tree without the need to change the structure or query processing algorithms of traditional R-Tree. 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 and updating an R-Tree, instead of relying on hand-crafted heuristic rules currently used by the R-Tree and its variants. Experiments on real and synthetic datasets with up to more than 100 million spatial objects show that our RL based index outperforms the R-Tree and its variants in terms of query processing time. |
| first_indexed | 2024-10-01T04:57:09Z |
| format | Conference Paper |
| id | ntu-10356/166210 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:57:09Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1662102023-05-08T02:17:54Z The RLR-tree: a reinforcement learning based R-tree for spatial data Gu, Tu Feng, Kaiyu Cong, Gao Long, Cheng Wang, Zheng Wang, Sheng Interdisciplinary Graduate School (IGS) 2023 ACM SIGMOD/PODS Alibaba Group Alibaba-NTU Singapore Joint Research Institute (JRI) Engineering::Computer science and engineering::Data Spatial Data Spatial Query Processing Learned Index Reinforcement Learning Deep Learning Learned indexes have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. They require to replace both the indexes 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 build a better R-Tree without the need to change the structure or query processing algorithms of traditional R-Tree. 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 and updating an R-Tree, instead of relying on hand-crafted heuristic rules currently used by the R-Tree and its variants. Experiments on real and synthetic datasets with up to more than 100 million spatial objects show that our RL based index outperforms the R-Tree and its variants in terms of query processing time. Nanyang Technological University This work was supported by Alibaba Group through Alibaba Innovative Research (AIR) Program and Alibaba-NTU Singapore Joint Research Institute (JRI), Nanyang Technological University, Singapore. 2023-05-08T02:17:19Z 2023-05-08T02:17:19Z 2023 Conference Paper Gu, T., Feng, K., Cong, G., Long, C., Wang, Z. & Wang, S. (2023). The RLR-tree: a reinforcement learning based R-tree for spatial data. 2023 ACM SIGMOD/PODS. https://dx.doi.org/10.1145/3588917 https://hdl.handle.net/10356/166210 10.1145/3588917 https://2023.sigmod.org/ en AN-GC-2018-024 © 2023 The owner/author(s). Publication rights licensed to ACM. All rights reserved. |
| spellingShingle | Engineering::Computer science and engineering::Data Spatial Data Spatial Query Processing Learned Index Reinforcement Learning Deep Learning Gu, Tu Feng, Kaiyu Cong, Gao Long, Cheng Wang, Zheng Wang, Sheng The RLR-tree: a reinforcement learning based R-tree for spatial data |
| title | The RLR-tree: a reinforcement learning based R-tree for spatial data |
| title_full | The RLR-tree: a reinforcement learning based R-tree for spatial data |
| title_fullStr | The RLR-tree: a reinforcement learning based R-tree for spatial data |
| title_full_unstemmed | The RLR-tree: a reinforcement learning based R-tree for spatial data |
| title_short | The RLR-tree: a reinforcement learning based R-tree for spatial data |
| title_sort | rlr tree a reinforcement learning based r tree for spatial data |
| topic | Engineering::Computer science and engineering::Data Spatial Data Spatial Query Processing Learned Index Reinforcement Learning Deep Learning |
| url | https://hdl.handle.net/10356/166210 https://2023.sigmod.org/ |
| work_keys_str_mv | AT gutu therlrtreeareinforcementlearningbasedrtreeforspatialdata AT fengkaiyu therlrtreeareinforcementlearningbasedrtreeforspatialdata AT conggao therlrtreeareinforcementlearningbasedrtreeforspatialdata AT longcheng therlrtreeareinforcementlearningbasedrtreeforspatialdata AT wangzheng therlrtreeareinforcementlearningbasedrtreeforspatialdata AT wangsheng therlrtreeareinforcementlearningbasedrtreeforspatialdata AT gutu rlrtreeareinforcementlearningbasedrtreeforspatialdata AT fengkaiyu rlrtreeareinforcementlearningbasedrtreeforspatialdata AT conggao rlrtreeareinforcementlearningbasedrtreeforspatialdata AT longcheng rlrtreeareinforcementlearningbasedrtreeforspatialdata AT wangzheng rlrtreeareinforcementlearningbasedrtreeforspatialdata AT wangsheng rlrtreeareinforcementlearningbasedrtreeforspatialdata |