{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:30Z","timestamp":1750219830853,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            Recently, the value of data has been widely recognized, which highlights the significance of data-centric computing in diversified application scenarios. In many cases, the data are multidimensional, and the management of multidimensional data often confronts greater challenges in supporting efficient data access operations and guaranteeing the space utilization. On the other hand, while many existing index data structures have been proposed for multidimensional data management, however, their designs are not fully optimized for modern nonvolatile memories, in particular the byte-addressable persistent memories. As a result, they might undergo serious access performance degradation or fail to guarantee space utilization. This observation motivates the redesigning of index data structures for multidimensional point data on modern persistent memories, such as the phase-change memory. In this work, we present the\n            <jats:italic>WARM-tree<\/jats:italic>\n            , a\n            <jats:underline>m<\/jats:underline>\n            ultidimensional\n            <jats:underline>t<\/jats:underline>\n            ree for\n            <jats:underline>r<\/jats:underline>\n            educing the\n            <jats:underline>w<\/jats:underline>\n            rite\n            <jats:underline>a<\/jats:underline>\n            mplification effect, for multidimensional point data. In our evaluation studies, as compared to the bucket PR quadtree and R*-tree, the WARM-tree can provide any worst-case space utilization guarantees in the form of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{m-1}{m}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (\n            <jats:italic>m<\/jats:italic>\n            \u2208 \u2124^+) and effectively reduces the write traffic of key insertions by up to 48.10% and 85.86%, respectively, at the price of degraded average space utilization and prolonged latency of query operations. This suggests that the WARM-tree is a potential multidimensional index structure for insert-intensive workloads.\n          <\/jats:p>","DOI":"10.1145\/3608033","type":"journal-article","created":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T13:33:18Z","timestamp":1694266398000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["WARM-tree: Making Quadtrees Write-efficient and Space-economic on Persistent Memories"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8503-1185","authenticated-orcid":false,"given":"Shin-Ting","family":"Wu","sequence":"first","affiliation":[{"name":"National Tsing Hua University, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2579-4305","authenticated-orcid":false,"given":"Liang-Chi","family":"Chen","sequence":"additional","affiliation":[{"name":"National Cheng Kung University, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1076-2271","authenticated-orcid":false,"given":"Po-Chun","family":"Huang","sequence":"additional","affiliation":[{"name":"National Taipei University of Technology, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1282-2111","authenticated-orcid":false,"given":"Yuan-Hao","family":"Chang","sequence":"additional","affiliation":[{"name":"Institute of Information Science, Academia Sinica, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3460-8674","authenticated-orcid":false,"given":"Chien-Chung","family":"Ho","sequence":"additional","affiliation":[{"name":"National Cheng Kung University, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8356-2495","authenticated-orcid":false,"given":"Wei-Kuan","family":"Shih","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2023,9,9]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Kaggle: 13 Dimension 10 Million Big Data High Dimension","author":"Agrawal Nitin Vinayak","year":"2021","unstructured":"Nitin Vinayak Agrawal. 2021. Kaggle: 13 Dimension 10 Million Big Data High Dimension. https:\/\/www.kaggle.com\/datasets\/nitinvinayak\/13-dimension-10-million-big-data-high-dimension"},{"key":"e_1_3_2_3_2","first-page":"152","article-title":"Persistent memory: A survey of programming support and implementations","author":"Baldassin Alexandro","year":"2022","unstructured":"Alexandro Baldassin, Jo\u00e3o Barreto, Daniel Castro, and Paolo Romano. 2022. Persistent memory: A survey of programming support and implementations. ACM Computing Survey, Article 152 (2022), 37 pages.","journal-title":"ACM Computing Survey"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98741"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/3034786.3056117","volume-title":"ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Bender Michael A","year":"2017","unstructured":"Michael A Bender, Martin Farach-Colton, Rob Johnson, Simon Mauras, Tyler Mayer, Cynthia A Phillips, and Helen Xu. 2017. Write-optimized skip lists. In ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 69\u201378."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_7_2","unstructured":"Gerth Stolting Brodal and Rolf Fagerberg. 2003. Lower bounds for external memory dictionaries(SODA\u201903). Society for Industrial and Applied Mathematics USA 546\u2013554."},{"key":"e_1_3_2_8_2","first-page":"1","article-title":"Spatial index structures for modern storage devices: A survey","author":"Carniel Anderson Chaves","year":"2023","unstructured":"Anderson Chaves Carniel and Cristina Dutra de Aguiar. 2023. Spatial index structures for modern storage devices: A survey. IEEE Transactions on Knowledge and Data Engineering (2023), 1\u201320.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_9_2","first-page":"17","article-title":"B3-Tree: Byte-addressable binary b-tree for persistent memory","author":"Cha Hokeun","year":"2020","unstructured":"Hokeun Cha, Moohyeon Nam, Kibeom Jin, Jiwon Seo, and Beomseok Nam. 2020. B3-Tree: Byte-addressable binary b-tree for persistent memory. ACM Trans. Storage, Article 17 (jul2020), 27 pages.","journal-title":"ACM Trans. Storage"},{"key":"e_1_3_2_10_2","first-page":"76","volume-title":"WALCOM","author":"Chowdhury NM Mosharaf Kabir","year":"2007","unstructured":"NM Mosharaf Kabir Chowdhury, Md Mostofa Akbar, and Mohammad Kaykobad. 2007. DiskTrie: An efficient data structure using flash memory for mobile devices.. In WALCOM. 76\u201387."},{"key":"e_1_3_2_11_2","volume-title":"Introduction to Algorithms, 4th Edition","author":"Cormen Thomas H","year":"2022","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to Algorithms, 4th Edition. MIT press."},{"key":"e_1_3_2_12_2","first-page":"45","volume-title":"International Asia-Pacific Web Conference","author":"Cui Kai","year":"2010","unstructured":"Kai Cui, Peiquan Jin, and Lihua Yue. 2010. HashTree: A new hybrid index for flash disks. In International Asia-Pacific Web Conference. IEEE, 45\u201351."},{"key":"e_1_3_2_13_2","first-page":"635","volume-title":"International Conference on Distributed Computing Systems (ICDCS)","author":"Debnath Biplob","year":"2011","unstructured":"Biplob Debnath, Sudipta Sengupta, Jin Li, David J Lilja, and David HC Du. 2011. BloomFlash: Bloom filter on flash-based storage. In International Conference on Distributed Computing Systems (ICDCS). IEEE, 635\u2013644."},{"key":"e_1_3_2_14_2","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"e_1_3_2_15_2","volume-title":"SpatialHadoop: A MapReduce Framework for Spatial Data","author":"Eldawy Ahmed","year":"2015","unstructured":"Ahmed Eldawy and Mohamed F. Mokbel. 2015. SpatialHadoop: A MapReduce Framework for Spatial Data. http:\/\/spatialhadoop.cs.umn.edu\/datasets.html"},{"key":"e_1_3_2_16_2","first-page":"296","volume-title":"The Annual Symposium on Computational Geometry (SCG\u201905)","author":"Eppstein David","year":"2005","unstructured":"David Eppstein, Michael T. Goodrich, and Jonathan Z. Sun. 2005. The skip quadtree: A simple data structure for multidimensional data. In The Annual Symposium on Computational Geometry (SCG\u201905). ACM, 296\u2013305."},{"issue":"1","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/s00778-019-00559-8","article-title":"Indexing in flash storage devices: A survey on challenges, current approaches, and future trends","volume":"29","author":"al. Athanasios Fevgas et","year":"2020","unstructured":"Athanasios Fevgas et al.2020. Indexing in flash storage devices: A survey on challenges, current approaches, and future trends. The VLDB Journal 29, 1 (2020), 273\u2013311.","journal-title":"The VLDB Journal"},{"key":"e_1_3_2_18_2","first-page":"1","article-title":"HyR-tree: A spatial index for hybrid flash\/3D XPoint storage","author":"al. Athanasios Fevgas et","year":"2021","unstructured":"Athanasios Fevgas et al.2021. HyR-tree: A spatial index for hybrid flash\/3D XPoint storage. Neural Computing and Applications (2021), 1\u201313.","journal-title":"Neural Computing and Applications"},{"key":"e_1_3_2_19_2","article-title":"Dash: Scalable hashing on persistent memory","volume":"2003","author":"al. Baotong Lu et","year":"2020","unstructured":"Baotong Lu et al.2020. Dash: Scalable hashing on persistent memory. CoRR abs\/2003.07302 (2020). arXiv:2003.07302https:\/\/arxiv.org\/abs\/2003.07302","journal-title":"CoRR"},{"key":"e_1_3_2_20_2","first-page":"447","volume-title":"ACM Symposium on Operating Systems Principles (SOSP\u201919)","author":"al. Baptiste Lepers et","year":"2019","unstructured":"Baptiste Lepers et al.2019. KVell: The design and implementation of a fast persistent key-value store. In ACM Symposium on Operating Systems Principles (SOSP\u201919). Association for Computing Machinery, 447\u2013461."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2022.02.001","article-title":"Domain wall memory: Physics, materials, and devices","volume":"958","author":"al. Durgesh Kumar et","year":"2022","unstructured":"Durgesh Kumar et al.2022. Domain wall memory: Physics, materials, and devices. Physics Reports 958 (2022), 1\u201335.","journal-title":"Physics Reports"},{"key":"e_1_3_2_22_2","first-page":"542","volume-title":"ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u20192023)","author":"al. Mohammadamin Ajdari et","year":"2023","unstructured":"Mohammadamin Ajdari et al.2023. Re-architecting I\/O caches for emerging fast storage devices. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u20192023). ACM, 542\u2013555."},{"key":"e_1_3_2_23_2","first-page":"31","volume-title":"USENIX Conference on File and Storage Technologies (FAST 19)","author":"al. Moohyeon Nam et","year":"2019","unstructured":"Moohyeon Nam et al.2019. Write-optimized dynamic hashing for persistent memory. In USENIX Conference on File and Storage Technologies (FAST 19). 31\u201344."},{"key":"e_1_3_2_24_2","first-page":"1","volume-title":"ACM\/IEEE Design Automation Conference (DAC)","author":"al. Yu-Pei Liang et","year":"2020","unstructured":"Yu-Pei Liang et al.2020. Enabling a B \\(^+\\) -tree-based data management scheme for key-value store over SMR-based SSHD. In ACM\/IEEE Design Automation Conference (DAC). 1\u20136."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2019.04.002"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_3_2_27_2","first-page":"47","volume-title":"ACM International Conference on Management of Data (SIGMOD)","author":"Guttman Antonin","year":"1984","unstructured":"Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In ACM International Conference on Management of Data (SIGMOD). 47\u201357."},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/RT.2006.280218","volume-title":"IEEE Symposium on Interactive Ray Tracing","author":"Hunt Warren","year":"2006","unstructured":"Warren Hunt, William R. Mark, and Gordon Stoll. 2006. Fast kd-tree construction with an adaptive error-bounded heuristic. In IEEE Symposium on Interactive Ray Tracing. 81\u201388."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-014-7157-7"},{"key":"e_1_3_2_30_2","first-page":"1","volume-title":"ACM\/IEEE Design Automation Conference (DAC)","author":"Kim Nam Sung","year":"2019","unstructured":"Nam Sung Kim, Choungki Song, Woo Young Cho, Jian Huang, and Myoungsoo Jung. 2019. LL-PCM: Low-latency phase change memory architecture. In ACM\/IEEE Design Automation Conference (DAC). 1\u20136."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2010.03.004"},{"key":"e_1_3_2_32_2","first-page":"635","volume-title":"IEEE International Conference on Computer and Information Technology","author":"Li Guohui","year":"2010","unstructured":"Guohui Li, Pei Zhao, Sheng Gao, and Jianqiang Du. 2010. F-KDB: An KDB tree implementation over flash memory. In IEEE International Conference on Computer and Information Technology. IEEE, 635\u2013642."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384355"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00555-y"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2442980"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/348.318586"},{"key":"e_1_3_2_37_2","first-page":"323","volume-title":"International Conference on Mobile Data Management: Systems, Services and Middleware","author":"On Sai Tung","year":"2009","unstructured":"Sai Tung On, Haibo Hu, Yu Li, and Jianliang Xu. 2009. Lazy-update B+-tree for flash devices. In International Conference on Mobile Data Management: Systems, Services and Middleware. IEEE, 323\u2013328."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2899463"},{"issue":"4","key":"e_1_3_2_39_2","first-page":"76","article-title":"A survey on PCM lifetime enhancement schemes","volume":"52","author":"Rashidi Saeed","year":"2019","unstructured":"Saeed Rashidi, Majid Jalili, and Hamid Sarbazi-Azad. 2019. A survey on PCM lifetime enhancement schemes. ACM Comput. Surv. 52, 4, Article 76 (aug2019), 38 pages.","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_2_40_2","first-page":"10","volume-title":"ACM International Conference on Management of Data (SIGMOD)","author":"Robinson John T","year":"1981","unstructured":"John T Robinson. 1981. The KDB-tree: A search structure for large multidimensional dynamic indexes. In ACM International Conference on Management of Data (SIGMOD). 10\u201318."},{"key":"e_1_3_2_41_2","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet Hanan","year":"2006","unstructured":"Hanan Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Elsevier."},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4842-4932-1","volume-title":"Programming Persistent Memory: A Comprehensive Guide for Developers (1st ed.)","author":"Scargall Steve","year":"2020","unstructured":"Steve Scargall. 2020. Programming Persistent Memory: A Comprehensive Guide for Developers (1st ed.). Apress, USA."},{"key":"e_1_3_2_43_2","first-page":"30","volume-title":"ACM SIGPLAN International Symposium on Memory Management (ISMM 2020)","author":"al. Shihao Song et","year":"2020","unstructured":"Shihao Song et al.2020. Improving phase change memory performance with data content aware access. In ACM SIGPLAN International Symposium on Memory Management (ISMM 2020). ACM, 30\u201347."},{"issue":"199","key":"e_1_3_2_44_2","first-page":"1","article-title":"Pigeon hole principle","volume":"2","author":"Trybulec Wojciech A","year":"1990","unstructured":"Wojciech A Trybulec. 1990. Pigeon hole principle. Journal of Formalized Mathematics 2, 199 (1990), 1\u20135.","journal-title":"Journal of Formalized Mathematics"},{"key":"e_1_3_2_45_2","first-page":"1","volume-title":"Proceedings of the ACM Turing 50th Celebration Conference-China","author":"Wang Huiying","year":"2017","unstructured":"Huiying Wang and Jianhua Feng. 2017. FlashSkipList: Indexing on flash devices. In Proceedings of the ACM Turing 50th Celebration Conference-China. 1\u201310."},{"key":"e_1_3_2_46_2","first-page":"323","volume-title":"USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Xu Jian","year":"2016","unstructured":"Jian Xu and Steven Swanson. 2016. NOVA: A log-structured file system for hybrid volatile\/non-volatile main memories. In USENIX Conference on File and Storage Technologies (FAST\u201916). 323\u2013338."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3608033","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3608033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:32Z","timestamp":1750178792000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3608033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,9]]},"references-count":45,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3608033"],"URL":"https:\/\/doi.org\/10.1145\/3608033","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2023,9,9]]},"assertion":[{"value":"2023-03-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-13","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}