Categorical range queries in large databases

Abstract

In this paper, we introduce the categorical (a.k.a. chromatic) range queries (CRQs) in the context of large, disk-resident data sets, motivated by the fact, that CRQs are conceptually simple and emerge often in DBMSs. On the basis of spatial data structures, and R-trees in particular, we propose a multi-tree index that follows the broad concept of augmenting nodes with additional information to accelerate queries. Augmentation is examined with respect to maximal/minimal points in subtrees, the properties of which are exploited by the proposed searching algorithm to effectively prune the search space. Detailed experimental results, with both real and synthetic data, illustrate the significant performance gains (up to an order of magnitude) due to the proposed method, compared to the regular range query (followed by the filtering w.r.t. categories) and to a naive R-tree augmentation method.