For decades, the success of the similarity search has been based on detailed quantifications of pairwise similarities of objects. Currently, the search features have become much more precise but also bulkier, and the similarity computations are more time-consuming. We show that nearly no precise similarity quantifications are needed to evaluate the k nearest neighbours ( k NN) queries that dominate real-life applications. Based on the well-known fact that a selection of the most similar alternative out of several options is a much easier task than deciding the absolute similarity scores, we propose the search based on an epistemologically simpler concept of relational similarity. Having arbitrary objects q , o 1 , o 2 from the search domain, the k NN search is solvable just by the ability to choose the more similar object to q out of o 1 , o 2 . To support the filtering efficiency, we also consider a neutral option, i.e., equal similarities of q , o 1 and q , o 2 . We formalise such concept and discuss its advantages with respect to similarity quantifications, namely the efficiency, robustness and scalability with respect to the dataset size. Our pioneering implementation of the relational similarity search for the Euclidean and Cosine spaces demonstrates robust filtering power and efficiency compared to several contemporary techniques.

This article addresses the problem of matching the most similar data objects to a given query object. We adopt a generic model of similarity that involves the domain of objects and metric distance functions only. We examine the case of a large dataset in a complex data space, which makes this problem inherently difficult. Many indexing and searching approaches have been proposed, but they have often failed to efficiently prune complex search spaces and access large portions of the dataset when evaluating queries. We propose an approach to enhancing the existing search techniques to significantly reduce the number of accessed data objects while preserving the quality of the search results. In particular, we extend each data object with its sketch , a short binary string in Hamming space. These sketches approximate the similarity relationships in the original search space, and we use them to filter out non-relevant objects not pruned by the original search technique. We provide a probabilistic model to tune the parameters of the sketch-based filtering separately for each query object. Experiments conducted with different similarity search techniques and real-life datasets demonstrate that the secondary filtering can speed-up similarity search several times.