Detailed Information on Publication Record
2016
Designing Sketches for Similarity Filtering
MÍČ, Vladimír, David NOVÁK and Pavel ZEZULABasic information
Original name
Designing Sketches for Similarity Filtering
Authors
MÍČ, Vladimír (203 Czech Republic, guarantor, belonging to the institution), David NOVÁK (203 Czech Republic, belonging to the institution) and Pavel ZEZULA (203 Czech Republic, belonging to the institution)
Edition
USA, 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), p. 655-662, 8 pp. 2016
Publisher
IEEE
Other information
Language
English
Type of outcome
Stať ve sborníku
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í
Publication form
printed version "print"
References:
RIV identification code
RIV/00216224:14330/16:00088645
Organization unit
Faculty of Informatics
ISBN
978-1-5090-5472-5
ISSN
UT WoS
000401906900090
Keywords in English
Algorithm;Similarity search;Similarity filtering;Bit strings;Sketches;Hamming distance
Tags
Tags
International impact, Reviewed
Změněno: 14/5/2020 15:31, RNDr. Pavel Šmerk, Ph.D.
Abstract
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.
Links
GBP103/12/G084, research and development project |
|