{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:07:17Z","timestamp":1775912837489,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>To index multi-dimensional data, space-filling curves (SFCs) have been used to map the data to one dimension, and then a one-dimensional indexing method such as the B-tree is used to index the mapped data. The existing SFCs all adopt a single mapping scheme for the whole data space. However, a single mapping scheme often does not perform well on all the data space. In this paper, we propose a new type of SFC called piecewise SFCs, which adopts different mapping schemes for different data subspaces. Specifically, we propose a data structure called Bit Merging tree (BMTree), which can generate data subspaces and their SFCs simultaneously and achieve desirable properties of the SFC for the whole data space. Furthermore, we develop a reinforcement learning based solution to build the BMTree, aiming to achieve excellent query performance. Extensive experiments show that our proposed method outperforms existing SFCs in terms of query performance.<\/jats:p>","DOI":"10.14778\/3598581.3598589","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T22:19:06Z","timestamp":1689027546000},"page":"2158-2171","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Towards Designing and Learning Piecewise Space-Filling Curves"],"prefix":"10.14778","volume":"16","author":[{"given":"Jiangneng","family":"Li","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Zheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Gao","family":"Cong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Han Mao","family":"Kiah","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Bin","family":"Cui","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63343-X_48"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.6184"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73746"},{"key":"e_1_2_1_9_1","volume-title":"The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. CoRR abs\/2103.04541","author":"Gu Tu","year":"2021","unstructured":"Tu Gu , Kaiyu Feng , Gao Cong , Cheng Long , Zheng Wang , and Sheng Wang . 2021. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. CoRR abs\/2103.04541 ( 2021 ). arXiv:2103.04541 https:\/\/arxiv.org\/abs\/2103.04541 Tu Gu, Kaiyu Feng, Gao Cong, Cheng Long, Zheng Wang, and Sheng Wang. 2021. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. CoRR abs\/2103.04541 (2021). arXiv:2103.04541 https:\/\/arxiv.org\/abs\/2103.04541"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-021-3578-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98742"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2020.31"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373678"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0166-x"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325886"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342221"},{"key":"e_1_2_1_21_1","unstructured":"Guanli Liu. 2020. Released RSMI Code. https:\/\/github.com\/Liuguanli\/RSMI.  Guanli Liu. 2020. Released RSMI Code. https:\/\/github.com\/Liuguanli\/RSMI."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/502585.502671"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45072-6_7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025196714293"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908985"},{"key":"e_1_2_1_27_1","volume-title":"https:\/\/www.census.gov\/geographies\/mapping-files\/time-series\/geo\/tiger-line-file.html. [Online","author":"Shapefiles Line","year":"2023","unstructured":"n.d. 2022. TIGER\/ Line Shapefiles . https:\/\/www.census.gov\/geographies\/mapping-files\/time-series\/geo\/tiger-line-file.html. [Online ; accessed 3- May - 2023 ]. n.d. 2022. TIGER\/Line Shapefiles. https:\/\/www.census.gov\/geographies\/mapping-files\/time-series\/geo\/tiger-line-file.html. [Online; accessed 3-May-2023]."},{"key":"e_1_2_1_28_1","volume-title":"http:\/\/www.openstreetmap.org\/. [Online","year":"2023","unstructured":"n.d. 2023. OpenStreetMap. http:\/\/www.openstreetmap.org\/. [Online ; accessed 3- May - 2023 ]. n.d. 2023. OpenStreetMap. http:\/\/www.openstreetmap.org\/. [Online; accessed 3-May-2023]."},{"key":"e_1_2_1_29_1","volume-title":"https:\/\/postgis.net\/docs\/using_postgis_dbmanagement.html. [Online","year":"2023","unstructured":"n.d. 2023. PostGis. https:\/\/postgis.net\/docs\/using_postgis_dbmanagement.html. [Online ; accessed 3- May - 2023 ]. n.d. 2023. PostGis. https:\/\/postgis.net\/docs\/using_postgis_dbmanagement.html. [Online; accessed 3-May-2023]."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2011.41"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035934"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16886"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66954"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/588011.588037"},{"key":"e_1_2_1_35_1","volume-title":"4th International Workshop on Applied AI for Database Systems and Applications (AIDB@ VLDB2022)","author":"Pai Sachith Gopalakrishna","year":"2022","unstructured":"Sachith Gopalakrishna Pai , Michael Mathioudakis , and Yanhao Wang . 2022 . Towards an Instance-Optimal Z-Index . In 4th International Workshop on Applied AI for Database Systems and Applications (AIDB@ VLDB2022) . Sachith Gopalakrishna Pai, Michael Mathioudakis, and Yanhao Wang. 2022. Towards an Instance-Optimal Z-Index. In 4th International Workshop on Applied AI for Database Systems and Applications (AIDB@ VLDB2022)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00147-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01199438"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536233"},{"key":"e_1_2_1_41_1","volume-title":"Foundations of multidimensional and metric data structures","author":"Samet Hanan","unstructured":"Hanan Samet . 2006. Foundations of multidimensional and metric data structures . Academic Press . Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press."},{"key":"e_1_2_1_42_1","volume-title":"Proximal Policy Optimization Algorithms. CoRR abs\/1707.06347","author":"Schulman John","year":"2017","unstructured":"John Schulman , Filip Wolski , Prafulla Dhariwal , Alec Radford , and Oleg Klimov . 2017. Proximal Policy Optimization Algorithms. CoRR abs\/1707.06347 ( 2017 ). arXiv:1707.06347 http:\/\/arxiv.org\/abs\/1707.06347 John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal Policy Optimization Algorithms. CoRR abs\/1707.06347 (2017). arXiv:1707.06347 http:\/\/arxiv.org\/abs\/1707.06347"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2004.12.001"},{"key":"e_1_2_1_44_1","unstructured":"Zack Slayton. 2017. Z-Order Indexing for Multifaceted Queries in Amazon DynamoDB. https:\/\/aws.amazon.com\/blogs\/database\/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1\/.  Zack Slayton. 2017. Z-Order Indexing for Multifaceted Queries in Amazon DynamoDB. https:\/\/aws.amazon.com\/blogs\/database\/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1\/."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_1_46_1","volume-title":"Barto","author":"Sutton Richard S.","year":"1998","unstructured":"Richard S. Sutton and Andrew G . Barto . 1998 . Reinforcement learning - an introduction. MIT Press . https:\/\/www.worldcat.org\/oclc\/37293240 Richard S. Sutton and Andrew G. Barto. 1998. Reinforcement learning - an introduction. MIT Press. https:\/\/www.worldcat.org\/oclc\/37293240"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-022-00186-4"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556686"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389770"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0013-2"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-021-1348-2"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2020.3030473"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485456"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3598581.3598589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T22:59:52Z","timestamp":1689807592000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3598581.3598589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":53,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.14778\/3598581.3598589"],"URL":"https:\/\/doi.org\/10.14778\/3598581.3598589","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"2023-07-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}