Space efficient bitmap indexing

There exists a well known tradeo between the performance of queries on a collection of tables and the space devoted to the indices indexing the attributes in these tables.We introduce additional parameters in the analysis of this tradeo namely the query and data distribution on the attribute instance.We propose a technique to index large cardinality attributes using bitmaps taking into account both the query and data distribution of the attribute instance, as well as the space requirements of the bitmaps.We formulate this problem in mathematical terms and we propose optimal algorithms for its solution.We also consider variants of the problem in which bitmap compression is taken into account.Detailed experimental results obtained from the application of our techniques in realistic databases, highlight t h e bene ts of the proposed solution.