{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T06:58:19Z","timestamp":1792652299646,"version":"4.5.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100019783","name":"National Agency for Research and Development","doi-asserted-by":"crossref","award":["DOCTORADO BECAS CHILE\/2023 - 72230222"],"award-info":[{"award-number":["DOCTORADO BECAS CHILE\/2023 - 72230222"]}],"id":[{"id":"10.13039\/100019783","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Data stream processing systems enable querying over sliding windows of streams of data. Efficient index structures for the streaming window are a crucial building block to enable querying the sliding window for operations such as aggregation and joins. This paper proposes SWIX, a novel memory-efficient learned index for sliding windows. Unlike conventional learned indexes that rely on tree structures to achieve logarithmic query cost, SWIX has a flat structure that uses substantially less memory and enables efficient query execution while having a low cost for index maintenance when inserting (and retraining). SWIX dynamically adapts itself to the real-time distribution shifts of data streams.<\/jats:p>\n                  <jats:p>SWIX outperforms existing indexes in terms of query execution time and memory footprint for workloads characterized by very frequent updates. Our results show that SWIX has a significantly smaller memory footprint than conventional, streaming, and learned indexes, using only 22% to 42% of the size compared to state-of-the-art approaches, yet outperforming them by up 1.2\u00d7 to 1.6\u00d7 on average (and up to 52\u00d7) in terms of query time, making it a space- and time-efficient method for indexing data streams. For concurrent learned indexes, Parallel SWIX can achieve up to 3.45\u00d7 throughput with only 34% of memory consumption.<\/jats:p>","DOI":"10.1145\/3639296","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":8,"title":["SWIX: A Memory-efficient Sliding Window Learned Index"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4566-6178","authenticated-orcid":false,"given":"Liang","family":"Liang","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6456-9077","authenticated-orcid":false,"given":"Guang","family":"Yang","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2010-0765","authenticated-orcid":false,"given":"Ali","family":"Hadian","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0101-4431","authenticated-orcid":false,"given":"Luis Alberto","family":"Croquevielle","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7470-2123","authenticated-orcid":false,"given":"Thomas","family":"Heinis","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPCW.2016.014"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1694-0_16"},{"key":"e_1_2_2_3_1","volume-title":"Optimal piecewise linear function approximation for GPU-based applications","author":"Berj\u00f3n Daniel","year":"2015","unstructured":"Daniel Berj\u00f3n, Guillermo Gallego, Carlos Cuevas, Francisco Mor\u00e1n, and Narciso Garc'ia. 2015. Optimal piecewise linear function approximation for GPU-based applications. IEEE transactions on cybernetics, Vol. 46, 11 (2015), 2584--2595."},{"key":"e_1_2_2_4_1","unstructured":"bingmann. 2019. STX-BTree. https:\/\/github.com\/bingmann\/stx-btree Last Accessed: 2023--12--28."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_2_2_6_1","volume-title":"Boyang Jerry Peng, et al","author":"Chintapalli Sanket","year":"2016","unstructured":"Sanket Chintapalli, Derek Dagit, Bobby Evans, Reza Farivar, Thomas Graves, Mark Holderbaugh, Zhuo Liu, Kyle Nusbaum, Kishorkumar Patil, Boyang Jerry Peng, et al. 2016. Benchmarking streaming computation engines: Storm, flink and spark streaming. In 2016 IEEE international parallel and distributed processing symposium workshops (IPDPSW). IEEE, 1789--1792."},{"key":"e_1_2_2_7_1","unstructured":"Yifan Dai Yien Xu Aishwarya Ganesan Ramnatthan Alagappan Brian Kroth Andrea Arpaci-Dusseau and Remzi Arpaci-Dusseau. 2020. From wisckey to bourbon: A learned index for log-structured merge trees. In OSDI. 155--171."},{"key":"e_1_2_2_8_1","volume-title":"Order statistics","author":"David Herbert A","unstructured":"Herbert A David and Haikady N Nagaraja. 2004. Order statistics. John Wiley & Sons."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190660"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_2_2_14_1","unstructured":"gvinciguerra. 2023. PGM-Index. https:\/\/github.com\/gvinciguerra\/PGM-index Last Accessed: 2023--12--28."},{"key":"e_1_2_2_15_1","volume-title":"COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies. arXiv preprint arXiv:2006.16393","author":"Hadian Ali","year":"2021","unstructured":"Ali Hadian, Behzad Ghaffari, Taiyi Wang, and Thomas Heinis. 2021. COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies. arXiv preprint arXiv:2006.16393 (2021)."},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT).","author":"Hadian Ali","year":"2019","unstructured":"Ali Hadian and Thomas Heinis. 2019. Interpolation-friendly B-trees: Bridging the Gap Between Algorithmic and Learned Indexes. In Proceedings of the International Conference on Extending Database Technology (EDBT)."},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB).","author":"Hadian Ali","year":"2020","unstructured":"Ali Hadian and Thomas Heinis. 2020. MADEX: Learning-augmented Algorithmic Index Structures. In Proceedings of the International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB)."},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT).","author":"Hadian Ali","year":"2021","unstructured":"Ali Hadian and Thomas Heinis. 2021. Shift-Table: A Low-latency Learned Index for Range Queries using Model Correction. In Proceedings of the International Conference on Extending Database Technology (EDBT)."},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB).","author":"Hadian Ali","year":"2020","unstructured":"Ali Hadian, Ankit Kumar, and Thomas Heinis. 2020. Hands-off Model Integration in Spatial Index Structures. In Proceedings of the International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB)."},{"key":"e_1_2_2_20_1","unstructured":"Intel. 1997. Read Time-Stamp Counter. https:\/\/c9x.me\/x86\/html\/file_module_x86_id_278.html Last Accessed: 2023--10--14."},{"key":"e_1_2_2_21_1","volume-title":"SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2019. SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems (2019)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 1st International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB).","author":"Llavesh Anisa","year":"2019","unstructured":"Anisa Llavesh, Utku Sirin, Robert West, and Anastasia Ailamaki. 2019. Accelerating Btree Search by Using Simple Machine Learning Techniques. In Proceedings of the 1st International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384706"},{"key":"e_1_2_2_31_1","unstructured":"microsoft. 2022. ALEX. https:\/\/github.com\/microsoft\/ALEX Last Accessed: 2023--12--28."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB).","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 International VLDB Workshop on Applied AI for Database Systems and Applications (AIDB)."},{"key":"e_1_2_2_34_1","volume-title":"Benjamin IP Rubinstein, and Renata Borovica-Gajic","author":"Setiawan Naufal Fikri","year":"2020","unstructured":"Naufal Fikri Setiawan, Benjamin IP Rubinstein, and Renata Borovica-Gajic. 2020. Function Interpolation for Learned Index Structures. In ADC."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380576"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Springer, 1--17","author":"Sprenger Stefan","year":"2016","unstructured":"Stefan Sprenger, Steffen Zeuch, and Ulf Leser. 2016. Cache-sensitive skip list: Efficient range queries on modern cpus. In Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Springer, 1--17."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470717"},{"key":"e_1_2_2_38_1","unstructured":"Chuzhe Tang. 2022a. FINEdex. https:\/\/github.com\/iotlpf\/FINEdex Last Accessed: 2023--12--28."},{"key":"e_1_2_2_39_1","unstructured":"Chuzhe Tang. 2022b. XIndex. https:\/\/ipads.se.sjtu.edu.cn:1312\/opensource\/xindex Last Accessed: 2023--12--28."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_2_41_1","volume-title":"Updatable learned index with precise positions. arXiv preprint arXiv:2104.05520","author":"Wu Jiacheng","year":"2021","unstructured":"Jiacheng Wu, Yong Zhang, Shimin Chen, Jin Wang, Yu Chen, and Chunxiao Xing. 2021. Updatable learned index with precise positions. arXiv preprint arXiv:2104.05520 (2021)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.54"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02831750"},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). 234--246","author":"Yang Guang","year":"2023","unstructured":"Guang Yang, Liang Liang, Ali Hadian, and Thomas Heinis. 2023. FLIRT: A Fast Learned Index for Rolling Time frames. In Proceedings of the International Conference on Extending Database Technology (EDBT). 234--246."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551823"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452793"},{"key":"e_1_2_2_47_1","volume-title":"REMIX: Efficient Range Query for LSM-trees. In USENIX Conference on File and Storage Technologies (FAST). 51--64","author":"Zhong Wenshao","year":"2021","unstructured":"Wenshao Zhong, Chen Chen, Xingbo Wu, and Song Jiang. 2021. REMIX: Efficient Range Query for LSM-trees. In USENIX Conference on File and Storage Technologies (FAST). 51--64."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639296","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:17:47Z","timestamp":1755789467000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639296"],"URL":"https:\/\/doi.org\/10.1145\/3639296","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}