Efficient processing of KNN and skyjoin queries

Abstract

High-dimensional nearest neighbor search is a very important operation in many emerging database applications. We proposed two new indexing techniques, the Diagonal Ordering method and the SA-tree. Diagonal Ordering is based on data clustering and sorting each cluster along the diagonal direction. The KNN search is then performed as a sequence of one-dimensional range searches. The SA-tree utilizes the characteristics of each cluster to adaptively compress feature vectors into bit-strings. We also developed an efficient KNN search algorithm using MinMax Pruning or Partial MinDist Pruning method. Besides high-dimensional KNN query, we also extend the skyline operation to the Skyjoin query, which finds the skyline of each data point in the database. We proposed an efficient algorithm to speed up the processing of the Skyjoin query by ordering feature vectors lexicographically and computing the grid skyline first. We conducted extensive experiments to evaluate the effectiveness of the proposed techniques.