This paper addresses the problem of finding the nearest neighbor (or one of the R-nearest neighbors) of a query object q in a database of n objects. In contrast with most existing approaches, we can only access the "hidden" space in which the objects live through a similarity oracle. The oracle, given two reference objects and a query object, returns the reference object closest to the query object. The oracle attempts to model the behavior of human users, capable of making statements about similarity, but not of assigning meaningful numerical values to distances between objects. Using such an oracle, the best we can hope for is to obtain, for every object u in the database, a sorted list of the other objects according to their distance to u. We call the position of object v in this list the rank of v with respect to u. The difficulty of searching using such an oracle depends on the non-homogeneities of the underlying space. We use two different characterizations of the underlying space to capture this property. The first one, rank distortion, relates pairwise ranks to the average difference in ranks w.r.t. other objects (a more precise definition is given in Section II). The second one, the combinatorial framework (a notion from [1], [2]), defines approximate triangle inequalities on ranks (a more precise definition is given in Section II). Roughly speaking, it defines a multiplicative factor D by which the triangle inequality on ranks can be violated. Utilizing the insights from these ideas, we develop a hierarchical search algorithm that builds a data structure, which allows us to retrieve the nearest neighbor with high probability in O(D 3 log 2 n log log n D 3 ) questions. The learning requires asking O(nD 3 log 2 n log log n D 3 ) questions in total and we need to store O(n log 2 n/ log(2D)) bits in total. We also provide an approximate nearest neighbor search algorithm. Finally, we show a lower bound of Ω(D log n D 2 + D 2 ) average number of questions in the search phase for randomized algorithms when the answers to all possible questions in the learning phase are given. We also introduce rank-sensitive hash functions which gives same hash value for "similar" objects based on the rank-value of the objects obtained from the similarity oracle. As one application of RSH, we demonstrate that, we can retrieve one of the (1 + ǫ)r-nearest neighbor of a query point in n θ evaluations of the hash function, where θ only depends on ǫ and the rank distortion.
In REF , we prove a lower bound which demonstrates that our schemes are (almost) efficient.
Approximate Nearest Neighbor Search through Comparisons
ArXiv
ArXiv
Computer Science