We propose a new algorithm for fast approximate nearest neighbor search based on the properties of ordered vectors. Data vectors are classified based on the index and sign of their largest components, thereby partitioning the space in a number of cones centered in the origin. The query is itself classified, and the search starts from the selected cone and proceeds to neighboring ones. Overall, the proposed algorithm corresponds to locality sensitive hashing in the space of directions, with hashing based on the order of components. Thanks to the statistical features emerging through ordering, it deals very well with the challenging case of unstructured data, and is a valuable building block for more complex techniques dealing with structured data. Experiments on both simulated and real-world data prove the proposed algorithm to provide a state-of-the-art performance.
In Concomitant LSH @cite_0 , instead, a Voronoi partition of the space of directions is built based on a set of @math points taken at random on the unit sphere. Although originally proposed for cosine distance, it presents some similarities with ROSANNA, the use of directions and sorting, and can be easily adapted to deal with the Euclidean distance. However, to classify the query, @math distances must be computed at search-time, before inspecting the candidates, which is a severe overhead for large hashing tables. To reduce this burden, several variants are also proposed in @cite_0 which, however, tend to produce a worse partition of the space. Irrespective of the implementation details, the regular partition of the space of directions provided by ROSANNA can be expected to be more effective than the random partition used in Concomitant LSH. Moreover, in ROSANNA, the hashing requires only a vector sorting, with no distance computation. As for concomitants (related to order statistics) they are only used to carry out a theoretical analysis of performance, but are not considered in the algorithm.
@cite_0
2019336343
Locality Sensitive Hash functions are invaluable tools for approximate near neighbor problems in high dimensional spaces. In this work, we are focused on LSH schemes where the similarity metric is the cosine measure. The contribution of this work is a new class of locality sensitive hash functions for the cosine similarity measure based on the theory of concomitants, which arises in order statistics. Consider n i.i.d sample pairs, (X1; Y1); (X2; Y2); : : : ;(Xn; Yn) obtained from a bivariate distribution f(X, Y). Concomitant theory captures the relation between the order statistics of X and Y in the form of a rank distribution given by Prob(Rank(Yi)=j-Rank(Xi)=k). We exploit properties of the rank distribution towards developing a locality sensitive hash family that has excellent collision rate properties for the cosine measure. The computational cost of the basic algorithm is high for high hash lengths. We introduce several approximations based on the properties of concomitant order statistics and discrete transforms that perform almost as well, with significantly reduced computational cost. We demonstrate the practical applicability of our algorithms by using it for finding similar images in an image repository.