Group Testing for Accurate and Efficient Range-Based Near Neighbor
  Search : An Adaptive Binary Splitting Approach
Kashish Mittal Harsh Shah Ajit Rajwade
This work presents an adaptive group testing framework for the range-based
high dimensional near neighbor search problem. The proposed method detects
high-similarity vectors from an extensive collection of high dimensional
vectors, where each vector represents an image descriptor. Our method
efficiently marks each item in the collection as neighbor or non-neighbor on
the basis of a cosine distance threshold without exhaustive search. Like other
methods in the domain of large scale retrieval, our approach exploits the
assumption that most of the items in the collection are unrelated to the query.
Unlike other methods, it does not assume a large difference between the cosine
similarity of the query vector with the least related neighbor and that with
the least unrelated non-neighbor. Following the procedure of binary splitting,
a multi-stage adaptive group testing algorithm, we split the set of items to be
searched into half at each step, and perform dot product tests on smaller and
smaller subsets, many of which we are able to prune away. We experimentally
show that our method achieves a speed-up over exhaustive search by a factor of
more than ten with an accuracy same as that of exhaustive search, on a variety
of large datasets. We present a theoretical analysis of the expected number of
distance computations per query and the probability that a pool with a certain
number of members will be pruned. In this way, our method exploits very useful
and practical distributional properties unlike other methods. In our method,
all required data structures are created purely offline. Moreover, our method
does not impose any strong assumptions on the number of true near neighbors, is
adaptible to streaming settings where new vectors are dynamically added to the
database, and does not require any parameter tuning.