Abstract
The performance of an R-tree mostly depends on how it is built (how to pack tree nodes), which is an NP-hard problem. The existing R-tree building algorithms use either heuristic or greedy strategy to perform node packing and mainly have 2 limitations: (1) They greedily optimize the short-term but not the overall tree costs. (2) They enforce full-packing of each node. These both limit the built tree structure. To address these limitations, we propose ACR-tree, an R-tree building algorithm based on deep reinforcement learning. To optimize the long-term tree costs, we design a tree Markov decision process to model the R-tree construction. To effectively explore the huge searching space of non-full R-tree packing, we utilize the Actor-Critic algorithm and design a deep neural network model to capture spatial data distribution for estimating the long-term tree costs and making node packing decisions. We also propose a bottom-up method to efficiently train the model. Extensive experiments on real-world datasets show that the ACR-tree significantly outperforms existing R-trees.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arge, L., Berg, M.D., Haverkort, H., Yi, K.: The priority R-tree: a practically efficient and worst-case optimal R-tree. ACM Trans. Algorithms (TALG) 4(1), 1–30 (2008)
Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pp. 322–331 (1990)
Beckmann, N., Seeger, B.: A revised R*-tree in comparison with related index structures. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 799–812 (2009)
García R, Y.J., López, M.A., Leutenegger, S.T.: A greedy algorithm for bulk loading R-trees. In: Proceedings of the 6th ACM International Symposium on Advances in geoGraphic Information Systems, pp. 163–164 (1998)
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57 (1984)
Haverkort, H., Walderveen, F.V.: Four-dimensional Hilbert curves for R-trees. J. Exp. Algorithmics (JEA) 16, 3-1 (2008)
Kamel, I., Faloutsos, C.: Hilbert R-tree: an improved R-tree using fractals. Technical report (1993)
Kamel, I., Faloutsos, C.: On packing R-trees. In: Proceedings of the Second International Conference on Information and Knowledge Management, pp. 490–499 (1993)
Konda, V., Tsitsiklis, J.: Actor-critic algorithms. Adv. Neural Inf. Process. Syst. 12 (1999)
Krizhevsky, A., Sutskever, I., Hinton, G.E.: ImageNet classification with deep convolutional neural networks. Adv. Neural. Inf. Process. Syst. 25, 1097–1105 (2012)
LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86(11), 2278–2324 (1998)
Leutenegger, S.T., Lopez, M.A., Edgington, J.: STR: a simple and efficient algorithm for R-tree packing. In: Proceedings 13th International Conference on Data Engineering, pp. 497–506. IEEE (1997)
Li, G., Zhou, X., Li, S., Gao, B.: QTune: a query-aware database tuning system with deep reinforcement learning. Proc. VLDB Endow. 12(12), 2118–2130 (2019)
Qi, J., Tao, Y., Chang, Y., Zhang, R.: Theoretically optimal and empirically efficient R-trees with strong parallelizability. Proc. VLDB Endow. 11(5), 621–634 (2018)
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
Sellis, T., Roussopoulos, N., Faloutsos, C.: The R+-tree: a dynamic index for multi-dimensional objects. Technical report (1987)
Silver, D., et al.: Mastering the game of go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)
Yu, X., Li, G., Chai, C., Tang, N.: Reinforcement learning with tree-LSTM for join order selection. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 1297–1308. IEEE (2020)
Acknowledgement
This paper was supported by National Natural Science Foundation of China (61925205, 62232009), Huawei, TAL education, and Beijing National Research Center for Information Science and Technology.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Huang, S., Wang, Y., Li, G. (2023). ACR-Tree: Constructing R-Trees Using Deep Reinforcement Learning. In: Wang, X., et al. Database Systems for Advanced Applications. DASFAA 2023. Lecture Notes in Computer Science, vol 13943. Springer, Cham. https://doi.org/10.1007/978-3-031-30637-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-30637-2_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30636-5
Online ISBN: 978-3-031-30637-2
eBook Packages: Computer ScienceComputer Science (R0)