{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:46:05Z","timestamp":1770752765880,"version":"3.50.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE-T2EP20221-0015"],"award-info":[{"award-number":["MOE-T2EP20221-0015"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3626742","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-26","source":"Crossref","is-referenced-by-count":10,"title":["PLATON: Top-down R-tree Packing with Learned Partition Policy"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-3641-1054","authenticated-orcid":false,"given":"Jingyi","family":"Yang","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4430-6373","authenticated-orcid":false,"given":"Gao","family":"Cong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n. d.]. Decimal Degrees. https:\/\/en.wikipedia.org\/wiki\/Decimal_degrees."},{"key":"e_1_2_2_2_1","unstructured":"[n. d.]. libspatialindex 1.9.3. https:\/\/libspatialindex.org\/en\/latest\/index.html."},{"key":"e_1_2_2_3_1","unstructured":"[n. d.]. LISA Implementation. https:\/\/github.com\/pfl-cs\/LISA."},{"key":"e_1_2_2_4_1","unstructured":"[n. d.]. OpenStreetMap. https:\/\/www.openstreetmap.org."},{"key":"e_1_2_2_5_1","unstructured":"[n. d.]. RSMI Implementation. https:\/\/github.com\/Liuguanli\/RSMI."},{"key":"e_1_2_2_6_1","unstructured":"[n. d.]. TIGER\/Line Shapefiles. https:\/\/www.census.gov\/geographies\/mapping-files\/time-series\/geo\/tiger-line-file.html."},{"key":"e_1_2_2_7_1","unstructured":"[n. d.]. Waffle Implementation. https:\/\/gitlab.com\/moinmoti\/waffle."},{"key":"e_1_2_2_8_1","unstructured":"2023. PostGIS. https:\/\/postgis.net\/."},{"key":"e_1_2_2_9_1","unstructured":"2023. PostgreSQL. https:\/\/www.postgresql.org\/."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM55031.2022.00023"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398577"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328920"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559929"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0100987"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_2_2_17_1","volume-title":"VLDB","volume":"94","author":"DeWitt David J","year":"1994","unstructured":"David J DeWitt, Navin Kabra, Jun Luo, Jignesh M Patel, and Jie-Bing Yu. 1994. Client-server paradise. In VLDB, Vol. 94. Citeseer, 558--569."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457270"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_2_20_1","volume-title":"Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. arXiv preprint arXiv:2006.13282","author":"Ding Jialin","year":"2020","unstructured":"Jialin Ding, Vikram Nathan, Mohammad Alizadeh, and Tim Kraska. 2020. Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. arXiv preprint arXiv:2006.13282 (2020)."},{"key":"e_1_2_2_21_1","volume-title":"RW-Tree: A Learned Workload-aware Framework for R-tree Construction. In 2022 IEEE 38th International Conference on Data Engineering. IEEE.","author":"Dong Haowen","year":"2022","unstructured":"Haowen Dong, Chengliang Chai, Yuyu Luo, Jiabin Liu, Jianhua Feng, and Chaoqun Zhan. 2022. RW-Tree: A Learned Workload-aware Framework for R-tree Construction. In 2022 IEEE 38th International Conference on Data Engineering. IEEE."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"e_1_2_2_23_1","unstructured":"R Elmasri Shamkant B Navathe R Elmasri and SB Navathe. 2000. Fundamentals of Database Systems"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the 6th ACM international symposium on Advances in geographic information systems. 163--164","author":"Yv\u00e1n J","year":"1998","unstructured":"Yv\u00e1n J Garc\u00eda R, Mario A L\u00f3pez, and Scott T Leutenegger. 1998. A greedy algorithm for bulk loading R-trees. In Proceedings of the 6th ACM international symposium on Advances in geographic information systems. 163--164."},{"key":"e_1_2_2_26_1","volume-title":"A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments. arXiv preprint arXiv:2103.04541","author":"Gu Tu","year":"2021","unstructured":"Tu Gu, Kaiyu Feng, Gao Cong, Cheng Long, Zheng Wang, and Sheng Wang. 2021. A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments. arXiv preprint arXiv:2103.04541 (2021)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588917"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1993.344078"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2817-1"},{"key":"e_1_2_2_31_1","first-page":"3","article-title":"Four-dimensional Hilbert curves for R-trees","volume":"16","author":"Haverkort Herman","year":"2008","unstructured":"Herman Haverkort and Freek V Walderveen. 2008. Four-dimensional Hilbert curves for R-trees. Journal of Experimental Algorithmics (JEA) 16 (2008), 3--1.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206049.1206056"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_2_35_1","volume-title":"The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures. arXiv preprint arXiv:2008.00297","author":"Kornaropoulos Evgenios M","year":"2020","unstructured":"Evgenios M Kornaropoulos, Silei Ren, and Roberto Tamassia. 2020. The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures. arXiv preprint arXiv:2008.00297 (2020)."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476392"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_38_1","volume-title":"OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree.. In CAISE Short paper proceedings","author":"Lee Taewon","year":"2003","unstructured":"Taewon Lee and Sukho Lee. 2003. OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree.. In CAISE Short paper proceedings, Vol. 74. 69--72."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_2_41_1","volume-title":"Umar Farooq Minhas, and Tianzheng Wang","author":"Lu Baotong","year":"2021","unstructured":"Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang. 2021. APEX: A High-Performance Learned Index on Persistent Memory. arXiv preprint arXiv:2105.00683 (2021)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574253"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the 2nd International Workshop on Applied AI for Database Systems and Applications (AIDB'20)","author":"Pandey Varun","year":"2020","unstructured":"Varun Pandey, Alexander van Renen, Andreas Kipf, Ibrahim Sabek, Jialin Ding, and Alfons Kemper. 2020. The case for learned spatial indexes. In Proceedings of the 2nd International Workshop on Applied AI for Database Systems and Applications (AIDB'20)."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177738"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/318898.318900"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526158"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases (VLDB '87)","author":"Sellis Timos K.","year":"1987","unstructured":"Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R-Tree: A Dynamic Index for Multi-Dimensional Objects. In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB '87). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 507--518."},{"key":"e_1_2_2_52_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389770"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626742","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626742","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T12:59:03Z","timestamp":1755867543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626742"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626742"],"URL":"https:\/\/doi.org\/10.1145\/3626742","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}