Indexes for nearest neighbor queries and related problems

The goal of this dissertation is to design index structures for the nearest neighbor query and related problems in databases of multi-dimensional objects. The main idea is to precompute the solution space and incorporate it into the index structure. Our first attempt is to compute the Voronoi diagram and embed it in an R-tree. We call such a tree the VorR-tree. Our results on nearest neighbor searches with the VorR-tree show that this is a promising direction.; The simplicity of one dimensional data makes it possible to design the B-tree that can achieve a low search cost, log n. In higher dimensional space, the situation is far more complicated. In chapter 4 we study the properties of higher dimensional index and give a set of sufficient conditions for an index to achieve log n on search cost. We further design the ANN-tree to approximate such an ideal index.; The Rdnn-tree is designed for nearest neighbor (NN) as well as reverse nearest neighbor (RNN) searches. It outperforms the existing solutions significantly both on building cost and search cost. One Rdnn-tree that supports both NN and RNN searches effectively makes it possible to perform batch NN and combined NN-RNN searches.; We also study various join queries with the bichromatic version of the Rdnn-tree, the bRdnn-tree; such queries include the k-Closest Pair and the k-Closest NN Pair problems. Finally, we introduce the RNN search into publish/subscribe systems using bRdnn-tree and propose to deliver only the most relavent information to each subscriber.