Binary Sketches for Secondary Filtering

J 2019

Binary Sketches for Secondary Filtering

MÍČ, Vladimír, David NOVÁK a Pavel ZEZULA

Základní údaje

Originální název

Binary Sketches for Secondary Filtering

Autoři

MÍČ, Vladimír (203 Česká republika, domácí), David NOVÁK (203 Česká republika, domácí) a Pavel ZEZULA (203 Česká republika, garant, domácí)

Vydání

ACM Transactions on Information Systems, New York, ACM Press, 2019, 1046-8188

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 2.889

Kód RIV

RIV/00216224:14330/19:00107167

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1145/3231936

UT WoS

000457519000001

Klíčová slova anglicky

Top-k retrieval in databases;Retrieval efficiency;Retrieval effectiveness;Similarity measures;

Štítky

best, DISA

Změněno: 13. 4. 2020 23:22, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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ávaznosti

GBP103/12/G084, projekt VaV

Název: Centrum pro multi-modální interpretaci dat velkého rozsahu

Investor: Grantová agentura ČR, Centrum pro multi-modální interpretaci dat velkého rozsahu

Citovat

MÍČ, Vladimír, David NOVÁK a Pavel ZEZULA. Binary Sketches for Secondary Filtering. ACM Transactions on Information Systems. New York: ACM Press, 2019, roč. 37, č. 1, s. "1:1"-"1:28", 28 s. ISSN 1046-8188. Dostupné z: https://dx.doi.org/10.1145/3231936.

@article{1421494,
   author = {Míč, Vladimír and Novák, David and Zezula, Pavel},
   article_location = {New York},
   article_number = {1},
   doi = {http://dx.doi.org/10.1145/3231936},
   keywords = {Top-k retrieval in databases;Retrieval efficiency;Retrieval effectiveness;Similarity measures;},
   language = {eng},
   issn = {1046-8188},
   journal = {ACM Transactions on Information Systems},
   title = {Binary Sketches for Secondary Filtering},
   url = {http://dx.doi.org/10.1145/3231936},
   volume = {37},
   year = {2019}
}

TY  - JOUR
ID  - 1421494
AU  - Míč, Vladimír - Novák, David - Zezula, Pavel
PY  - 2019
TI  - Binary Sketches for Secondary Filtering
JF  - ACM Transactions on Information Systems
VL  - 37
IS  - 1
SP  - "1:1"-"1:28"
EP  - "1:1"-"1:28"
PB  - ACM Press
SN  - 10468188
KW  - Top-k retrieval in databases;Retrieval efficiency;Retrieval effectiveness;Similarity measures;
UR  - http://dx.doi.org/10.1145/3231936
L2  - http://dx.doi.org/10.1145/3231936
N2  - 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, David NOVÁK a Pavel ZEZULA. Binary Sketches for Secondary Filtering. \textit{ACM Transactions on Information Systems}. New York: ACM Press, 2019, roč.~37, č.~1, s.~''1:1''-''1:28'', 28 s. ISSN~1046-8188. Dostupné z: https://dx.doi.org/10.1145/3231936.

Podrobný výpis o publikaci