Making the Pyramid technique robust to query types and workloads

Abstract

The effectiveness of many existing high-dimensional indexing structures is limited to specific types of queries and workloads. For example, while the Pyramid technique and the iMinMax are efficient for window queries, the iDistance is superior for kNN queries. In this paper, we present a new structure, called the P +-tree, that supports both window queries and kNN queries under different workloads efficiently. In the P +-tree, a B +-tree is employed to index the data points as follows. The data space is partitioned into subspaces based on clustering, and points in each sub-space are mapped onto a single dimensional space using the Pyramid technique, and stored in the B +-tree. The crux of the scheme lies in the transformation of the data which has two crucial properties. First, it maps each subspace into a hypercube so that the Pyramid technique can be applied. Second, it shifts the cluster center to the top of the pyramid, which is the case that the Pyramid technique works very efficiently. We present window and kNN query processing algorithms for the P +-tree. Through an extensive performance study, we show that the P +-tree has considerable speedup over the Pyramid technique and the iMinMax for window queries and outperforms the iDistance for kNN queries.