Partially Specified Nearest Neighbor Search

摘要

We study the Partial Nearest Neighbor Problem that consists in preprocessing n points D from d-dimensional metric space such that the following query can be answered efficiently: Given a query vector Q ∈ R~d and an axes-aligned query subspace represented by S ∈ {0, l}~d, report a point P ∈ D with d_s(Q,P) ≤ d_S(Q,P') for all P' ∈ D, where d_S(Q, P) is the distance between Q and P in the subspace S. This problem is related to similarity search between feature vectors w.r.t. a subset of features. Thus, the problem is of great practical importance in bioin-formatics, image recognition, etc., however, due to exponentially many subspaces, each changing distances significantly, the problem has a considerable complexity. We present the first exact algorithms for e_2- and e_∞-metrics with linear space and sub-linear worst-case query time. We also give a simple approximation algorithm, and show experimentally that our approach performs well on real world data.