Binary Sketches for Secondary Filtering

p 2020

Binary Sketches for Secondary Filtering

MÍČ, Vladimír

Basic information

Original name

Binary Sketches for Secondary Filtering

Authors

MÍČ, Vladimír (203 Czech Republic, guarantor, belonging to the institution)

Edition

43rd International ACM SIGIR Conference on Research and Development in Information Retrieval July 25-30, 2020 (Xi'an, China), 2020

Other information

Language

English

Type of outcome

Vyžádané přednášky

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

References:

Conference Program

RIV identification code

RIV/00216224:14330/20:00116742

Organization unit

Faculty of Informatics

Keywords in English

Similarity Search; Metric Space Transformation; Hamming Space; Similarity Filtering

Abstract

V originále

Invited talk and discussion (30 minutes, together) at the ACM SIGIR conference (A* rank) about the journal article "Binary Sketches for Secondary Filtering" published in the ACM TOIS journal (2018). The abstract of the article and the presentation: "This paper 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 so as 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."

Links

EF16_019/0000822, research and development project

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

Citovat

MÍČ, Vladimír. Binary Sketches for Secondary Filtering. In 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval July 25-30, 2020 (Xi'an, China). 2020.

@misc{1687336,
   author = {Míč, Vladimír},
   booktitle = {43rd International ACM SIGIR Conference on Research and Development in Information Retrieval July 25-30, 2020 (Xi'an, China)},
   keywords = {Similarity Search; Metric Space Transformation; Hamming Space; Similarity Filtering},
   language = {eng},
   title = {Binary Sketches for Secondary Filtering},
   url = {https://sigir.org/sigir2020/assets/files/SIGIR20.pdf},
   year = {2020}
}

TY  - SLIDE
ID  - 1687336
AU  - Míč, Vladimír
PY  - 2020
TI  - Binary Sketches for Secondary Filtering
KW  - Similarity Search
KW  - Metric Space Transformation
KW  - Hamming Space
KW  - Similarity Filtering
UR  - https://sigir.org/sigir2020/assets/files/SIGIR20.pdf
N2  - Invited talk and discussion (30 minutes, together) at the ACM SIGIR conference (A* rank) about the journal article "Binary Sketches for Secondary Filtering" published in the ACM TOIS journal (2018). The abstract of the article and the presentation: "This paper 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 so as 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."
ER  -

MÍČ, Vladimír. Binary Sketches for Secondary Filtering. In \textit{43rd International ACM SIGIR Conference on Research and Development in Information Retrieval July 25-30, 2020 (Xi'an, China)}. 2020.

Detailed Information on Publication Record