Optimizing bitmap index encoding for high performance queries. (7th September 2020)

• Record Type: Journal Article
• Authors: Yildiz, Beytullah
• Other Names: Oh Sangyoon guestEditor.; de Camargo Raphael Y. guestEditor.; Marozzo Fabrizio guestEditor.; Martins Wellington guestEditor.; Kołodziej Joanna guestEditor.; Jaatun Martin Gilje guestEditor.
• Is Part Of: Concurrency and computation. Volume 33:Number 18(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-09-07
• Subjects: bitmap encoding -- bitmap index -- data retrieval -- multicore -- parallel query -- query optimization; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5943
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Many sources such as historical archives, sensor readings, health systems, and machine records produce ever‐increasing but often unchanging data. These accumulating data create a need for faster processing. Bitmap index, which can take advantage of multi‐core and multiprocessor systems, is designed to process data that increase over time but do not change frequently. It has a well‐known advantage, especially in queries on data with low cardinality. However, bitmap index can handle high cardinality data efficiently because it can use its own compression algorithm. Bitmap index has many encoding schemes that affect query processing time. In this study, we developed an algorithm that improves query performance by using optimal encoding among bitmap encodings. With this optimization algorithm, we witnessed up to 40% performance increase in queries made with bitmap indexes created with different encodings. Furthermore, in comparison with a commonly used relational database, we found significant improvements in the number of query operations per second performed on optimized encoded bitmap indexes generated by the introduced algorithm.