towards optimal continuous nearest neighbor queries in spatial databases
One of the most important kind of queries in spatial data-bases to support location-based services (LBS) is the continuous nearest neighbors (CNN) query. Given a spatial data set of points of interest and a moving query point q , the CNN query partitions q into a set of adjacent disjoint intervals associated with their nearest points of interest. Existing solutions to this problem are known to be sub-optimal in terms of disk accesses. In this paper, we present an algorithm to compute the CNN query that is I/O optimal. With an experimental evaluation, we show that not only the number of disk accesses is reduced with the optimal algorithm, but also the CPU performance is improved, in some cases.
continuous nearest neighbors spatial databases location based services