Towards optimal continuous nearest neighbor queries in spatial databases
Victor Teixeira de Almeida · 2006
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.