Bitmap techniques for optimizing decision support queries and association rule algorithms

Abstract

In this paper, we discuss some new bitmap techniques for optimizing decision support queries and association rule algorithm. We first show how to use a new type of predefined bitmap join index (prejoin/spl I.bar/bitmap/spl I.bar/index) to efficiently execute complex decision support queries with multiple outer join operations involved and push the outer join operations from the data flow level to the bitmap level and achieve significant performance gain. Then we discuss a bitmap based association rule algorithm. Our bitmap based association rule algorithm Bit-AssocRule doesn't follow the generation-and-test strategy of a priori algorithm and adopts the divide-and-conquer strategy, thus avoids the time-consuming table scan to find and prune the item sets, all the operations of finding large item sets from the datasets are the fast bit operations. The experimental results show Bit-AssocRule is 2 to 3 orders of magnitude faster than a priori and a priori hybrid algorithms. Our results indicate that bitmap techniques can greatly improve the performance of decision support queries and association rule algorithm, and bitmap techniques are very promising for the decision support query optimization and data mining applications. © 2003 IEEE.