{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:40:03Z","timestamp":1755870003122,"version":"3.44.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["OAC-1835446, SHF-2312739"],"award-info":[{"award-number":["OAC-1835446, SHF-2312739"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>Bit-parallel scanning techniques are characterized by their ability to accelerate compute through the process known as early pruning. Early pruning techniques iterate over the bits of each value, searching for opportunities to safely prune compute early, before processing each data value in its entirety. However, because of this iterative evaluation, the effectiveness of early pruning depends on the relative position of bits that can be used for pruning within each value. Due to this behavior, bit-parallel techniques have faced significant challenges when processing skewed data, especially when values contain many leading zeroes. This problem is further amplified by the inherent trade-off that bit-parallel techniques make between columnar scan and fetch performance: a storage layer that supports early pruning requires multiple memory accesses to fetch a single value. Thus, in the case of skewed data, bit-parallel techniques increase fetch latency without significantly improving scan performance when compared to baseline columnar implementations.<\/jats:p>\n          <jats:p>To remedy this shortcoming, we transform the values in bit-parallel columns using novel encodings. We propose the concept of forward encodings: a family of encodings that shift pruning-relevant bits closer to the most significant bit. Using this concept, we propose two particular encodings: the Data Forward Encoding and the Extended Data Forward Encoding. We demonstrate the impact of these encodings using multiple real-world datasets. Across these datasets, forward encodings improve the current state-of-the-art bit-parallel technique's scan and fetch performance in many cases by 1.4x and 1.3x, respectively.<\/jats:p>","DOI":"10.1145\/3626751","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-27","source":"Crossref","is-referenced-by-count":1,"title":["Rethinking the Encoding of Integers for Scans on Skewed Data"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4348-236X","authenticated-orcid":false,"given":"Martin","family":"Prammer","sequence":"first","affiliation":[{"name":"University of Wisconsin - Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3653-2538","authenticated-orcid":false,"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142548"},{"key":"e_1_2_1_2_1","unstructured":"Apache Parquet. 2022. Apache Parquet Documentation. https:\/\/parquet.apache.org\/docs\/"},{"key":"e_1_2_1_3_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 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 Engineering Bulletin, Vol. 35, 1 (2012), 9--14.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409360.1409380"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536260"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2019 USENIX Annual Technical Conference (Renton, WA, USA) (USENIX ATC '19). USENIX Association, USA, 1--14","author":"Duplyakin Dmitry","year":"2019","unstructured":"Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019. The Design and Operation of Cloudlab. In Proceedings of the 2019 USENIX Annual Technical Conference (Renton, WA, USA) (USENIX ATC '19). USENIX Association, USA, 1--14."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_8_1","unstructured":"Federal Election Commission. 2022. Individual Contributions. https:\/\/www.fec.gov\/introduction-campaign-finance\/how-to-research-public-records\/individual-contributions\/"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747642"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1956.5219803"},{"key":"e_1_2_1_11_1","volume-title":"The SAP HANA database - An architecture overview","author":"F\u00e4rber Franz","year":"2012","unstructured":"Franz F\u00e4rber, Norman May, Wolfgang Lehner, Philipp Gro\u00dfe, Ingo M\u00fcller, Hannes Rauhe, and Jonathan Dees. 2012. The SAP HANA database - An architecture overview. IEEE Data Eng. Bull., Vol. 35 (03 2012), 28--33."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330993"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","unstructured":"IEEE. 2019. IEEE Standard for Floating-Point Arithmetic. https:\/\/doi.org\/10.1109\/ieeestd.2019.8766229","DOI":"10.1109\/ieeestd.2019.8766229"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457283"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453925"},{"key":"e_1_2_1_17_1","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1997. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Addison-Wesley Longman Publishing Co., Inc., USA, Chapter 4.1: Positional Number Systems.","edition":"3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047491"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360994"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00052"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737787"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465322"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732965"},{"key":"e_1_2_1_24_1","unstructured":"Meta Platforms Inc. [n. d.]. Zstandard. https:\/\/facebook.github.io\/zstd\/"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Paulius Micikevicius Dusan Stosic Neil Burgess Marius Cornea Pradeep Dubey Richard Grisenthwaite Sangwon Ha Alexander Heinecke Patrick Judd John Kamalu Naveen Mellempudi Stuart Oberman Mohammad Shoeybi Michael Siu and Hao Wu. 2022. FP8 Formats for Deep Learning. https:\/\/doi.org\/10.48550\/ARXIV.2209.05433","DOI":"10.48550\/ARXIV.2209.05433"},{"key":"e_1_2_1_26_1","unstructured":"New York City Metropolitan Transportation Authority. 2021. Car Toll Rates. https:\/\/new.mta.info\/fares-and-tolls\/bridges-and-tunnels\/tolls-by-vehicle\/cars"},{"key":"e_1_2_1_27_1","volume-title":"TLC Trip Record Data - Yellow Taxi Trip Records","author":"New York City Taxi and Limousine Commission","year":"2022","unstructured":"New York City Taxi and Limousine Commission. 2022. TLC Trip Record Data - Yellow Taxi Trip Records, 2022. https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page"},{"volume-title":"The Star Schema Benchmark and Augmented Fact Table Indexing","author":"O'Neil Patrick","key":"e_1_2_1_28_1","unstructured":"Patrick O'Neil, Elizabeth O'Neil, Xuedong Chen, and Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing. In Performance Evaluation and Benchmarking, Raghunath Nambiar and Meikel Poess (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 237--252."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253268"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3184470.3184471"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497414"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1971.1090789"},{"key":"e_1_2_1_33_1","unstructured":"Neal Richardson Ian Cook Nic Crane Dewey Dunnington Romain Fran\u00e7ois Jonathan Keane Drago? Moldovan-Gr\u00fcnfeld Jeroen Ooms and Apache Arrow. 2022. arrow: Integration to 'Apache' 'Arrow'. https:\/\/github.com\/apache\/arrow\/ https:\/\/arrow.apache.org\/docs\/r\/."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375669"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3124544"},{"key":"e_1_2_1_36_1","unstructured":"The Transaction Processing Council. 2022. TPC-H Benchmark (Version 3.0.1). http:\/\/www.tpc.org\/tpch\/"},{"key":"e_1_2_1_37_1","unstructured":"UK Power Networks. 2014. SmartMeter Energy Consumption Data in London Households. https:\/\/data.london.gov.uk\/dataset\/smartmeter-energy-use-data-in-london-households"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/85.238389"},{"key":"e_1_2_1_39_1","unstructured":"Shibo Wang and Pankaj Kanwar. 2019. BFloat16: The secret to high performance on Cloud TPUs. https:\/\/cloud.google.com\/blog\/products\/ai-machine-learning\/bfloat16-the-secret-to-high-performance-on-cloud-tpus"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687671"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00028"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCA.2022.3201168"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.148"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626751","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626751","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:03:57Z","timestamp":1755867837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626751"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626751"],"URL":"https:\/\/doi.org\/10.1145\/3626751","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}