Digital Symposium Collection 2000

An Efficient Bitmap Encoding Scheme for Selection Queries Chee Yong Chan and Yannis E. Ioannidis   View Paper (PDF)   Return to Selectivities Abstract Bitmap indexes are useful in processing complex queries in decision support systems, and they have been implemented in several commercial database systems. A key design parameter for bitmap indexes is the encoding scheme, which determines the bits that are set to 1 in each bitmap in an index. While the relative performance of the two existing bitmap encoding schemes for simple selection queries of the form "v1 <= A <= v2" is known (specifically, one of the encoding schemes is better for processing equality queries; i.e., v1 = v2, while the other is better for processing range queries; i.e., v1 < v2), it remains an open question whether these two encoding schemes are indeed optimal for their respective query classes in the sense that there is no other encoding scheme with better space-time tradeoff. In this paper, we establish a number of optimality results for the existing encoding schemes; in particular, we prove that neither of the two known schemes is optimal for the class of two-sided range queries. We also propose a new encoding scheme and prove that it is optimal for that class. Finally, we present an experimental study comparing the performance of the new encoding scheme with that of the existing ones as well as four hybrid encoding schemes for both simple selection queries and the more general class of membership queries of the form " A E {v1; v2; ...; vk}". These results demonstrate that the new encoding scheme has an overall better space-time performance than existing schemes. References Note: References link to DBLP on the Web. [Ant93] ... [CI98a] ... [CI98b] Chee Yong Chan , Yannis E. Ioannidis : Bitmap Index Design and Evaluation. SIGMOD Conference 1998 : 355-366 [Ede95] ... [Inf] ... [Jak97] ... [OG95] Patrick E. O'Neil , Goetz Graefe : Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3) : 8-11(1995) [O'N87] Patrick E. O'Neil : Model 204 Architecture and Performance. HPTS 1987 : 40-59 [O'N97] ... [OQ97] Patrick E. O'Neil , Dallan Quass : Improved Query Performance with Variant Indexes. SIGMOD Conference 1997 : 38-49 [Syb97] ... [WB98] Ming-Chuan Wu , Alejandro P. Buchmann : Encoded Bitmap Indexing for Data Warehouses. ICDE 1998 : 220-230 [Win99] ... [WLO+85] Harry K. T. Wong , Hsiu-Fen Liu , Frank Olken , Doron Rotem , Linda Wong : Bit Transposed Files. VLDB 1985 : 448-457 [WLO+86] Harry K. T. Wong , Jianzhong Li , Frank Olken , Doron Rotem , Linda Wong : Bit Transposition for Very Large Scientific and Statistical Databases. Algorithmica 1(3) : 289-309(1986) BIBTEX @inproceedings{DBLP:conf/sigmod/ChanI99,   author    = {Chee Yong Chan and                 Yannis E. Ioannidis},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {An Efficient Bitmap Encoding Scheme for Selection Queries},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {215-226},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM