Bachelor's thesis
Awards: Dean's Award for an Outstanding Final Thesis

Experimental Verification of a Synergy of Techniques for Efficient Similarity Search in Metric Spaces

Iuliia Mariachkina
Abstract

Efektivní podobnostní vyhledávání je zásadní pro mnoho aplikací. Existují studie, které ukazují, že některé kombinace indexačních technik zvyšují efektivitu podobnostního vyhledávání ve srovnání se samostatnými indexačními technikami. Zatím však nebyla provedena dostatečně systematická studie na toto téma. Tato práce si klade za cíl poskytnout experimentální studii synergií indexačních technik různých …more

Abstract

Effective and efficient similarity search is crucial for many applications. There is strong but insufficiently systematized evidence that combinations of several indexing techniques increase the similarity search efficiency compared with standalone indexing techniques. This thesis aims to provide an experimental study of a synergy of indexing techniques of various types. To verify our hypothesis …more

Keywords
Similarity Search Approximate Similarity Search Metric Space kNN Queries Metric Filtering LAESA M-tree Metric Filtering Under the Assumption of Limited Angles in Triangles of Distances Pivot Permutation-based indexes PPP-Codes M-Index Transformations to Hamming Space
Thesis description
The student is asked to learn challenges of the similarity search in complex data such as multimedia, and basic approaches for efficient similarity search. She will consider both, the precise and approximate evaluations of queries by example, and study principles of contemporary searching techniques. The main focus will be paid to the following principles of searching techniques: the metric filtering, i.e. the use of triangle inequalities; triangle inequalities under the condition of limited angles in triangles of distances, transformations of metric spaces into the space of distances to pivoting objects; transformations of the searched space into Hamming space. The practical part of the thesis consists of experiments on the synergy of the selected techniques based on different principles, i.e., verification of the contribution of their chaining for more effective filtering of the searched dataset to speed up the similarity search. This should be done via analysis of the sets of non-filtered parts of the searched datasets.
Administrative information
The thesis has been checked:
20/12/2021 11:12, RNDr. Vladimír Míč, Ph.D., UČO 359890
Full text of thesis
1 MB / file PDF
Attachments (5)
Language used
English English
Defence date
8/2/2022
The thesis was defended successfully

Supervisor

RNDr. Vladimír Míč, Ph.D., UČO 359890
KSUZD FI MU

Reader

prof. Ing. Pavel Zezula, CSc., UČO 47485
KSUZD FI MU

Literature

  • ZEZULA, Pavel; Giuseppe AMATO; Vlastislav DOHNAL and Michal BATKO. Similarity Search: The Metric Space Approach. 2005th ed. New York, NY 10013, USA: Springer, 2005, 220 pp. Advances in Database Systems, Vol. 32. ISBN 0-387-29146-6.
  • MÍČ, Vladimír; David NOVÁK and Pavel ZEZULA. Binary Sketches for Secondary Filtering. ACM Transactions on Information Systems. New York: ACM Press, 2019, vol. 37, No 1, p. "1:1"-"1:28", 28 pp. ISSN 1046-8188. Available from: https://doi.org/10.1145/3231936.
  • CONNOR, Richard; Alan DEARLE; Vladimír MÍČ and Pavel ZEZULA. On the Application of Convex Transforms to Metric Search. Pattern Recognition Letters. 2020, vol. 138, October 2020, p. 563-570. ISSN 0167-8655. Available from: https://doi.org/10.1016/j.patrec.2020.08.008.
  • MÍČ, Vladimír and Pavel ZEZULA. Accelerating Metric Filtering by Improving Bounds on Estimated Distances. In Shin'ichi Satoh, Lucia Vadicamo, Arthur Zimek, Fabio Carrara, Ilaria Bartolini, Martin Aumüller, Björn Þór JónssonRasmus Pagh. Similarity Search and Applications: 13th International Conference, SISAP 2020, Copenhagen, Denmark, September 30 - October 2, 2020, Proceedings. Cham: Springer, 2020, p. 3-17. ISBN 978-3-030-60935-1. Available from: https://doi.org/10.1007/978-3-030-60936-8_1.
Cite this text
Masaryk University Faculty of Informatics
Programme
Informatics
Field of Study

Theses on a related topic

List of theses with an identical keyword.

Similar documents
 
Name
Posted by
Uploaded/Created
Rights
Archive of Thesis/Dissertation Iuliia Mariachkina FI B-IN PSZD m14as/11
Zemanová, J.
26/11/2021
Folders
Files
Abstract (in English) annotation_english.txt
Mariachkina, I.
16/12/2021
Abstract (in Czech) annotation.txt
Mariachkina, I.
16/12/2021
Keywords keywords.txt
Mariachkina, I.
15/12/2021
Full text of thesis Text.pdf
Mariachkina, I.
16/12/2021
Reader's report posudek_oponenta_Zezula.pdf
Zezula, P.
11/1/2022
Supervisor's report posudek_vedouciho_Mic.pdf
Míč, V.
20/1/2022
Appendix bp.zip
Mariachkina, I.
15/12/2021
Appendix Decaf.csv
Mariachkina, I.
15/12/2021
Appendix Mpeg.csv
Mariachkina, I.
15/12/2021
Appendix Random.csv
Mariachkina, I.
15/12/2021
Appendix Sift.csv
Mariachkina, I.
15/12/2021

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.