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. s. 655-662. ISBN 978-1-5090-5472-5. doi:10.1109/ICDMW.2016.0098. 2016.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Designing Sketches for Similarity Filtering
Autoři MÍČ, Vladimír (203 Česká republika, garant, domácí), David NOVÁK (203 Česká republika, domácí) a Pavel ZEZULA (203 Česká republika, domácí).
Vydání USA, 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), od s. 655-662, 8 s. 2016.
Nakladatel IEEE
Další údaje
Originální 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"
WWW URL
Kód RIV RIV/00216224:14330/16:00088645
Organizační jednotka Fakulta informatiky
ISBN 978-1-5090-5472-5
ISSN 2375-9232
Doi http://dx.doi.org/10.1109/ICDMW.2016.0098
UT WoS 000401906900090
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ěnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 14. 5. 2020 15:31.
Anotace
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 VaVNá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
VytisknoutZobrazeno: 29. 3. 2024 02:53