Tree-Encoded Bitmaps

Lang H, Beischl A, Leis V, Boncz P, Neumann T, Kemper A (2020)

Publication Type: Conference contribution

Publication year: 2020

Publisher: Association for Computing Machinery

Pages Range: 937-967

Conference Proceedings Title: Proceedings of the ACM SIGMOD International Conference on Management of Data

Event location: Portland, OR US

ISBN: 9781450367356

DOI: 10.1145/3318464.3380588

Abstract

We propose a novel method to represent compressed bitmaps. Similarly to existing bitmap compression schemes, we exploit the compression potential of bitmaps populated with consecutive identical bits, i.e., 0-runs and 1-runs. But in contrast to prior work, our approach employs a binary tree structure to represent runs of various lengths. Leaf nodes in the upper tree levels thereby represent longer runs, and vice versa. The tree-based representation results in high compression ratios and enables efficient random access, which in turn allows for the fast intersection of bitmaps. Our experimental analysis with randomly generated bitmaps shows that our approach significantly improves over state-of-the-art compression techniques when bitmaps are dense and/or only barely clustered. Further, we evaluate our approach with real-world data sets, showing that our tree-encoded bitmaps can save up to one third of the space over existing techniques.

Authors with CRIS profile

Viktor Leis

Involved external institutions

Centrum Wiskunde & Informatica (CWI) NL Netherlands (NL) Technische Universität München (TUM) DE Germany (DE) Friedrich-Schiller-Universität Jena DE Germany (DE)

How to cite

APA:

Lang, H., Beischl, A., Leis, V., Boncz, P., Neumann, T., & Kemper, A. (2020). Tree-Encoded Bitmaps. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 937-967). Portland, OR, US: Association for Computing Machinery.

MLA:

Lang, Harald, et al. "Tree-Encoded Bitmaps." Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD 2020, Portland, OR Association for Computing Machinery, 2020. 937-967.

BibTeX: Download