Original title: Metody hledání k-nejbližších sousedů
Translated title: K-Nearest Neighbour Search Methods
Authors: Cigánik, Marek ; Bartík, Vladimír (referee) ; Burgetová, Ivana (advisor)
Document type: Master’s theses
Year: 2023
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
V práci je popsán základní koncept algoritmu K-nejbližších sousedů a jeho vazba s lidským pojetím podobnosti objektů. Jsou rozvedeny pojmy a klíčové myšlenky jako vzdálenostní funkce nebo prokletí dimenzionality. Práce zahrnuje detailní popis metod KD-Strom, Kulovitý strom, Locality-Sensitive Hashing, Strom náhodných projekcí a rodiny algoritmů založené na grafu nejbližších sousedů. Ke každé metodě je poskytnuto vysvětlení ideje s vizualizacemi, pseudokódy a asymptotickými složitostmi. Metody byly podrobeny experimentům a byly měřeny základní i pokročilejší metriky, ze kterých byly vyhodnoceny případy vhodnosti pro jednotlivé metody. The thesis describes the basic concept of the K-nearest neighbors algorithm and its connection with the human concept of object similarity. Concepts and key ideas such as the distance function or the curse of dimensionality are elaborated. The work includes a detailed description of the methods KD-Tree, Spherical Tree, Locality-Sensitive Hashing, Random Projection Tree and families of algorithms based on the nearest neighbor graph. An explanation of the idea with visualizations, pseudocodes and asymptotic complexities is provided for each method. The methods were subjected to experiments and both basic and more advanced metrics were measured and appropriate use cases for individual methods were evaluated.
Keywords: Ball-Tree; HNSW; K-nearest neighbors; KD-Tree; KNN; KNNGraph; Locality-Sensitive Hasning; LSH; NNDescent; RPTree; HNSW; K-nejbližších sousedů; KD-Strom; KNN; KNN graf; Kulovitý Strom; Locality-Sensitive Hashing; LSH; NNDescent; Strom náhodných projekcí

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/211912

Permalink: http://www.nusl.cz/ntk/nusl-530177


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses