What is it about?
Bitmap indexes are widely used in database systems. The Tree-Encoded Bitmap (TEB) is a tree-based bitmap compression scheme that maps runs in a bitmap to leaf nodes in a binary tree. Currently, TEBs perform updates using an auxiliary differential data structure. However, consulting this additional data structure at every read introduces both memory and read overheads. To mitigate the shortcomings of differential updates, we propose algorithms to update TEBs in place.
Featured Image
Photo by Alexander Sinn on Unsplash
Why is it important?
Our experiments with synthetic data show that our in-place algorithms can perform updates in Tree-Encoded Bitmaps significantly faster than the original differential approach.
Perspectives
This work addresses the problem of the update efficiency in Tree-Encoded Bitmaps. Thereby, it is a significant enrichment of the original approach that increases the applicability of Tree-Encoded Bitmaps. Furthermore, this short paper was the outcome of a bachelor thesis at the Technical University of Berlin. It was great to see that even without research experience, the right mindset and dedication can lead to interesting findings.
Dr. Eleni Tzirita Zacharatou
Universitat Potsdam
Read the Original
This page is a summary of: In-Place Updates in Tree-Encoded Bitmaps, July 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3538712.3538745.
You can read the full text:
Contributors
The following have contributed to this page
