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...
Saved in:
Main Authors: | , , , , , |
---|---|
Other Authors: | |
Format: | Conference or Workshop Item |
Language: | English |
Published: |
2023
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/166210 https://2023.sigmod.org/ |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-166210 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.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. |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Computer science and engineering::Data Spatial Data Spatial Query Processing Learned Index Reinforcement Learning Deep Learning |
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 |
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. |
author2 |
Interdisciplinary Graduate School (IGS) |
author_facet |
Interdisciplinary Graduate School (IGS) Gu, Tu Feng, Kaiyu Cong, Gao Long, Cheng Wang, Zheng Wang, Sheng |
format |
Conference or Workshop Item |
author |
Gu, Tu Feng, Kaiyu Cong, Gao Long, Cheng Wang, Zheng Wang, Sheng |
author_sort |
Gu, Tu |
title |
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_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_sort |
rlr-tree: a reinforcement learning based r-tree for spatial data |
publishDate |
2023 |
url |
https://hdl.handle.net/10356/166210 https://2023.sigmod.org/ |
_version_ |
1770565135174205440 |