https://dl.acm.org/doi/10.1145/3035918.3064007 skip to main content * ACM Digital Library home * ACM Association for Computing Machinery corporate logo * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search 10.1145/3035918.3064007acmconferencesArticle/Chapter ViewAbstract Publication PagesmodConference Proceedingsconference-collections mod * Conference * Proceedings * Upcoming Events * Authors * Affiliations * Award Winners * More * Home * Conferences * MOD * Proceedings * SIGMOD '17 * An Experimental Study of Bitmap Compression vs. Inverted List Compression Export Citations Select Citation format[BibTeX ] * Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download,a status dialog will open to start the export process. The process may takea few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. + Download citation + Copy citation research-article Share on * * * * * * An Experimental Study of Bitmap Compression vs. Inverted List Compression Authors: [default-pr]Jianguo Wang, [default-pr]Chunbin Lin, [default-pr]Yannis Papakonstantinou, [contrib-81]Steven Swanson Authors Info & Claims SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data Pages 993 - 1008 https://doi.org/10.1145/3035918.3064007 Published: 09 May 2017 Publication History 60citation1,189Downloads Metrics Total Citations60 Total Downloads1,189 Last 12 Months83 Last 6 weeks11 Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account Get Access Contents SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data An Experimental Study of Bitmap Compression vs. Inverted List Compression Pages 993 - 1008 PREVIOUS CHAPTER A Cost-based Optimizer for Gradient Descent Optimization Previous NEXT CHAPTER Automatic Database Management System Tuning Through Large-scale Machine Learning Next * Abstract * References ACM Digital Library * Information & Contributors * Bibliometrics & Citations * Get Access * References * Figures * Tables * Media * Share Abstract [3035918] Bitmap compression has been studied extensively in the database area and many efficient compression schemes were proposed, e.g., BBC, WAH, EWAH, and Roaring. Inverted list compression is also a well-studied topic in the information retrieval community and many inverted list compression algorithms were developed as well, e.g., VB, PforDelta, GroupVB, Simple8b, and SIMDPforDelta. We observe that they essentially solve the same problem, i.e., how to store a collection of sorted integers with as few as possible bits and support query processing as fast as possible. Due to historical reasons, bitmap compression and inverted list compression were developed as two separated lines of research in the database area and information retrieval area. Thus, a natural question is: Which one is better between bitmap compression and inverted list compression? To answer the question, we present the first comprehensive experimental study to compare a series of 9 bitmap compression methods and 12 inverted list compression methods. We compare these 21 algorithms on synthetic datasets with different distributions (uniform, zipf, and markov) as well as 8 real-life datasets in terms of the space overhead, decompression time, intersection time, and union time. Based on the results, we provide many lessons and guidelines that can be used for practitioners to decide which technique to adopt in future systems and also for researchers to develop new algorithms. References [1] D. Abadi, S. Madden, and M. Ferreira. Integrating compression and execution in column-oriented database systems. In SIGMOD, pages 671--682, 2006. Digital Library Google Scholar [2] V. N. Anh and A. Moffat. Inverted index compression using word-aligned binary codes. IR, 8(1):151--166, 2005. Digital Library Google Scholar [3] V. N. Anh and A. Moffat. Index compression using 64-bit words. SPE, 40(2):131--147, 2010. Digital Library Google Scholar [4] G. Antoshenkov. Byte-aligned bitmap compression. In DCC, page 476, 1995. Digital Library Google Scholar [5] M. Athanassoulis, Z. Yan, and S. Idreos. Upbit: Scalable in-memory updatable bitmap indexing. In SIGMOD, pages 1319--1332, 2016. Digital Library Google Scholar [6] R. A. Baeza-Yates, C. Castillo, F. Junqueira, V. Plachouras, and F. Silvestri. Challenges on distributed web retrieval. In ICDE, pages 6--20, 2007. Crossref Google Scholar [7] L. A. Barroso, J. Dean, and U. Holzle. Web search for a planet: The google cluster architecture. IEEE Micro, 23(2):22--28, 2003. Digital Library Google Scholar [8] T. A. Bjorklund, N. Grimsmo, J. Gehrke, and O. Torbjornsen. Inverted indexes vs. bitmap indexes in decision support systems. In CIKM, pages 1509--1512, 2009. Digital Library Google Scholar [9] B. B. Cambazoglu and R. A. Baeza-Yates. Scalability and efficiency challenges in large-scale web search engines. In SIGIR, pages 1223--1226, 2016. Digital Library Google Scholar [10] S. Chambi, D. Lemire, O. Kaser, and R. Godin. Better bitmap performance with roaring bitmaps. SPE, 46(5):709--719, 2016. Digital Library Google Scholar [11] C. Y. Chan and Y. E. Ioannidis. Bitmap index design and evaluation. In SIGMOD, pages 355--366, 1998. Digital Library Google Scholar [12] C. Y. Chan and Y. E. Ioannidis. An efficient bitmap encoding scheme for selection queries. In SIGMOD, pages 215--226, 1999. Digital Library Google Scholar [13] A. Colantonio and R. D. Pietro. Concise: Compressed 'n' composable integer set. IPL, 110(16):644--650, 2010. Digital Library Google Scholar [14] J. S. Culpepper and A. Moffat. Efficient set intersection for inverted indexing. TOIS, 29(1):1--25, 2010. Digital Library Google Scholar [15] D. R. Cutting and J. O. Pedersen. Optimizations for dynamic inverted index maintenance. In SIGIR, pages 405--411, 1990. Digital Library Google Scholar [16] J. Dean. Challenges in building large-scale information retrieval systems: Invited talk. In WSDM, page 1, 2009. Digital Library Google Scholar [17] F. Deliege and T. B. Pedersen. Position list word aligned hybrid: Optimizing space and performance for compressed bitmaps. In EDBT, pages 228--239, 2010. Digital Library Google Scholar [18] H. Garcia-Molina, J. D. Ullman, and J. Widom. Database Systems: The Complete Book. Prentice Hall Press, 2008. Digital Library Google Scholar [19] G. Guzun and G. Canahuate. Hybrid query optimization for hard-to-compress bit-vectors. VLDBJ, 25(3):339--354, 2016. Digital Library Google Scholar [20] G. Guzun, G. Canahuate, D. Chiu, and J. Sawin. A tunable compression framework for bitmap indices. In ICDE, pages 484--495, 2014. Crossref Google Scholar [21] M. E. Haque, Y. H. Eom, Y. He, S. Elnikety, R. Bianchini, and K. S. McKinley. Few-to-many: Incremental parallelism for reducing tail latency in interactive services. In ASPLOS, pages 161--175, 2015. Digital Library Google Scholar [22] A. S. Kesheng Wu, Ekow J. Otoo and H. Nordberg. Notes on design and implementation of compressed bit vectors, 2001. Google Scholar [23] S. Kim, J. Lee, S. R. Satti, and B. Moon. Sbh: Super byte-aligned hybrid bitmap compression. IS, 62:155--168, 2016. Digital Library Google Scholar [24] A. Lamb, M. Fuller, R. Varadarajan, N. Tran, B. Vandier, L. Doshi, and C. Bear. The vertica analytic database: C-store 7 years later. PVLDB, 5(12):1790--1801, 2012. Digital Library Google Scholar [25] D. Lemire and L. Boytsov. Decoding billions of integers per second through vectorization. SPE, 45(1):1--29, 2015. Digital Library Google Scholar [26] D. Lemire, O. Kaser, and K. Aouiche. Sorting improves word-aligned bitmap indexes. DKE, 69(1):3--28, 2010. Digital Library Google Scholar [27] C. D. Manning, P. Raghavan, and H. Schutze. Introduction to Information Retrieval. Cambridge University Press, 2008. Crossref Google Scholar [28] S. Mehrotra, S. Chauhan, and H. Bansal. Apache Hive Cookbook. Packt Publishing, 2016. Digital Library Google Scholar [29] P. O'Neil, E. O'Neil, X. Chen, and S. Revilak. The star schema benchmark and augmented fact table indexing. 2009. Digital Library Google Scholar [30] G. Ottaviano and R. Venturini. Partitioned elias-fano indexes. In SIGIR, pages 273--282, 2014. Digital Library Google Scholar [31] V. Raman, L. Qiao, W. Han, I. Narang, Y.-L. Chen, K.-H. Yang, and F.-L. Ling. Lazy, adaptive rid-list intersection, and its application to index anding. In SIGMOD, pages 773--784, 2007. Digital Library Google Scholar [32] K. Stockinger, J. Cieslewicz, K. Wu, D. Rotem, and A. Shoshani. Using bitmap index for joint queries on structured and text data. In New Trends in Data Warehousing and Data Analysis, pages 1--23. 2009. Crossref Google Scholar [33] S. Tatikonda, B. B. Cambazoglu, and F. P. Junqueira. Posting list intersection on multicore architectures. In SIGIR, pages 963--972, 2011. Digital Library Google Scholar [34] L. Thiel and H. Heaps. Program design for retrospective searches on large data bases. IPM, 8(1):1--20, 1972. Google Scholar [35] S. Vigna. Quasi-succinct indices. In WSDM, pages 83--92, 2013. Digital Library Google Scholar [36] J. Wang, E. Lo, M. L. Yiu, J. Tong, G. Wang, and X. Liu. The impact of solid state drive on search engine cache management. In SIGIR, pages 693--702, 2013. Digital Library Google Scholar [37] J. Wang, E. Lo, M. L. Yiu, J. Tong, G. Wang, and X. Liu. Cache design of ssd-based search engine architectures: An experimental study. TOIS, 32(4):1--26, 2014. Digital Library Google Scholar [38] K. Wu, E. J. Otoo, and A. Shoshani. On the performance of bitmap indices for high cardinality attributes. In VLDB, pages 24--35, 2004. Digital Library Google Scholar [39] K. Wu, E. J. Otoo, and A. Shoshani. Optimizing bitmap indices with efficient compression. TODS, 31(1):1--38, 2006. Digital Library Google Scholar [40] H. Yan, S. Ding, and T. Suel. Inverted index compression and query processing with optimized document ordering. In WWW, pages 401--410, 2009. Digital Library Google Scholar [41] J. Yun, Y. He, S. Elnikety, and S. Ren. Optimal aggregation policy for reducing tail latency of web search. In SIGIR, pages 63--72, 2015. Digital Library Google Scholar [42] J. Zhang, X. Long, and T. Suel. Performance of compressed inverted list caching in search engines. In WWW, pages 387--396, 2008. Digital Library Google Scholar [43] M. Zukowski, S. Heman, N. Nes, and P. Boncz. Super-scalar ram-cpu cache compression. In ICDE, 2006. Digital Library Google Scholar Cited By View all * Su JHao CSun SZhang HGao SJiang JChen YZhang CHe BGuo M(2025) Revisiting the Design of In-Memory Dynamic Graph Storage Proceedings of the ACM on Management of Data10.1145/37097203:1 (1-27)Online publication date: 11-Feb-2025 https://dl.acm.org/doi/10.1145/3709720 * Xu QYang JZhang FChen ZGuan JChen KFan JShen YYang KZhang YDu X (2024)Improving Graph Compression for Efficient Resource-Constrained Graph AnalyticsProceedings of the VLDB Endowment10.14778/3665844.366585217:9(2212-2226)Online publication date: 1-May-2024 https://dl.acm.org/doi/10.14778/3665844.3665852 * Lv YZhang KWang ZZhang XLee RHe ZJing YWang X(2024)RTScan: Efficient Scan with Ray Tracing CoresProceedings of the VLDB Endowment10.14778/3648160.364818317:6(1460-1472)Online publication date: 3-May-2024 https://doi.org/10.14778/3648160.3648183 * Show More Cited By Index Terms 1. An Experimental Study of Bitmap Compression vs. Inverted List Compression 1. Information systems 1. Data management systems 1. Data structures 1. Data layout 1. Data compression 2. Database management system engines 1. Database query processing 1. Query optimization 2. Main memory engines 2. Information retrieval 1. Search engine architectures and scalability 1. Search index compression 3. World Wide Web 1. Web searching and information discovery 1. Web search engines 1. Web indexing Recommendations * Optimizing query execution for variable-aligned length compression of bitmap indices IDEAS '14: Proceedings of the 18th International Database Engineering & Applications Symposium Indexing is a fundamental mechanism for efficient data access. Recently, we proposed the Variable-Aligned Length (VAL) bitmap index encoding framework, which generalizes the commonly used word-aligned compression techniques. VAL presented a variable-... Read More * Optimizing bitmap indices with efficient compression Bitmap indices are efficient for answering queries on low-cardinality attributes. In this article, we present a new compression scheme called Word-Aligned Hybrid (WAH) code that makes compressed bitmap indices efficient even for high-cardinality ... Read More * Inverted indexes vs. bitmap indexes in decision support systems CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management Bitmap indexes are widely used in Decision Support Systems (DSSs) to improve query performance. In this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from Information Retrieval as an alternative. In a ... Read More Comments Please enable JavaScript to view thecomments powered by Disqus. Information & Contributors Information Published In cover image ACM Conferences SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data May 2017 1810 pages ISBN:9781450341974 DOI:10.1145/3035918 * General Chairs: * Author PictureRada Chirkova North Carolina State University, USA , * Author PictureJun Yang Duke University, USA , * Program Chair: * Author PictureDan Suciu University of Washington, USA Copyright (c) 2017 ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected] Sponsors * SIGMOD: ACM Special Interest Group on Management of Data Publisher Association for Computing Machinery New York, NY, United States Publication History Published: 09 May 2017 Permissions Request permissions for this article. Request Permissions Check for updates Author Tags 1. benchmarking 2. bitmap compression 3. evaluation 4. inverted list compression 5. main memory Qualifiers * Research-article Conference SIGMOD/PODS'17 Sponsor: * SIGMOD SIGMOD/PODS'17: International Conference on Management of Data May 14 - 19, 2017 Illinois, Chicago, USA Acceptance Rates Overall Acceptance Rate 785 of 4,003 submissions, 20% Contributors [loader-7e6] Other Metrics View Article Metrics Bibliometrics & Citations Bibliometrics Article Metrics * 60 Total Citations View Citations * 1,189 Total Downloads * Downloads (Last 12 months)83 * Downloads (Last 6 weeks)11 Reflects downloads up to 01 Mar 2025 Other Metrics View Author Metrics Citations Cited By View all * Su JHao CSun SZhang HGao SJiang JChen YZhang CHe BGuo M(2025) Revisiting the Design of In-Memory Dynamic Graph Storage Proceedings of the ACM on Management of Data10.1145/37097203:1 (1-27)Online publication date: 11-Feb-2025 https://dl.acm.org/doi/10.1145/3709720 * Xu QYang JZhang FChen ZGuan JChen KFan JShen YYang KZhang YDu X (2024)Improving Graph Compression for Efficient Resource-Constrained Graph AnalyticsProceedings of the VLDB Endowment10.14778/3665844.366585217:9(2212-2226)Online publication date: 1-May-2024 https://dl.acm.org/doi/10.14778/3665844.3665852 * Lv YZhang KWang ZZhang XLee RHe ZJing YWang X(2024)RTScan: Efficient Scan with Ray Tracing CoresProceedings of the VLDB Endowment10.14778/3648160.364818317:6(1460-1472)Online publication date: 3-May-2024 https://doi.org/10.14778/3648160.3648183 * Chen XTian JBeaver IFreeman CYan YWang JTao D(2024)FCBench: Cross-Domain Benchmarking of Lossless Compression for Floating-Point DataProceedings of the VLDB Endowment10.14778/ 3648160.364818017:6(1418-1431)Online publication date: 1-Feb-2024 https://dl.acm.org/doi/10.14778/3648160.3648180 * Gao CBallijepalli SWang J(2024)Revisiting B-tree Compression: An Experimental StudyProceedings of the ACM on Management of Data 10.1145/36549722:3(1-25)Online publication date: 30-May-2024 https://doi.org/10.1145/3654972 * Yang LGilad YAlizadeh MSekar VYu MSeneviratne AVeitch D(2024) Practical Rateless Set ReconciliationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672219(595-612)Online publication date: 4-Aug-2024 https://dl.acm.org/doi/10.1145/3651890.3672219 * Zeng XZhang S(2024)CStream: Parallel Data Stream Compression on Multicore Edge DevicesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338686236:11(5889-5904)Online publication date: Nov-2024 https://doi.org/10.1109/TKDE.2024.3386862 * Zhang YZhang FLi HZhang SGuo XChen YPan ADu X(2024)Data-Aware Adaptive Compression for Stream ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.337771036:9 (4531-4549)Online publication date: Sep-2024 https://doi.org/10.1109/TKDE.2024.3377710 * Zheng HLi YXiong FLi XZou LShi PQin Z(2024)Vertex Encoding for Edge Nonexistence Determination With SIMD AccelerationIEEE Transactions on Knowledge and Data Engineering10.1109/ TKDE.2024.335091936:7(3600-3614)Online publication date: Jul-2024 https://doi.org/10.1109/TKDE.2024.3350919 * He HXu ZLi RBao JLi TZheng Y(2024)TMan: A High-Performance Trajectory Data Management System Based on Key-Value Stores2024 IEEE 40th International Conference on Data Engineering (ICDE) 10.1109/ICDE60146.2024.00376(4951-4964)Online publication date: 13-May-2024 https://doi.org/10.1109/ICDE60146.2024.00376 * Show More Cited By View Options Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Publication View options PDF View or Download as a PDF file. PDF eReader View online with eReader. eReader Figures Tables Media Share Share Share this Publication link Copy Link Copied! Copying failed. Share on social media XLinkedInRedditFacebookemail Affiliations [default-pr] Jianguo Wang University of California, San Diego, San Diego, CA, USA View Profile [default-pr] Chunbin Lin University of California, San Diego, San Diego, CA, USA View Profile [default-pr] Yannis Papakonstantinou University of California, San Diego, San Diego, CA, USA View Profile [contrib-81] Steven Swanson University of California, San Diego, San Diego, CA, USA View Profile Download PDF Go to Go to Show all references Request permissionsExpand All Collapse Expand Table Authors Info & Affiliations View Table of Conten Footer Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * ACM Digital Library Board * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System * Accessibility Statement Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact us via email * ACM on Facebook * ACM DL on X * ACM on Linkedin * Send Feedback * Submit a Bug Report The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2025 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM Association for Computing Machinery corporate logo Your Search Results Download Request We are preparing your search results for download ... We will inform you here when the file is ready. Download now! Your Search Results Download Request Your file of search results citations is now ready. Download now! Your Search Results Download Request Your search export query has expired. Please try again.