Partially Specified Nearest Neighbor Search
Tomáš Hrúz, Schöngens, Marcel · 2012
We study the Partial Nearest Neighbor Problem that consists in pre-processing n points D from d-dimensional metric space such that the fol-lowing query can be answered efficiently: Given a query vector Q ∈ Rd and an axes-aligned query subspace represented by S ∈ {0, 1}d, report a point P ∈ D with dS(Q,P) ≤ dS(Q,P ′) for all P ′ ∈ D, where dS(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 bioinformatics, im-age recognition, etc., however, due to exponentially many subspaces, each changing distances significantly, the problem has a considerable complex-ity. We present the first exact algorithms for `2- and `∞-metrics with linear space and sub-linear worst-case query time, we give a simple approx-imation algorithm, and show experimentally that our approach performs well on real world data. 1