Bitmap Techniques for Optimizing Decision Support Queries and Association Rule Algorithms

摘要

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 (pre-join-bitmap-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 Apr lor i 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 itemsetsfrom the datasets are the fast bit operations. The experimental results show Bit-AssocRule is 2 to 3 orders of magnitude faster than Apriori and AprioirHybrid 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.