A Linear Programming Approach for Bitmap Join Indexes Selection in Data Warehouses

Data warehousing is the crucial part of business intelligence applications. The data warehouse physical design is a hard task due to a large number of possible choices involved. The bitmap join indexes selection problem is crucial in the data warehouse physical design. All proposed approaches to solve the bitmap join indexes selection problem are based on statistics such as data mining or meta-heuristics such as genetic algorithm and particle swarm optimization. In the present work, we propose a new approach based on mixed-integer linear programming for solving the bitmap join indexes selection problem. Several experiments are performed to demonstrate the effectiveness of the proposed approach and the results are compared to the well known approaches that are best so far: the data mining, the genetic algorithm and particle swarm optimization based approaches. The mixed-integer linear programming is found to be faster and more effective than the genetic algorithm, particle swarm optimization and data mining approaches for solving the bitmap join indexes selection problem.