Filtering with relational similarity

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

MÍČ Vladimír ZEZULA Pavel

Year of publication 2024
Type Article in Periodical
Magazine / Source Information systems
MU Faculty or unit

Faculty of Informatics

Citation
web https://doi.org/10.1016/j.is.2024.102345
Doi http://dx.doi.org/10.1016/j.is.2024.102345
Keywords Searching and sorting; Metric space searching; Similarity Search; Metric filtering; Data dependent filtering
Description 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 (kNN) 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, o1, o2 from the search domain, the kNN search is solvable just by the ability to choose the more similar object to q out of o1, o2. To support the filtering efficiency, we also consider a neutral option, i.e., equal similarities of q, o1 and q, o2. 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info