Designing Sketches for Similarity Filtering

D 2016

Designing Sketches for Similarity Filtering

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

Základní údaje

Originální název

Designing Sketches for Similarity Filtering

Autoři

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

Vydání

USA, 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), od s. 655-662, 8 s. 2016

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14330/16:00088645

Organizační jednotka

Fakulta informatiky

ISBN

978-1-5090-5472-5

ISSN

DOI

https://doi.org/10.1109/ICDMW.2016.0098

UT WoS

000401906900090

EID Scopus

2-s2.0-85015172117

Klíčová slova anglicky

Algorithm;Similarity search;Similarity filtering;Bit strings;Sketches;Hamming distance

Štítky

DISA

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 14. 5. 2020 15:31, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Abstract: The amounts of currently produced data emphasize the importance of techniques for efficient data processing. Searching big data collections according to similarity of data well corresponds to human perception. This paper is focused on similarity search using the concept of sketches – a compact bit string representations of data objects compared by Hamming distance, which can be used for filtering big datasets. The object-to-sketch transformation is a form of the dimensionality reduction and thus there are two basic contradictory requirements: (1) The length of the sketches should be small for efficient manipulation, but (2) longer sketches retain more information about the data objects. First, we study various sketching methods for data modeled by metric space and we analyse their quality. Specifically, we study importance of several sketch properties for similarity search and we propose a high quality sketching technique. Further, we focus on the length of sketches by studying mutual influence of sketch properties such as correlation of their bits and the intrinsic dimensionality of a set of sketches. The outcome is an equation that allows us to estimate a suitable length of sketches for an arbitrary given dataset. Finally, we empirically verify proposed approach on two real-life datasets.

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. Designing Sketches for Similarity Filtering. In Carlotta Domeniconi, Francesco Gullo, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu. 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW). USA: IEEE, 2016, s. 655-662. ISBN 978-1-5090-5472-5. Dostupné z: https://doi.org/10.1109/ICDMW.2016.0098.

@inproceedings{1371735,
   author = {Míč, Vladimír and Novák, David and Zezula, Pavel},
   address = {USA},
   booktitle = {2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW)},
   doi = {https://doi.org/10.1109/ICDMW.2016.0098},
   editor = {Carlotta Domeniconi, Francesco Gullo, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu},
   keywords = {Algorithm;Similarity search;Similarity filtering;Bit strings;Sketches;Hamming distance},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {USA},
   isbn = {978-1-5090-5472-5},
   pages = {655-662},
   publisher = {IEEE},
   title = {Designing Sketches for Similarity Filtering},
   url = {http://ieeexplore.ieee.org/document/7836729/},
   year = {2016}
}

TY  - CONF
ID  - 1371735
AU  - Míč, Vladimír - Novák, David - Zezula, Pavel
PY  - 2016
TI  - Designing Sketches for Similarity Filtering
PB  - IEEE
CY  - USA
SN  - 9781509054725
KW  - Algorithm;Similarity search;Similarity filtering;Bit strings;Sketches;Hamming distance
UR  - http://ieeexplore.ieee.org/document/7836729/
N2  - Abstract: The amounts of currently produced data emphasize the importance of techniques for efficient data processing. Searching big data collections according to similarity of data well corresponds to human perception. This paper is focused on similarity search using the concept of sketches – a compact bit string representations of data objects compared by Hamming distance, which can be used for filtering big datasets. The object-to-sketch transformation is a form of the dimensionality reduction and thus there are two basic contradictory requirements: (1) The length of the sketches should be small for efficient manipulation, but (2) longer sketches retain more information about the data objects. First, we study various sketching methods for data modeled by metric space and we analyse their quality. Specifically, we study importance of several sketch properties for similarity search and we propose a high quality sketching technique. Further, we focus on the length of sketches by studying mutual influence of sketch properties such as correlation of their bits and the intrinsic dimensionality of a set of sketches. The outcome is an equation that allows us to estimate a suitable length of sketches for an arbitrary given dataset. Finally, we empirically verify proposed approach on two real-life datasets.
ER  -

MÍČ, Vladimír; David NOVÁK a Pavel ZEZULA. Designing Sketches for Similarity Filtering. In Carlotta Domeniconi, Francesco Gullo, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu. \textit{2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW)}. USA: IEEE, 2016, s.~655-662. ISBN~978-1-5090-5472-5. Dostupné z: https://doi.org/10.1109/ICDMW.2016.0098.

Přehled o publikaci