Abstract
Constrained Nearest Neighbor Queries
by: Hakan Ferhatosmanoglu, Ioana Stanoi, Divyakant Agrawal, Amr El Abbadi
Abstract:
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.
Keywords:
constraint, nearest neighbor, query processing, I/O optimality
Date:
January 2001
Document: 2001-01
