Constrained Nearest Neighbor Queries

In this paper we introduce the notion of {\\em constrained nearestneighbor queries (CNN)} and propose a series of methods to answerthem. This class of queries can be thought of as nearest neighbor queries with range constraints. Although both nearest neighbor andrange queries have been analyzed extensively in previous literature,the implications of constrained nearest neighbor queries have not beendiscussed. Due to their versatility, CNN queries are suitable to awide range of applications from GIS systems to reverse nearestneighbor queries and multimedia applications. We develop methods foranswering CNN queries with different properties and advantages. Weprove the optimality (with respect to I/O cost) of one of thetechniques proposed in this paper. The superiority of the proposedtechnique is shown by a performance analysis.