Iskanje podobnih primerov v večrazsežnih prostorih
Iskanje najbližjih objektov se uporablja na različnih področjih in pomembno je, da jih lahko hitro poiščemo. Pri iskanju v visokodimenzionalnih prostorih ne znamo hitro poiskati eksaktnih sosedov, zato se zadovoljimo s približnimi. V magistrski nalogi opišemo najbolj uporabljane eksaktne in približn...
Main Author: | |
---|---|
Other Authors: | |
Format: | Master Thesis |
Language: | Slovenian |
Published: |
P. Kariž
2015
|
Subjects: | |
Online Access: | https://repozitorij.uni-lj.si/IzpisGradiva.php?id=70240 https://repozitorij.uni-lj.si/Dokument.php?id=70251&dn= http://www.cobiss.si/scripts/cobiss?command=DISPLAY&base=cobib&rid=1536276675&fmt=11 |
id |
ftuniljubljanair:oai:repozitorij.uni-lj.si:IzpisGradiva.php-id-70240 |
---|---|
record_format |
openpolar |
spelling |
ftuniljubljanair:oai:repozitorij.uni-lj.si:IzpisGradiva.php-id-70240 2023-05-15T18:13:50+02:00 Iskanje podobnih primerov v večrazsežnih prostorih Searching nearest neighbours in high dimensional spaces Kariž, Primož Robnik Šikonja, Marko 2015-07-10 text/url https://repozitorij.uni-lj.si/IzpisGradiva.php?id=70240 https://repozitorij.uni-lj.si/Dokument.php?id=70251&dn= http://www.cobiss.si/scripts/cobiss?command=DISPLAY&base=cobib&rid=1536276675&fmt=11 slv slv P. Kariž https://repozitorij.uni-lj.si/IzpisGradiva.php?id=70240 https://repozitorij.uni-lj.si/Dokument.php?id=70251&dn= http://www.cobiss.si/scripts/cobiss?command=DISPLAY&base=cobib&rid=1536276675&fmt=11 info:eu-repo/semantics/openAccess algoritmi podatkovne strukture iskanje najbližjih sosedov približni najbližji sosedi visokodimenzionalni prostor R-drevo R*-drevo M-drevo PM-drevo ball-drevo KD-drevo RKD-drevo LSH hierarhično razvrščanje z voditelji računalništvo računalništvo in informatika magisteriji algorithms data structures nearest neighbours search approximate nearest neighbours high-dimensional space R-tree R*-tree M-tree PM-tree ball-tree KD-tree RKD-tree hierarchical k-means computer science computer and information science master's degree info:eu-repo/classification/udc/004.42(043.2) info:eu-repo/semantics/masterThesis info:eu-repo/semantics/publishedVersion 2015 ftuniljubljanair 2021-12-06T09:39:35Z Iskanje najbližjih objektov se uporablja na različnih področjih in pomembno je, da jih lahko hitro poiščemo. Pri iskanju v visokodimenzionalnih prostorih ne znamo hitro poiskati eksaktnih sosedov, zato se zadovoljimo s približnimi. V magistrski nalogi opišemo najbolj uporabljane eksaktne in približne metode za iskanje najbližjih sosedov. Med eksaktnimi so to R, R*, KD, M, PM in ball-drevo, med približnimi pa RKD-drevo, LSH, hierarhično razvrščanje z voditelji in gozd robov. Nekatere smo implementirali sami, druge smo uporabili iz že obstoječih knjižnic. Predstavimo in analiziramo rezultate testiranj hitrosti iskanja najbližjih sosedov, točnosti in porabe pomnilnika. V programskem jeziku python smo razvili knjižnico, ki vsebuje opisane metode in omogoča njihovo preprosto in enotno uporabo preko programskega vmesnika. Knjižnica omogoča tudi avtomatsko izbiro najprimernejšega algoritma za dano podatkovno množico. Algoritem izberemo na podlagi dveh odločitvenih dreves, ki smo ju sestavili s pomočjo analize rezultatov testiranj. Nearest neighbours search is used in different problems, therefore it is important that we are able to find nearest neighbours fast. When searching in high-dimensional spaces we have to be satisfied with approximate nearest neighbours, because fast methods do not exist. In this master thesis we describe some well-known exact and approximate methods for searching nearest neighbours. The described exact ones are R, R*, KD, M, PM and ball-tree, while the approximate are RKD-tree, LSH, hierarchical k-means and boundary-forest. Some of them we implemented, while others were taken from existing libraries. We present and analyze the search results in terms of speed, precision and memory requirements of methods. We developed a library in python programming language, which includes the described methods and provides a simple and consistent API. The library also allows automatic selection of the most suitable algorithm for a given dataset based on two decision trees, which were created through analysis of the results. Master Thesis sami Repository of the University of Ljubljana (RUL) |
institution |
Open Polar |
collection |
Repository of the University of Ljubljana (RUL) |
op_collection_id |
ftuniljubljanair |
language |
Slovenian |
topic |
algoritmi podatkovne strukture iskanje najbližjih sosedov približni najbližji sosedi visokodimenzionalni prostor R-drevo R*-drevo M-drevo PM-drevo ball-drevo KD-drevo RKD-drevo LSH hierarhično razvrščanje z voditelji računalništvo računalništvo in informatika magisteriji algorithms data structures nearest neighbours search approximate nearest neighbours high-dimensional space R-tree R*-tree M-tree PM-tree ball-tree KD-tree RKD-tree hierarchical k-means computer science computer and information science master's degree info:eu-repo/classification/udc/004.42(043.2) |
spellingShingle |
algoritmi podatkovne strukture iskanje najbližjih sosedov približni najbližji sosedi visokodimenzionalni prostor R-drevo R*-drevo M-drevo PM-drevo ball-drevo KD-drevo RKD-drevo LSH hierarhično razvrščanje z voditelji računalništvo računalništvo in informatika magisteriji algorithms data structures nearest neighbours search approximate nearest neighbours high-dimensional space R-tree R*-tree M-tree PM-tree ball-tree KD-tree RKD-tree hierarchical k-means computer science computer and information science master's degree info:eu-repo/classification/udc/004.42(043.2) Kariž, Primož Iskanje podobnih primerov v večrazsežnih prostorih |
topic_facet |
algoritmi podatkovne strukture iskanje najbližjih sosedov približni najbližji sosedi visokodimenzionalni prostor R-drevo R*-drevo M-drevo PM-drevo ball-drevo KD-drevo RKD-drevo LSH hierarhično razvrščanje z voditelji računalništvo računalništvo in informatika magisteriji algorithms data structures nearest neighbours search approximate nearest neighbours high-dimensional space R-tree R*-tree M-tree PM-tree ball-tree KD-tree RKD-tree hierarchical k-means computer science computer and information science master's degree info:eu-repo/classification/udc/004.42(043.2) |
description |
Iskanje najbližjih objektov se uporablja na različnih področjih in pomembno je, da jih lahko hitro poiščemo. Pri iskanju v visokodimenzionalnih prostorih ne znamo hitro poiskati eksaktnih sosedov, zato se zadovoljimo s približnimi. V magistrski nalogi opišemo najbolj uporabljane eksaktne in približne metode za iskanje najbližjih sosedov. Med eksaktnimi so to R, R*, KD, M, PM in ball-drevo, med približnimi pa RKD-drevo, LSH, hierarhično razvrščanje z voditelji in gozd robov. Nekatere smo implementirali sami, druge smo uporabili iz že obstoječih knjižnic. Predstavimo in analiziramo rezultate testiranj hitrosti iskanja najbližjih sosedov, točnosti in porabe pomnilnika. V programskem jeziku python smo razvili knjižnico, ki vsebuje opisane metode in omogoča njihovo preprosto in enotno uporabo preko programskega vmesnika. Knjižnica omogoča tudi avtomatsko izbiro najprimernejšega algoritma za dano podatkovno množico. Algoritem izberemo na podlagi dveh odločitvenih dreves, ki smo ju sestavili s pomočjo analize rezultatov testiranj. Nearest neighbours search is used in different problems, therefore it is important that we are able to find nearest neighbours fast. When searching in high-dimensional spaces we have to be satisfied with approximate nearest neighbours, because fast methods do not exist. In this master thesis we describe some well-known exact and approximate methods for searching nearest neighbours. The described exact ones are R, R*, KD, M, PM and ball-tree, while the approximate are RKD-tree, LSH, hierarchical k-means and boundary-forest. Some of them we implemented, while others were taken from existing libraries. We present and analyze the search results in terms of speed, precision and memory requirements of methods. We developed a library in python programming language, which includes the described methods and provides a simple and consistent API. The library also allows automatic selection of the most suitable algorithm for a given dataset based on two decision trees, which were created through analysis of the results. |
author2 |
Robnik Šikonja, Marko |
format |
Master Thesis |
author |
Kariž, Primož |
author_facet |
Kariž, Primož |
author_sort |
Kariž, Primož |
title |
Iskanje podobnih primerov v večrazsežnih prostorih |
title_short |
Iskanje podobnih primerov v večrazsežnih prostorih |
title_full |
Iskanje podobnih primerov v večrazsežnih prostorih |
title_fullStr |
Iskanje podobnih primerov v večrazsežnih prostorih |
title_full_unstemmed |
Iskanje podobnih primerov v večrazsežnih prostorih |
title_sort |
iskanje podobnih primerov v večrazsežnih prostorih |
publisher |
P. Kariž |
publishDate |
2015 |
url |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=70240 https://repozitorij.uni-lj.si/Dokument.php?id=70251&dn= http://www.cobiss.si/scripts/cobiss?command=DISPLAY&base=cobib&rid=1536276675&fmt=11 |
genre |
sami |
genre_facet |
sami |
op_relation |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=70240 https://repozitorij.uni-lj.si/Dokument.php?id=70251&dn= http://www.cobiss.si/scripts/cobiss?command=DISPLAY&base=cobib&rid=1536276675&fmt=11 |
op_rights |
info:eu-repo/semantics/openAccess |
_version_ |
1766186491307884544 |