APPLE: a new compression scheme for bitmap indexes: poster abstract
Authors: 
Ge Ma, Tao Yu, Guowei Zhu, Kan Lv, Qiyang Huang, Weixi GuAuthors Info & Claims
Pages 663 - 664
Abstract
Compressed bitmap indexes are increasingly used in databases and search engines. By exploiting bit-level parallelism and bitwise operations, e.g. AND/OR operations, they can significantly accelerate the development of many areas. The Word Aligned Hybrid (WAH) bitmap compression scheme using run-length encoding (RLE), is commonly recognized as the most efficient scheme in terms of CPU-performance. This paper presents a new form of compressed bitmap indexes named Adaptive Partitioned Position List Encoding (APPLE), which uses packed position lists for compression. For experiments, we compare it with Huffman encoding, and two enhanced variants of WAH : Concise and COMPAX. Our empirical results show this scheme achieves significant improvement.
References
[1]
G. Ma, et al. "Wireless Caching in Large-Scale Edge Access Points: A Local Distributed Approach." MobiCom. ACM, 2018.
[2]
Z. Chen, et al. "A Survey of Bitmap Index Compression Algorithms for Big Data". Tsinghua Science & Technology (2015): 100--115.
[3]
F. Fusco, et al. "RecoNet: An Interpretable Neural Architecture for Recommender Systems." IJCAI, 2019.
[4]
F. Yang, et al. "Druid: A Real-time Analytical Data Store." SIGMOD. ACM, 2014.
[5]
P. Chhikara, et al. "Data dimensionality reduction techniques for Industry 4.0: Research results, challenges, and future research directions." Software Practice and Experience 4(2020).
[6]
G. Ma, et al. "BreadZip: A Combination of Network Traffic Data and Bitmap Index Encoding Algorithm." SMC. IEEE, 2014.
[7]
Y. Wu, et al. "A General Analytical Model for Spatial and Temporal Performance of Bitmap Index Compression Algorithms in Big Data." ICCCN. IEEE, 2014.
[8]
Y. Wen, et al. "SECOMPAX: A Bitmap Index Compression Algorithm." ICCCN. IEEE, 2014.
[9]
G. Ma, et al. "Understanding Performance of Edge Content Caching for Mobile Video Streaming." JSAC (2017): 1076--1089.
Index Terms
- APPLE: a new compression scheme for bitmap indexes: poster abstract
Recommendations
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 ...
Histogram-aware sorting for enhanced word-aligned compression in bitmap indexes
DOLAP '08: Proceedings of the ACM 11th international workshop on Data warehousing and OLAPBitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. ...
Better bitmap performance with Roaring bitmaps
Bitmap indexes are commonly used in databases and search engines. By exploiting bit-level parallelism, they can significantly accelerate queries. However, they can use much memory, and thus, we might prefer compressed bitmap indexes. Following Oracle's ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2020
852 pages
ISBN:9781450375900
DOI:10.1145/3384419
Copyright © 2020 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
- SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
- SIGCOMM: ACM Special Interest Group on Data Communication
- SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing
- SIGOPS: ACM Special Interest Group on Operating Systems
- SIGBED: ACM Special Interest Group on Embedded Systems
- SIGARCH: ACM Special Interest Group on Computer Architecture
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 November 2020
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
SenSys '20: The 18th ACM Conference on Embedded Networked Sensor Systems
November 16 - 19, 2020
Virtual Event, Japan
Acceptance Rates
Overall Acceptance Rate 174 of 867 submissions, 20%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 87Total Downloads
- Downloads (Last 12 months)10
- Downloads (Last 6 weeks)4
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
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