Multi-Dimensional Bitmap Indices for Optimising Data Access within Object Oriented Databases at CERN

Efficient query processing in high-dimensional search spaces is an important requirement for many analysis tools. In the literature on index data structures one can find a wide range of methods for optimising database access. In particular, bitmap indices have recently gained substantial popularity in data warehouse applications with large amounts of read mostly data. Bitmap indices are implemented in various commercial database products and are used for querying typical business applications. However, scientific data that is mostly characterised by non-discrete attribute values cannot be queried efficiently by the techniques currently supported. In this thesis we propose a novel access method based on bitmap indices that efficiently handles multi-dimensional queries against typical scientific data. The algorithm is called GenericRangeEval and is an extension of a bitmap index for discrete attribute values. By means of a cost model we study the performance of queries with various selectivities against uniformly distributed and independent data values. Experimentally we verify our analytical findings and demonstrate that for certain query selectivities the proposed bitmap index shows a significant performance improvement over traditional access methods. Apart from evaluating bitmap indices for synthetic data, we also evaluate this access method based on real data taken from High Energy Physics and Astronomy applications. We thus demonstrate that our approach is not only of theoretical value but also improves the performance of practical applications. In this sense this thesis is a successful proof that multi-dimensional access methods can significantly speed up typical high-dimensional end-user analysis.