PLATON: top-down R-tree packing with learned partition policy

• Main Authors: Yang, Jingyi, Cong, Gao
• Other Authors: Interdisciplinary Graduate School (IGS)
• Format: Conference or Workshop Item
• Language: English
• Published: 2024
• Subjects: Computer and Information Science; Learned index; Information systems
• Online Access: https://hdl.handle.net/10356/174800; https://dl.acm.org/toc/pacmmod/2023/1/4; https://2023.sigmod.org/
• Institution: Nanyang Technological University

The exponential growth of spatial data poses new challenges to the performance of spatial databases. Spatial indexes like R-tree greatly accelerate the query performance and can be effectively constructed through packing, i.e., loading all data into the index at once. However, existing R-tree packing methods rely on a set of fixed heuristic rules, which may not be suitable for different data distributions and workload patterns. To address the limitations of existing R-tree packing methods, we propose PLATON, a top-down R-tree packing method with learned partition policy that explicitly optimizes the query performance with regard to the given data and workload instance. We develop a learned partition policy based on Monte Carlo Tree Search and carefully make design choices for the MCTS exploration strategy and simulation strategy to improve algorithm convergence. We propose a divide and conquer strategy and two optimization techniques, early termination and level-wise sampling, to drastically reduce the MCTS algorithm’s time complexity and make it a linear-time algorithm. Experiments on both synthetic and real-world datasets demonstrate the superior performance of PLATON over existing R-tree variants and recently proposed learned/workload-aware spatial indexes.