Filtering with relational similarity

Vladimir Mic; Pavel Zezula

doi:10.1016/j.is.2024.102345

Filtering with relational similarity

^*Corresponding author af dette arbejde

Institut for Datalogi

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

Abstract

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,o₁,o₂ from the search domain, the kNN search is solvable just by the ability to choose the more similar object to q out of o₁,o₂. To support the filtering efficiency, we also consider a neutral option, i.e., equal similarities of q,o₁ and q,o₂. 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.

Originalsprog	Engelsk
Artikelnummer	102345
Tidsskrift	Information Systems
Vol/bind	122
ISSN	0306-4379
DOI	https://doi.org/10.1016/j.is.2024.102345
Status	Udgivet - maj 2024

Adgang til dokumentet

10.1016/j.is.2024.102345Licens: CC BY

Citationsformater

@article{3604781c4a224fbd808f79a7d7d40010,

title = "Filtering with relational similarity",

abstract = "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.",

keywords = "Data dependent filtering, Metric filtering, Metric space searching, Searching and sorting, Similarity Search",

author = "Vladimir Mic and Pavel Zezula",

note = "Publisher Copyright: {\textcopyright} 2024 The Authors",

year = "2024",

month = may,

doi = "10.1016/j.is.2024.102345",

language = "English",

volume = "122",

journal = "Information Systems",

issn = "0306-4379",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - Filtering with relational similarity

AU - Mic, Vladimir

AU - Zezula, Pavel

PY - 2024/5

Y1 - 2024/5

N2 - 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.

AB - 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.

KW - Data dependent filtering

KW - Metric filtering

KW - Metric space searching

KW - Searching and sorting

KW - Similarity Search

U2 - 10.1016/j.is.2024.102345

DO - 10.1016/j.is.2024.102345

M3 - Journal article

AN - SCOPUS:85184992306

SN - 0306-4379

VL - 122

JO - Information Systems

JF - Information Systems

M1 - 102345

ER -

Filtering with relational similarity

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater