On the Similarity Search With Hamming Space Sketches

MÍČ, Vladimír and Pavel ZEZULA. On the Similarity Search With Hamming Space Sketches. In Zhaohao Sun. Intelligent Analytics With Advanced Multi-Industry Applications. Hershey, PA (USA): IGI Global, 2021, p. 97-127. First edition, 1. ISBN 978-1-7998-4963-6. Available from: https://dx.doi.org/10.4018/978-1-7998-4963-6.ch005.

Basic information

• Original name: On the Similarity Search With Hamming Space Sketches
• Authors: MÍČ, Vladimír (203 Czech Republic, guarantor, belonging to the institution) and Pavel ZEZULA (203 Czech Republic, belonging to the institution).
• Edition: Hershey, PA (USA), Intelligent Analytics With Advanced Multi-Industry Applications, p. 97-127, 31 pp. First edition, 1, 2021.
• Publisher: IGI Global

Other information

• Original language: English
• Type of outcome: Chapter(s) of a specialized book
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• WWW: URL
• RIV identification code: RIV/00216224:14330/21:00121403
• Organization unit: Faculty of Informatics
• ISBN: 978-1-7998-4963-6
• Doi: http://dx.doi.org/10.4018/978-1-7998-4963-6.ch005
• Keywords in English: Similarity search;Hamming space;Sketch;Efficiency;Metric Space;Space Transformations

Abstract

This chapter focuses on data searching, which is nowadays mostly based on similarity. The similarity search is challenging due to its computational complexity, and also the fact that similarity is subjective and context dependent. The authors assume the metric space model of similarity, defined by the domain of objects and the metric function that measures the dissimilarity of object pairs. The volume of contemporary data is large, and the time efficiency of similarity query executions is essential. This chapter investigates transformations of metric space to Hamming space to decrease the memory and computational complexity of the search. Various challenges of the similarity search with sketches in the Hamming space are addressed, including the definition of sketching transformation and efficient search algorithms that exploit sketches to speed-up searching. The indexing of Hamming space and a heuristic to facilitate the selection of a suitable sketching technique for any given application are also considered.

Links

• EF16_019/0000822, research and development project: Name: Centrum excelence pro kyberkriminalitu, kyberbezpečnost a ochranu kritických informačních infrastruktur