{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T01:16:21Z","timestamp":1728177381746},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,6]]},"abstract":"\n The recently proposed learned indexes have attracted much attention as they can adapt to the actual data and query distributions to attain better search efficiency. Based on this technique, several existing works build up indexes for multi-dimensional data and achieve improved query performance. A common paradigm of these works is to (i) map multi-dimensional data points to a one-dimensional space using a fixed space-filling curve (SFC) or its variant and (ii) then apply the learned indexing techniques. We notice that the first step typically uses a fixed SFC method, such as row-major order and\n z<\/jats:italic>\n -order. It definitely limits the potential of learned multi-dimensional indexes to adapt variable data distributions via different query workloads.\n <\/jats:p>\n In this paper, we propose a novel idea of learning a space-filling curve that is carefully designed and actively optimized for efficient query processing. We also identify innovative offline and online optimization opportunities common to SFC-based learned indexes and offer optimal and\/or heuristic solutions. Experimental results demonstrate that our proposed method, LMSFC, outperforms state-of-the-art non-learned or learned methods across three commonly used real-world datasets and diverse experimental settings.<\/jats:p>","DOI":"10.14778\/3603581.3603598","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:06:48Z","timestamp":1691521608000},"page":"2605-2617","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["LMSFC: A Novel Multidimensional Index Based on Learned Monotonic Space Filling Curves"],"prefix":"10.14778","volume":"16","author":[{"given":"Jian","family":"Gao","sequence":"first","affiliation":[{"name":"UNSW, Australia"}]},{"given":"Xin","family":"Cao","sequence":"additional","affiliation":[{"name":"UNSW, Australia"}]},{"given":"Xin","family":"Yao","sequence":"additional","affiliation":[{"name":"Huawei Theory Lab, China"}]},{"given":"Gong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huawei Theory Lab, China"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"Laboratory of Materials Informatics, HKUST (Guangzhou), China and HKUST, HKSAR, China"}]}],"member":"320","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Aref","author":"Rakin Haider Ch. Md.","year":"2022","unstructured":"Abdullah-Al-Mamun, Ch. Md. Rakin Haider , Jianguo Wang , and Walid G . Aref . 2022 . The \"AI+R\"-tree: An Instance-optimized R-tree. In MDM. Abdullah-Al-Mamun, Ch. Md. Rakin Haider, Jianguo Wang, and Walid G. Aref. 2022. The \"AI+R\"-tree: An Instance-optimized R-tree. In MDM."},{"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.1145\/361002.361007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2020.44"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_6_1","first-page":"74","article-title":"Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads","volume":"14","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 . VLDB 14 , 2 (2020), 74 -- 86 . http:\/\/www.vldb.org\/pvldb\/vol14\/p74-ding.pdf Jialin Ding, Vikram Nathan, Mohammad Alizadeh, and Tim Kraska. 2020. Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads. VLDB 14, 2 (2020), 74--86. http:\/\/www.vldb.org\/pvldb\/vol14\/p74-ding.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_7_1","unstructured":"Yihe Dong Piotr Indyk Ilya P. Razenshteyn and Tal Wagner. 2020. Learning Space Partitions for Nearest Neighbor Search. In ICLR. OpenReview.net. https:\/\/openreview.net\/forum?id=rkenmREFDr Yihe Dong Piotr Indyk Ilya P. Razenshteyn and Tal Wagner. 2020. Learning Space Partitions for Nearest Neighbor Search. In ICLR. OpenReview.net. https:\/\/openreview.net\/forum?id=rkenmREFDr"},{"key":"e_1_2_1_8_1","first-page":"1162","article-title":"The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds","volume":"13","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina and Giorgio Vinciguerra . 2020 . The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds . VLDB 13 , 8 (2020), 1162 -- 1175 . http:\/\/www.vldb.org\/pvldb\/vol13\/p1162-ferragina.pdf Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. VLDB 13, 8 (2020), 1162--1175. http:\/\/www.vldb.org\/pvldb\/vol13\/p1162-ferragina.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_9_1","volume-title":"Quad trees a data structure for retrieval on composite keys. Acta informatica 4, 1","author":"Finkel Raphael A","year":"1974","unstructured":"Raphael A Finkel and Jon Louis Bentley . 1974. Quad trees a data structure for retrieval on composite keys. Acta informatica 4, 1 ( 1974 ), 1--9. Raphael A Finkel and Jon Louis Bentley. 1974. Quad trees a data structure for retrieval on composite keys. Acta informatica 4, 1 (1974), 1--9."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Alex Galakatos Michael Markovitch Carsten Binnig Rodrigo Fonseca and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In SIGMOD. ACM 1189--1206. Alex Galakatos Michael Markovitch Carsten Binnig Rodrigo Fonseca and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In SIGMOD. ACM 1189--1206.","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_11_1","unstructured":"Tu Gu Kaiyu Feng Gao Cong Cheng Long Zheng Wang and Sheng Wang. [n.d.]. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. ([n. d.]). https:\/\/arxiv.org\/abs\/2103.04541 Tu Gu Kaiyu Feng Gao Cong Cheng Long Zheng Wang and Sheng Wang. [n.d.]. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. ([n. d.]). https:\/\/arxiv.org\/abs\/2103.04541"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_13_1","unstructured":"Ali Hadian Ankit Kumar and Thomas Heinis. 2020. Hands-off Model Integration in Spatial Index Structures (AIDB@VLDB). Ali Hadian Ankit Kumar and Thomas Heinis. 2020. Hands-off Model Integration in Spatial Index Structures (AIDB@VLDB)."},{"key":"e_1_2_1_14_1","volume-title":"\u00dcber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck. Dritter Band: Analysis\u00b7 Grundlagen der Mathematik\u00b7 Physik Verschiedenes: Nebst Einer Lebensgeschichte","author":"Hilbert David","year":"1935","unstructured":"David Hilbert and David Hilbert . 1935. \u00dcber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck. Dritter Band: Analysis\u00b7 Grundlagen der Mathematik\u00b7 Physik Verschiedenes: Nebst Einer Lebensgeschichte ( 1935 ), 1--2. David Hilbert and David Hilbert. 1935. \u00dcber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck. Dritter Band: Analysis\u00b7 Grundlagen der Mathematik\u00b7 Physik Verschiedenes: Nebst Einer Lebensgeschichte (1935), 1--2."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25566-3_40"},{"key":"e_1_2_1_16_1","volume-title":"Hilbert R-tree: An Improved R-tree using Fractals. In VLDB. Morgan Kaufmann, 500--509","author":"Kamel Ibrahim","year":"1994","unstructured":"Ibrahim Kamel and Christos Faloutsos . 1994 . Hilbert R-tree: An Improved R-tree using Fractals. In VLDB. Morgan Kaufmann, 500--509 . http:\/\/www.vldb.org\/conf\/1994\/P500.PDF Ibrahim Kamel and Christos Faloutsos. 1994. Hilbert R-tree: An Improved R-tree using Fractals. In VLDB. Morgan Kaufmann, 500--509. http:\/\/www.vldb.org\/conf\/1994\/P500.PDF"},{"key":"e_1_2_1_17_1","unstructured":"Andreas Kipf Ryan Marcus Alexander van Renen Mihail Stoian Alfons Kemper Tim Kraska and Thomas Neumann. [n.d.]. SOSD: A Benchmark for Learned Indexes. ([n. d.]). http:\/\/arxiv.org\/abs\/1911.13014 Andreas Kipf Ryan Marcus Alexander van Renen Mihail Stoian Alfons Kemper Tim Kraska and Thomas Neumann. [n.d.]. SOSD: A Benchmark for Learned Indexes. ([n. d.]). http:\/\/arxiv.org\/abs\/1911.13014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373678"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.000"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_25_1","unstructured":"Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966). Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318586"},{"key":"e_1_2_1_28_1","first-page":"2341","article-title":"Effectively Learning Spatial Indices","volume":"13","author":"Qi Jianzhong","year":"2020","unstructured":"Jianzhong Qi , Guanli Liu , Christian S. Jensen , and Lars Kulik . 2020 . Effectively Learning Spatial Indices . VLDB 13 , 11 (2020), 2341 -- 2354 . http:\/\/www.vldb.org\/pvldb\/vol13\/p2341-qi.pdf Jianzhong Qi, Guanli Liu, Christian S. Jensen, and Lars Kulik. 2020. Effectively Learning Spatial Indices. VLDB 13, 11 (2020), 2341--2354. http:\/\/www.vldb.org\/pvldb\/vol13\/p2341-qi.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_29_1","unstructured":"Frank Ramsak Volker Markl Robert Fenk Martin Zirkel Klaus Elhardt and Rudolf Bayer. 2000. Integrating the UB-Tree into a Database System Kernel. In VLDB. 263--272. http:\/\/www.vldb.org\/conf\/2000\/P263.pdf Frank Ramsak Volker Markl Robert Fenk Martin Zirkel Klaus Elhardt and Rudolf Bayer. 2000. Integrating the UB-Tree into a Database System Kernel. In VLDB. 263--272. http:\/\/www.vldb.org\/conf\/2000\/P263.pdf"},{"key":"e_1_2_1_30_1","unstructured":"Yanhao Wang Sachith Gopalakrishna Pai Michael Mathioudakis. 2022. Towards an Instance-Optimal Z-Index (AIDB@VLDB). Yanhao Wang Sachith Gopalakrishna Pai Michael Mathioudakis. 2022. Towards an Instance-Optimal Z-Index (AIDB@VLDB)."},{"key":"e_1_2_1_31_1","unstructured":"Timos K. Sellis Nick Roussopoulos and Christos Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In VLDB. Morgan Kaufmann 507--518. http:\/\/www.vldb.org\/conf\/1987\/P507.PDF Timos K. Sellis Nick Roussopoulos and Christos Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In VLDB. Morgan Kaufmann 507--518. http:\/\/www.vldb.org\/conf\/1987\/P507.PDF"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00046"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2204.10028"},{"key":"e_1_2_1_34_1","first-page":"71","article-title":"Multidimensional Range Search in Dynamically Balanced Trees","volume":"2","author":"Tropf Herbert","year":"1981","unstructured":"Herbert Tropf and Helmut Herzog . 1981 . Multidimensional Range Search in Dynamically Balanced Trees . ANGEWANDTE INFO. 2 (1981), 71 -- 77 . Herbert Tropf and Helmut Herzog. 1981. Multidimensional Range Search in Dynamically Balanced Trees. ANGEWANDTE INFO. 2 (1981), 71--77.","journal-title":"ANGEWANDTE INFO."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_36_1","first-page":"1640","article-title":"Are We Ready For Learned Cardinality Estimation","volume":"14","author":"Wang Xiaoying","year":"2021","unstructured":"Xiaoying Wang , Changbo Qu , Weiyuan Wu , Jiannan Wang , and Qingqing Zhou . 2021 . Are We Ready For Learned Cardinality Estimation ? VLDB 14 , 9 (2021), 1640 -- 1654 . http:\/\/www.vldb.org\/pvldb\/vol14\/p1640-wang.pdf Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, and Qingqing Zhou. 2021. Are We Ready For Learned Cardinality Estimation? VLDB 14, 9 (2021), 1640--1654. http:\/\/www.vldb.org\/pvldb\/vol14\/p1640-wang.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_37_1","first-page":"1276","article-title":"Updatable Learned Index with Precise Positions","volume":"14","author":"Wu Jiacheng","year":"2021","unstructured":"Jiacheng Wu , Yong Zhang , Shimin Chen , Yu Chen , Jin Wang , and Chunxiao Xing . 2021 . Updatable Learned Index with Precise Positions . VLDB 14 , 8 (2021), 1276 -- 1288 . http:\/\/www.vldb.org\/pvldb\/vol14\/p1276-wu.pdf Jiacheng Wu, Yong Zhang, Shimin Chen, Yu Chen, Jin Wang, and Chunxiao Xing. 2021. Updatable Learned Index with Precise Positions. VLDB 14, 8 (2021), 1276--1288. http:\/\/www.vldb.org\/pvldb\/vol14\/p1276-wu.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389770"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470892"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3603581.3603598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:08:01Z","timestamp":1691521681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3603581.3603598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":38,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.14778\/3603581.3603598"],"URL":"https:\/\/doi.org\/10.14778\/3603581.3603598","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"2023-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
