On the Similarity Search With Hamming Space Sketches

C 2021

On the Similarity Search With Hamming Space Sketches

MÍČ, Vladimír and Pavel ZEZULA

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

Language

English

Type of outcome

Kapitola resp. kapitoly v odborné knize

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:

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

Změněno: 23/5/2022 13:16, Mgr. Michal Petr

Abstract

V originále

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

Citovat

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.

@inbook{1759880,
   author = {Míč, Vladimír and Zezula, Pavel},
   address = {Hershey, PA (USA)},
   booktitle = {Intelligent Analytics With Advanced Multi-Industry Applications},
   doi = {http://dx.doi.org/10.4018/978-1-7998-4963-6.ch005},
   editor = {Zhaohao Sun},
   keywords = {Similarity search;Hamming space;Sketch;Efficiency;Metric Space;Space Transformations},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Hershey, PA (USA)},
   isbn = {978-1-7998-4963-6},
   pages = {97-127},
   publisher = {IGI Global},
   title = {On the Similarity Search With Hamming Space Sketches},
   url = {https://www.igi-global.com/chapter/on-the-similarity-search-with-hamming-space-sketches/272781},
   year = {2021}
}

TY  - CHAP
ID  - 1759880
AU  - Míč, Vladimír - Zezula, Pavel
PY  - 2021
TI  - On the Similarity Search With Hamming Space Sketches
VL  - First edition, 1
PB  - IGI Global
CY  - Hershey, PA (USA)
SN  - 9781799849636
KW  - Similarity search;Hamming space;Sketch;Efficiency;Metric Space;Space Transformations
UR  - https://www.igi-global.com/chapter/on-the-similarity-search-with-hamming-space-sketches/272781
N2  - 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.
ER  -

MÍČ, Vladimír and Pavel ZEZULA. On the Similarity Search With Hamming Space Sketches. In Zhaohao Sun. \textit{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.

Detailed Information on Publication Record