On approximate nearest neighbors in non-Euclidean spaces

摘要: The nearest neighbor search (NNS) problem is the following: Given a set of n points P={p/sub 1/,...,p/sub n/} in some metric space X, preprocess P so as to efficiently answer queries which require finding point closest query q/spl isin/X. approximate (c-NNS) relaxation NNS allows return any within c times distance (called c-nearest neighbor). This major and growing importance variety applications. In this paper we give an algorithm for (4log/sub 1+/spl rho//log4d+3)-NNS l/sub /spl infin///sup d/ with O(dn/sup rho//logn) storage O(dlogn) time. particular yields first O(1)-NNS infin// subexponential storage. preprocessing time linear size data structure. can be also used (after simple modifications) output exact bounded plus number rho//log4d+3)-nearest neighbors point. Building on result, obtain approximation general class product metrics. Finally: show that c<3 c-NNS provably hard version indexing model introduced by Hellerstein et al. (1997).