{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T06:58:30Z","timestamp":1792652310752,"version":"4.5.0"},"reference-count":38,"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\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62172390"],"award-info":[{"award-number":["62172390"]}],"id":[{"id":"10.13039\/501100001809","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>Scan is a fundamental operation widely used in main-memory analytical database systems. To accelerate scans, previous studies build either record-order or sort-order structures known as scan indices. While achieving good performance, scan indices often incur significant space overhead, limiting their use in main-memory databases. For example, the most recent and best performing scan index, BinDex, consists of a sort-order position array, which is an array of rowIDs in the value order, and a set of record-order bit vectors, representing records in pre-defined value intervals. The structures can be much larger than the base data column size.<\/jats:p>\n          <jats:p>In this paper, we propose a novel scan index, Cabin, that exploits the following three techniques for better time-space tradeoff. 1) filter sketches that represent every 2^w-2 value intervals with a w-bit sketched vector, thereby exponentially reducing the space for the bit vectors; 2) selective position array that removes the rowID array for a fraction of intervals in order to lower the space overhead for the position array; and 3) data-aware intervals that judiciously select interval boundaries based on the data characteristics to better support popular values in skewed data distributions or categorical attributes. Experimental results show that compared with state-of-the-art scan solutions, Cabin achieves better time-space tradeoff, and attains 1.70 -- 4.48x improvement for average scan performance given the same space budget.<\/jats:p>","DOI":"10.1145\/3639312","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":5,"title":["Cabin: A Compressed Adaptive Binned Scan Index"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-9959-7391","authenticated-orcid":false,"given":"Yiyuan","family":"Chen","sequence":"first","affiliation":[{"name":"SKLP and Center for Advanced Computer Systems, Institute of Computing Technology, CAS &amp; University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1043-6236","authenticated-orcid":false,"given":"Shimin","family":"Chen","sequence":"additional","affiliation":[{"name":"SKLP and Center for Advanced Computer Systems, Institute of Computing Technology, CAS &amp; University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2023. DBLP Citation Network Dataset. https:\/\/www.aminer.cn\/citation."},{"key":"e_1_2_2_2_1","unstructured":"2023. IMDb Datasets. https:\/\/developer.imdb.com\/non-commercial-datasets\/."},{"key":"e_1_2_2_3_1","unstructured":"2023. stx::Btree(tlx::Btree). https:\/\/github.com\/tlx."},{"key":"e_1_2_2_4_1","volume-title":"Weaving Relations for Cache Performance. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11--14","author":"Ailamaki Anastassia","year":"2001","unstructured":"Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, and Marios Skounakis. 2001. Weaving Relations for Cache Performance. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11--14, 2001, Roma, Italy. Morgan Kaufmann, 169--180."},{"key":"e_1_2_2_5_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509--512."},{"key":"e_1_2_2_6_1","first-page":"9","article-title":"Business Analytics in (a) Blink","volume":"35","author":"Barber Ronald","year":"2012","unstructured":"Ronald Barber, Peter Bendel, Marco Czech, Oliver Draese, Frederick Ho, Namik Hrle, Stratos Idreos, Min-Soo Kim, Oliver Koeth, Jae-Gil Lee, Tianchao Tim Li, Guy M. Lohman, Konstantinos Morfonios, Ren\u00e9 M\u00fcller, Keshava Murthy, Ippokratis Pandis, Lin Qiao, Vijayshankar Raman, Richard Sidle, Knut Stolze, and Sandor Szabo. 2012. Business Analytics in (a) Blink. IEEE Data Eng. Bull. 35, 1 (2012), 9--14.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559877"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409360.1409380"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 2nd International Workshop on In Memory Data Management and Analytics, IMDM 2014","author":"Broneske David","year":"2014","unstructured":"David Broneske, Sebastian Bre\u00df, and Gunter Saake. 2014. Database Scan Variants on Modern CPUs: A Performance Study. In Proceedings of the 2nd International Workshop on In Memory Data Management and Analytics, IMDM 2014, Hangzhou, China, September 1, 2014. 1--15."},{"key":"e_1_2_2_10_1","volume-title":"Bitmap Index Design and Evaluation. In SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2--4","author":"Chan Chee Yong","year":"1998","unstructured":"Chee Yong Chan and Yannis E. Ioannidis. 1998. Bitmap Index Design and Evaluation. In SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2--4, 1998, Seattle, Washington, USA. ACM Press, 355--366."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094114.2094126"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747642"},{"key":"e_1_2_2_14_1","first-page":"22","article-title":"Compilation in the Microsoft SQL Server Hekaton Engine","volume":"37","author":"Freedman Craig","year":"2014","unstructured":"Craig Freedman, Erik Ismert, and Per-\u00c5ke Larson. 2014. Compilation in the Microsoft SQL Server Hekaton Engine. IEEE Data Eng. Bull. 37, 1 (2014), 22--30.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_15_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2012","unstructured":"John L. Hennessy and David A. Patterson. 2012. Computer Architecture - A Quantitative Approach, 5th Edition. Morgan Kaufmann.","edition":"5"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196911"},{"key":"e_1_2_2_17_1","volume-title":"Database Cracking. In Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7--10, 2007, Online Proceedings. www.cidrdb.org, 68--78","author":"Idreos Stratos","year":"2007","unstructured":"Stratos Idreos, Martin L. Kersten, and Stefan Manegold. 2007. Database Cracking. In Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7--10, 2007, Online Proceedings. www.cidrdb.org, 68--78."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453925"},{"key":"e_1_2_2_19_1","volume-title":"Adaptive Execution of Compiled Queries. In 34th IEEE International Conference on Data Engineering, ICDE 2018","author":"Kohn Andr\u00e9","year":"2018","unstructured":"Andr\u00e9 Kohn, Viktor Leis, and Thomas Neumann. 2018. Adaptive Execution of Compiled Queries. In 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, April 16--19, 2018. IEEE Computer Society, 197--208."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447892"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113373"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882925"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14--19","author":"Li Linwei","year":"2020","unstructured":"Linwei Li, Kai Zhang, Jiading Guo, Wen He, Zhenying He, Yinan Jing, Weili Han, and X. Sean Wang. 2020. BinDex: A Two-Layered Index for Fast and Robust Scans. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14--19, 2020. ACM, 909--923."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465322"},{"key":"e_1_2_2_27_1","volume-title":"VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24--27","author":"Moerkotte Guido","year":"1998","unstructured":"Guido Moerkotte. 1998. Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24--27, 1998, New York City, New York, USA. Morgan Kaufmann, 476--487."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253268"},{"key":"e_1_2_2_30_1","volume-title":"IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA","author":"Pirk Holger","year":"2014","unstructured":"Holger Pirk, Stefan Manegold, and Martin L. Kersten. 2014. Waste not... Efficient co-processing of relational data. In IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014. IEEE Computer Society, 508--519."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747645"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_2_33_1","volume-title":"27th International Symposium on Computer Architecture (ISCA 2000","author":"Rixner Scott","year":"2000","unstructured":"Scott Rixner, William J. Dally, Ujval J. Kapasi, Peter R. Mattson, and John D. Owens. 2000. Memory access scheduling. In 27th International Symposium on Computer Architecture (ISCA 2000), June 10--14, 2000, Vancouver, BC, Canada. IEEE Computer Society, 128--138."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465306"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_2_36_1","first-page":"31","article-title":"Runtime Code Generation in Cloudera Impala","volume":"37","author":"Wanderman-Milne Skye","year":"2014","unstructured":"Skye Wanderman-Milne and Nong Li. 2014. Runtime Code Generation in Cloudera Impala. IEEE Data Eng. Bull. 37, 1 (2014), 31--37.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_37_1","volume-title":"Vectorizing Database Column Scans with Complex Predicates. In International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS 2013","author":"Willhalm Thomas","year":"2013","unstructured":"Thomas Willhalm, Ismail Oukid, Ingo M\u00fcller, and Franz Faerber. 2013. Vectorizing Database Column Scans with Complex Predicates. In International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS 2013, Riva del Garda, Trento, Italy, August 26, 2013. 1--12."},{"key":"e_1_2_2_38_1","first-page":"17","article-title":"MonetDB\/X100 - A DBMS In The CPU Cache","volume":"28","author":"Zukowski Marcin","year":"2005","unstructured":"Marcin Zukowski, Peter A. Boncz, Niels Nes, and S\u00e1ndor H\u00e9man. 2005. MonetDB\/X100 - A DBMS In The CPU Cache. IEEE Data Eng. Bull. 28, 2 (2005), 17--22.","journal-title":"IEEE Data Eng. Bull."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639312","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:46Z","timestamp":1755789286000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639312"],"URL":"https:\/\/doi.org\/10.1145\/3639312","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}