Binary Sketches for Secondary Filtering

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00107167" target="_blank" >RIV/00216224:14330/19:00107167 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1145/3231936" target="_blank" >http://dx.doi.org/10.1145/3231936</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3231936" target="_blank" >10.1145/3231936</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Binary Sketches for Secondary Filtering

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Binary Sketches for Secondary Filtering

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

<a href="/cs/project/GBP103%2F12%2FG084" target="_blank" >GBP103/12/G084: Centrum pro multi-modální interpretaci dat velkého rozsahu</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Information Systems

ISSN

1046-8188

e-ISSN

1558-2868

Svazek periodika

37

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

28

Strana od-do

„1:1“-„1:28“

Kód UT WoS článku

000457519000001

EID výsledku v databázi Scopus

—