Research Seminar by Professor Nikos MAMOULIS | A secondary partitioning technique for indexing multidimensional ranges

Most database systems focus on the effective management of scalars or vectors, i.e., (multidimensional) points. Still, in many applications, there is a need for indexing (multidimensional) ranges, i.e., intervals or multidimensional boxes. This problem is also a classic one and it has been supported by effective access methods, such as the interval tree and the R-tree. Recently, given the fact that main memories have become bigger and cheaper, there is an increasing interest for efficient main-memory indices, where the objective is to minimize the computational cost of queries instead of the I/O cost. Based on this, we revisit the design and implementation of indexing (multidimensional) ranges. Driven by the fact that the most efficient methods for points are those which define and use disjoint space partitions, we focus on adaptations of such methods for ranges. An inherent problem of indexing ranges using disjoint partitions is that a data unit may have to be assigned to multiple partitions, which causes data redundancy and duplicate results in queries. We propose a simple but effective secondary data partitioning, which (i) reduces redundancy, (ii) avoids the generation of duplicate results, and (iii) minimizes the number of necessary comparisons. For 1D intervals, we propose HINT, an efficient hierarchical index that has controlled space requirements and includes storage optimization techniques for the effective handling of data sparsity and skewness. Our indices target range overlap queries, which are a basic component of many search and analysis tasks. Experimental results on real and synthetic data show that our approaches are typically one order of magnitude faster than the state-of-the-art indexing methods.