Original title: Akcelerace vyhledávání v prostorových strukturách
Translated title: Search Acceleration in Spatial Structure
Authors: Vlk, Jakub ; Čižmarik, Roman (referee) ; Vlnas, Michal (advisor)
Document type: Bachelor's theses
Year: 2024
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce představuje implementaci rychlých algoritmů pro nalezení nejbližšího souseda, které efektivně určují, který bod z dané množiny je nejblíže k zadanému bodu. Algoritmy jsou navíc škálovatelné pro hledání k-nejbližších sousedů. Součástí je i specializované vyhledávání bodů s podobnou orientací na základě specifických kritérií a většího množství přístupů pro hledání orientovaných bodů. Struktura využívá vlastností z Voronoi diagramu, Octree, ale i hašovací tabulky nebo binární vyhledávání. Složitost u vyhledání nejbližšího souseda dosahuje časů blížících se konstantním hodnotám, neboť celková složitost je logaritmicky logaritmická. Práce obsahuje podrobné testování, jak po stránce přesnosti, tak po stránce výkonnosti. This thesis presents the implementation of a fast nearest neighbor lookup algorithm, which identifies the closest point from a set of points to other points. "The algorithm is scalable for searching for k-neighbors, and it supports the identification of oriented points according to selected criteria and various approaches. The structure offers various approaches and utilizes properties of structures such as Voronoi diagrams, Octree binary search, or hash tables. The complexity of the nearest neighbor search is nearly constant because the cost is logarithmically logarithmic. The thesis shows numerous benchmarks for accuracy and performance.
Keywords: algorithm optimization; hash table; k-nearest neighbors; machine code; nearest neighbor; octree; parallel processing; search acceleration; Spatial structures; vectorization; akcelerace vyhledávání; hašovací tabulka; k-nejbližší soused; nejbližší soused; oktalový strom; optimalizace algoritmů; paralelní zpracování; Prostorové struktury; strojový kód; vektorizace

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

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


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