Similarity Search with the Distance Density Model

D 2022

Similarity Search with the Distance Density Model

KŘENKOVÁ, Markéta, Vladimír MÍČ and Pavel ZEZULA

Basic information

Original name

Similarity Search with the Distance Density Model

Authors

KŘENKOVÁ, Markéta (203 Czech Republic, belonging to the institution), Vladimír MÍČ (203 Czech Republic, belonging to the institution) and Pavel ZEZULA (203 Czech Republic, guarantor, belonging to the institution)

Edition

Cham, Similarity Search and Applications: 15th International Conference, SISAP 2022, Bologna, Italy, October 5 - October 7, 2020, Proceedings, p. 118-132, 15 pp. 2022

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/22:00127335

Organization unit

Faculty of Informatics

ISBN

978-3-031-17848-1

ISSN

DOI

http://dx.doi.org/10.1007/978-3-031-17849-8_10

UT WoS

000874756300010

Keywords in English

Metric space similarity model;Perceived similarity;Data-dependent similarity;Distance density model;Effective and efficient similarity search

Abstract

V originále

The metric space model of similarity has become a standard formal paradigm of generic similarity search engine implementations. However, the constraints of identity and symmetry prevent from expressing the subjectivity and dependence on the context perceived by humans. In this paper, we study the suitability of the Distance density model of similarity for searching. First, we use the Local Outlier Factor (LOF) to estimate a data density in search collections and evaluate plenty of queries using the standard geometric model and its extension respecting the densities. We let 200 people assess the search effectiveness of the two alternatives using the web interface. Encouraged by the positive effects of the Distance density model, we propose an alternative way to estimate the data densities to avoid the quadratic LOF computation complexity with respect to the dataset size. The sketches with unbalanced bits are clarified to be in correlation with LOFs, which opens a possibility for an efficient implementation of large-scale similarity search systems based on the Distance density model.

Links

EF16_019/0000822, research and development project

Name: Centrum excelence pro kyberkriminalitu, kyberbezpečnost a ochranu kritických informačních infrastruktur

Citovat

KŘENKOVÁ, Markéta, Vladimír MÍČ and Pavel ZEZULA. Similarity Search with the Distance Density Model. In Tomáš Skopal, Fabrizio Falchi, Jakub Lokoč, Maria Luisa Sapino, Ilaria Bartolini, Marco Patella. Similarity Search and Applications: 15th International Conference, SISAP 2022, Bologna, Italy, October 5 - October 7, 2020, Proceedings. Cham: Springer, 2022, p. 118-132. ISBN 978-3-031-17848-1. Available from: https://dx.doi.org/10.1007/978-3-031-17849-8_10.

@inproceedings{2236339,
   author = {Křenková, Markéta and Míč, Vladimír and Zezula, Pavel},
   address = {Cham},
   booktitle = {Similarity Search and Applications: 15th International Conference, SISAP 2022, Bologna, Italy, October 5 - October 7, 2020, Proceedings},
   doi = {http://dx.doi.org/10.1007/978-3-031-17849-8_10},
   editor = {Tomáš Skopal, Fabrizio Falchi, Jakub Lokoč, Maria Luisa Sapino, Ilaria Bartolini, Marco Patella},
   keywords = {Metric space similarity model;Perceived similarity;Data-dependent similarity;Distance density model;Effective and efficient similarity search},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-031-17848-1},
   pages = {118-132},
   publisher = {Springer},
   title = {Similarity Search with the Distance Density Model},
   url = {https://link.springer.com/chapter/10.1007/978-3-031-17849-8_10},
   year = {2022}
}

TY  - JOUR
ID  - 2236339
AU  - Křenková, Markéta - Míč, Vladimír - Zezula, Pavel
PY  - 2022
TI  - Similarity Search with the Distance Density Model
PB  - Springer
CY  - Cham
SN  - 9783031178481
KW  - Metric space similarity model;Perceived similarity;Data-dependent similarity;Distance density model;Effective and efficient similarity search
UR  - https://link.springer.com/chapter/10.1007/978-3-031-17849-8_10
N2  - The metric space model of similarity has become a standard formal paradigm of generic similarity search engine implementations. However, the constraints of identity and symmetry prevent from expressing the subjectivity and dependence on the context perceived by humans. In this paper, we study the suitability of the Distance density model of similarity for searching. First, we use the Local Outlier Factor (LOF) to estimate a data density in search collections and evaluate plenty of queries using the standard geometric model and its extension respecting the densities. We let 200 people assess the search effectiveness of the two alternatives using the web interface. Encouraged by the positive effects of the Distance density model, we propose an alternative way to estimate the data densities to avoid the quadratic LOF computation complexity with respect to the dataset size. The sketches with unbalanced bits are clarified to be in correlation with LOFs, which opens a possibility for an efficient implementation of large-scale similarity search systems based on the Distance density model.
ER  -

KŘENKOVÁ, Markéta, Vladimír MÍČ and Pavel ZEZULA. Similarity Search with the Distance Density Model. In Tomáš Skopal, Fabrizio Falchi, Jakub Lokoč, Maria Luisa Sapino, Ilaria Bartolini, Marco Patella. \textit{Similarity Search and Applications: 15th International Conference, SISAP 2022, Bologna, Italy, October 5 - October 7, 2020, Proceedings}. Cham: Springer, 2022, p.~118-132. ISBN~978-3-031-17848-1. Available from: https://dx.doi.org/10.1007/978-3-031-17849-8\_{}10.

Detailed Information on Publication Record