Bakalářská práce

Algoritmy pro vyhledání nejbližších sousedů

Nearest Neighbor Search Algorithms

Erik Hasprunár
Anotace

Bakalárska práca sa venuje vyhľadávaniu najbližších susedov. Stručne je predstavená teória spolu so známymi technikami vyhľadávania. Praktická časť implementuje známy algoritmus randomizovaného lesa KD~stromov a jeho rozšírenie pre indexáciu viac dátových množín. Algoritmus aj s rozšírením sú v práci popísané. Práca obsahuje aj vyhodnotenie experimentálnych testov a výkonnostné porovnanie s knižnicou VLFeat.

Abstract

Bachelor thesis deals with the nearest neighbor search. Basic theory and known techniques are discussed. Practical output of this work is implemented randomized kd-tree forest and the extension for indexing more data sets. Both algorithm and extension are discussed in the thesis. Thesis also contains experimental test results and performance comparisons to the VLFeat library.

Klíčová slova
vyhľadávanie najbližších susedov k-NN KD strom les randomizovaných KD stromov aproximované hľadanie MESSIF Java KD Tree nearest neighbor search randomized kd-tree forest approximate search
Zadání práce
Cílem práce je nastudovat několik dostupných algoritmů pro vyhledání nejbližších sousedů (kNN), vybraný algoritmus implementovat a porovnat výkonnost této implementace s existující knihovnou (VLfeat.org) nad vhodnou datovou množinou. Dále student navrhne algoritmus pro současné vyhodnocení kNN dotazu nad nezávislými datovými kolekcemi, které sdílí stejný metrický/vektorový prostor, a porovná jej se triviálním řešením, které využívá několik nezávislých indexů. Implementace bude v jazyce Java s využitím knihovny MESSIF. Textová část práce bude popisovat principy vybraných algoritmů, s důrazem na implementovaný algoritmus, a vyhodnocení experimentální výsledků.
Administrativní informace
Práce zkontrolována:
7. 1. 2015 10:05, doc. RNDr. Vlastislav Dohnal, Ph.D., učo 2952
Plný text práce
323,7 KB / soubor PDF
Přílohy (2)
Jazyk práce
slovenština slovenština
Termín obhajoby
2. 2. 2015
Práce byla úspěšně obhájena

Vedoucí

doc. RNDr. Vlastislav Dohnal, Ph.D., učo 2952
KPSK FI MU

Oponent

RNDr. Petra Budíková, Ph.D., učo 66445
abs FI MU

Literatura

  • ZEZULA, Pavel; Giuseppe AMATO; Vlastislav DOHNAL a Michal BATKO. Similarity Search: The Metric Space Approach. 2005. vyd. New York, NY 10013, USA: Springer, 2005, 220 s. Advances in Database Systems, Vol. 32. ISBN 0-387-29146-6.
  • BATKO, Michal; David NOVÁK a Pavel ZEZULA. MESSIF: Metric Similarity Search Implementation Framework. In Digital Libraries: Research and Development. Berlin, Heidelberg: Springer-Verlag, 2007, s. 1-10. ISBN 978-3-540-77087-9.
  • SAMET, Hanan. Foundations of multidimensional and metric data structures. Amsterdam: Elsevier, 2006, xxvii, 993. ISBN 0123694469.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • 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.