{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:51Z","timestamp":1750309371663,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T00:00:00Z","timestamp":1736553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Academia Sinica","award":["AS-IA-111-M01"],"award-info":[{"award-number":["AS-IA-111-M01"]}]},{"name":"National Science and Technology Council","award":["111-2221-E-001-013-MY3, 111-2923-E-002-014-MY3, 112-2222-E-002-009-MY3, 112-2223-E-001-001, and 113-2927-I-001-502"],"award-info":[{"award-number":["111-2221-E-001-013-MY3, 111-2923-E-002-014-MY3, 112-2222-E-002-009-MY3, 112-2223-E-001-001, and 113-2927-I-001-502"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            With the proliferation of sensors and the emergence of novel applications, IoT data has grown exponentially in recent years. Given this trend, efficient data management is crucial for a system to easily access vast amounts of information. For decades, B\n            <jats:sup>+<\/jats:sup>\n            -tree-based indexing schemes have been widely adopted for providing effective search in IoT systems. However, in systems with pre-distributed sensors, B\n            <jats:sup>+<\/jats:sup>\n            -tree-based indexes fail to optimally utilize the known IoT data distribution, leading to significant write overhead and energy consumption. Furthermore, as non-volatile memory (NVM) technology emerges as the alternative storage medium, the inherent write asymmetry of NVM leads to instability issues in IoT systems, especially for write-intensive applications. In this research, by considering the write overheads of tree-based indexing schemes and key-range distribution assumption, we rethink the design of the tree-based indexing schemes and propose an adaptive pre-built tree (APB-tree) indexing scheme to reduce the write overhead in serving insertion and deletion of keys in the NVM-based IoT system. The APB-tree profiles the hot region of the key distribution from the known key range to pre-allocate the index structure that alleviates online index management costs and runtime index overhead. Meanwhile, the APB-tree maintains the scalability of a tree-based index structure to accommodate the large amount of new data brought by the additional nodes to the IoT system. Extensive experiments demonstrate that our solution achieves significant performance improvements in write operations while maintaining effective energy consumption in the NVM-based IoT system. We compare the energy and time required for basic key operations such as Put(), Get(), and Delete() in APB-trees and B\n            <jats:sup>+<\/jats:sup>\n            -tree-based indexing schemes. Under workloads with varying ratios of these operations, the proposed design effectively reduces execution time by 47% to 72% and energy consumption by 11% to 72% compared to B\n            <jats:sup>+<\/jats:sup>\n            -tree-based indexing schemes.\n          <\/jats:p>","DOI":"10.1145\/3677179","type":"journal-article","created":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T11:09:12Z","timestamp":1721992152000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["APB-tree: An Adaptive Pre-built Tree Indexing Scheme for NVM-based IoT Systems"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5090-7354","authenticated-orcid":false,"given":"Shih-Wen","family":"Hsu","sequence":"first","affiliation":[{"name":"Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2126-6380","authenticated-orcid":false,"given":"Yen-Ting","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Engineering Science and Ocean Engineering, National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-3566","authenticated-orcid":false,"given":"Kam-Yiu","family":"Lam","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8356-2495","authenticated-orcid":false,"given":"Wei-Kuan","family":"Shih","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3222-1708","authenticated-orcid":false,"given":"Han-Chieh","family":"Chao","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, National Dong Hwa University, Hualien, Taiwan, Department of Artificial Intelligence, Takang University, New Taipei, Taiwan, and Institute of Computer Science and Innovation, UCSI University, Kuala Lumpur, Malaysia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,1,11]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054780"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.3390\/app10030999"},{"issue":"19","key":"e_1_3_1_4_2","doi-asserted-by":"crossref","first-page":"193002","DOI":"10.1088\/1361-6463\/ab71aa","article-title":"Phase change memory for automotive grade embedded NVM applications","volume":"53","author":"Cappelletti Paolo","year":"2020","unstructured":"Paolo Cappelletti, Roberto Annunziata, Franck Arnaud, Fabio Disegni, Alfonso Maurelli, and Paola Zuliani. 2020. Phase change memory for automotive grade embedded NVM applications. J. Phys. D: Appl. Phys. 53, 19 (2020), 193002.","journal-title":"J. Phys. D: Appl. Phys."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sse.2016.07.006"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2094091.2094104"},{"volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR)","key":"e_1_3_1_7_2","unstructured":"Shimin Chen, Phillip B. Gibbons, and Suman Nath. 2011. Rethinking database algorithms for phase change memory. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR). 21--31."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394885.3431511"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2627369.2627630"},{"issue":"9","key":"e_1_3_1_11_2","first-page":"1461","article-title":"Adapting B+-Tree for emerging nonvolatile memory-based main memory","volume":"35","author":"Chi Ping","year":"2015","unstructured":"Ping Chi, Wang-Chien Lee, and Yuan Xie. 2015. Adapting B+-Tree for emerging nonvolatile memory-based main memory. IEEE Trans. Parallel Distrib. Syst. 35, 9 (2015), 1461\u20131474.","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"e_1_3_1_12_2","first-page":"109","volume-title":"Proceedings of the 21st Asia and South Pacific Design Automation Conference (ASP-DAC\u201916)","author":"Chi Ping","year":"2016","unstructured":"Ping Chi, Shuangchen Li, Yuanqing Cheng, Yu Lu, Seung H. Kang, and Yuan Xie. 2016. Architecture design with STT-RAM: Opportunities and challenges. In Proceedings of the 21st Asia and South Pacific Design Automation Conference (ASP-DAC\u201916). IEEE, 109\u2013114."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2022.05.012"},{"key":"e_1_3_1_14_2","first-page":"969","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","year":"2020","unstructured":"Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David Lomet, and Tim Kraska. 2020. ALEX: An updatable adaptive learned index. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 969\u2013984."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/JETCAS.2016.2547704"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3154525"},{"key":"e_1_3_1_17_2","first-page":"143","volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201919)","author":"Hankin Alexander","year":"2019","unstructured":"Alexander Hankin, Tomer Shapira, Karthik Sangaiah, Michael Lui, and Mark Hempstead. 2019. Evaluation of non-volatile memory based last level cache given modern use case behavior. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201919). IEEE, 143\u2013154."},{"key":"e_1_3_1_18_2","first-page":"1","volume-title":"Proceedings of the IEEE 51st European Solid-State Device Research Conference (ESSDERC\u201921)","author":"Hartmann Jo\u00ebl","year":"2021","unstructured":"Jo\u00ebl Hartmann, Paolo Cappelletti, Nitin Chawla, Franck Arnaud, and Andreia Cathelin. 2021. Artificial intelligence: Why moving it to the edge? In Proceedings of the IEEE 51st European Solid-State Device Research Conference (ESSDERC\u201921). IEEE, 1\u20136."},{"key":"e_1_3_1_19_2","volume-title":"Proceedings of the IEEE International Electron Devices Meeting (IEDM\u201920)","author":"Jew Thomas","year":"2020","unstructured":"Thomas Jew. 2020. MRAM in microcontroller and microprocessor product applications. In Proceedings of the IEEE International Electron Devices Meeting (IEDM\u201920). IEEE, 11\u20131."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10617-013-9123-4"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"Saeed Kargar and Faisal Nawab. 2023. Challenges and future directions for energy latency and lifetime improvements in NVMs. Distributed and Parallel Databases 41 3 (2023) 163--189.","DOI":"10.1007\/s10619-022-07421-x"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3041872"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-021-03377-2"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"issue":"21","key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"213002","DOI":"10.1088\/1361-6463\/ab7794","article-title":"An overview of phase-change memory device physics","volume":"53","author":"Gallo Manuel Le","year":"2020","unstructured":"Manuel Le Gallo and Abu Sebastian. 2020. An overview of phase-change memory device physics. J. Phys. D: Appl. Phys. 53, 21 (2020), 213002.","journal-title":"J. Phys. D: Appl. Phys."},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/978-3-319-46922-5_28","volume-title":"Proceedings of the 27th Australasian Database Conference on Databases Theory and Applications (ADC\u201916)","author":"Li Lu","year":"2016","unstructured":"Lu Li, Peiquan Jin, Chengcheng Yang, Shouhong Wan, and Lihua Yue. 2016. XB+-Tree: A novel index for PCM\/DRAM-based hybrid memory. In Proceedings of the 27th Australasian Database Conference on Databases Theory and Applications (ADC\u201916). Springer, 357\u2013368."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3358201"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2849865"},{"key":"e_1_3_1_29_2","article-title":"APEX: A high-performance learned index on persistent memory","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).","journal-title":"arXiv preprint arXiv:2105.00683"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2442980"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2391254"},{"key":"e_1_3_1_32_2","first-page":"371","volume-title":"Proceedings of the International Conference on Management of Data","author":"Oukid Ismail","year":"2016","unstructured":"Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. 2016. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In Proceedings of the International Conference on Management of Data. 371\u2013386."},{"issue":"4","key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"04022013","DOI":"10.1061\/(ASCE)CP.1943-5487.0001027","article-title":"Phase change memories in smart sensing solutions for structural health monitoring","volume":"36","author":"Quqa Said","year":"2022","unstructured":"Said Quqa, Alessio Antolini, Eleonora Franchi Scarselli, Antonio Gnudi, Andrea Lico, Marcella Carissimi, Marco Pasotti, Roberto Canegallo, Luca Landi, and Pier Paolo Diotallevi. 2022. Phase change memories in smart sensing solutions for structural health monitoring. J. Comput. Civil Eng. 36, 4 (2022), 04022013.","journal-title":"J. Comput. Civil Eng."},{"issue":"3","key":"e_1_3_1_34_2","first-page":"3833","article-title":"Internet of things enabled vehicular and ad hoc networks for smart city traffic monitoring and controlling: A review","volume":"10","author":"Sharif Abida","year":"2018","unstructured":"Abida Sharif, Jian Ping Li, and Muhammad Asim Saleem. 2018. Internet of things enabled vehicular and ad hoc networks for smart city traffic monitoring and controlling: A review. Int. J. Advan. Netw. Applic. 10, 3 (2018), 3833\u20133842.","journal-title":"Int. J. Advan. Netw. Applic."},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.3390\/electronics9061013"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2015.4"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2014.2308213"},{"issue":"1","key":"e_1_3_1_38_2","first-page":"20","article-title":"GeoTNavi\u2013smart navigation using geo-temporal traffic information","volume":"5","author":"Wang Shawn","year":"2013","unstructured":"Shawn Wang, Susamma Barua, Kunal Desai, and Swaroop Deshmukh. 2013. GeoTNavi\u2013smart navigation using geo-temporal traffic information. Int. J. Data Min., Model. Manag. 5, 1 (2013), 20\u201336.","journal-title":"Int. J. Data Min., Model. Manag."},{"key":"e_1_3_1_39_2","first-page":"1","volume-title":"Proceedings of the IEEE International Memory Workshop (IMW\u201920)","year":"2020","unstructured":"Zihui Wang, Xiaojie Hao, Pengfa Xu, Longqian Hu, Dongha Jung, Woojin Kim, Kimihiro Satoh, Bing Yen, Zhiqiang Wei, Lienchang Wang, Jing Zhang, and Yiming Huai. 2020. STT-MRAM for embedded memory applications. In Proceedings of the IEEE International Memory Workshop (IMW\u201920). IEEE, 1\u20133."},{"key":"e_1_3_1_40_2","first-page":"167","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST","volume":"15","author":"Yang Jun","year":"2015","unstructured":"Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He. 2015. NV-Tree: Reducing consistency cost for NVM-based single level systems. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u2019 15). 167\u2013181."},{"key":"e_1_3_1_41_2","first-page":"1","article-title":"Resistive random access memory (RRAM): An overview of materials, switching mechanism, performance, multilevel cell (MLC) storage, modeling, and applications","volume":"15","author":"Zahoor Furqan","year":"2020","unstructured":"Furqan Zahoor, Tun Zainal Azni Zulkifli, and Farooq Ahmad Khanday. 2020. Resistive random access memory (RRAM): An overview of materials, switching mechanism, performance, multilevel cell (MLC) storage, modeling, and applications. Nanosc. Res. Lett. 15 (2020), 1\u201326.","journal-title":"Nanosc. Res. Lett."},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372717"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677179","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:17Z","timestamp":1750291577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,11]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3677179"],"URL":"https:\/\/doi.org\/10.1145\/3677179","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2025,1,11]]},"assertion":[{"value":"2023-11-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}