In this PhD dissertation, we propose database solutions to support a set of queries for large scale, multidimensional and dynamic databases. In particular, we discuss two main topics: Angular Similarity Queries and Bitmap Indexes.
We start with presenting the notion of Angular Similarity that previously lack the database support and discuss our index structures suited for that kind of queries. These proposed compression-based methods enable the angular queries to run faster than the current practice. Cosine, correlation coefficient, and inner product are examples of distance measures utilized as angular similarities. These measures find applications in astrophysics, aviation, graphics, text documents, time series, etc.
Then we focus on Bitmap Indexes, which are widely used in data warehouses, scientific applications and which are also implemented by commercial database products such as Oracle. We investigate the Bitmap Indexes from three different perspectives. First, we present our approximate encoding scheme for these indexes.
Second, we investigate the data ordering techniques and study their effectiveness on the compression ratios of bitmap indexes. We provide theoretical foundations and a performance analysis on two popular ordering techniques, namely lexicographical ordering and Gray code ordering. Our analysis does not only focus on bitmaps, but from a wider perspective, we cover these approaches in the context of Boolean matrices and binary data.
Third, we explore the dynamic nature of real data sets. By exploiting the append-only trend in data warehouses and scientific data sets, we propose a dynamic organization technique for bitmap indexes. For static data sets, compression is shown to be greatly improved by data ordering techniques. However, these data reorganization methods are not applicable to dynamic and very large data sets because of their significant overhead. Our dynamic data structure and the algorithm for organizing the bitmap indexes provide better compression and query processing performance. Our scheme enforces a compression rate close to the optimum for a target ordering of the data which results in fast query response time.