Compressed bitmap indexes: beyond unions and intersections. (15th September 2014)

• Record Type: Journal Article
• Authors: Kaser, Owen; Lemire, Daniel
• Is Part Of: Software, practice & experience. Volume 46:Number 2(2016)
• Page Start: 167
• Page End: 198
• Publication Date: 2014-09-15
• Subjects: T‐overlap queries -- compressed bitmaps -- threshold functions -- symmetric functions -- Opt‐threshold queries; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2289
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Compressed bitmap indexes are used to speed up simple aggregate queries in databases. Indeed, set operations like intersections, unions and complements can be represented as logical operations (AND, OR and NOT) that are ideally suited for bitmaps. However, it is less obvious how to apply bitmaps to more advanced queries. For example, we might seek products in a store that meet some, but maybe not all, criteria. Such threshold queries generalize intersections and unions; they are often used in information‐retrieval and data‐mining applications. We introduce new algorithms that are sometimes three orders of magnitude faster than a naïve approach. Our work shows that bitmap indexes are more broadly applicable than is commonly believed. Copyright © 2014 John Wiley & Sons, Ltd.