National Repository of Dissertations in Serbia
    • English
    • Српски
    • Српски (Serbia)
  • English 
    • English
    • Serbian (Cyrilic)
    • Serbian (Latin)
  • Login
View Item 
  •   NaRDuS home
  • Универзитет у Новом Саду
  • Природно-математички факултет
  • View Item
  •   NaRDuS home
  • Универзитет у Новом Саду
  • Природно-математички факултет
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Approximation algorithms for k-NN graph construction

Aproksimativni algoritmi za generisanje k-NN grafa

Thumbnail
2021
Disertacija.pdf (3.362Mb)
IzvestajKomisije.pdf (650.7Kb)
Author
Bratić, Brankica
Mentor
Kurbalija, Vladimir
Committee members
Ivanović, Mirjana
Kurbalija, Vladimir
Radovanović, Miloš
Houle Michael, E.
Geler, Zoltan
Metadata
Show full item record
Abstract
Nearest neighbor graphs are modeling proximity relationships between objects. They are widely used in many areas, primarily in machine learning, but also in information retrieval, biology, computer graphics,geographic information systems, etc. The focus of this thesis are knearest neighbor graphs (k-NNG), a special class of nearest neighbor graphs. Each node of k-NNG is connected with directed edges to its k nearest neighbors.A brute-force method for constructing k-NNG entails O(n 2 ) distance calculations. This thesis addresses the problem of more efficient k-NNG construction, achieved by approximation algorithms. The main challenge of an approximation algorithm for k-NNG construction is to decrease the number of distance calculations, while maximizing the approximation’s accuracy.NN-Descent is one such approximation algorithm for k-NNG construction, which reports excellent results in many cases. However, it does not perform well on high-dimensional data. The first part of this thesis... summarizes the problem, and gives explanations for such a behavior. The second part introduces five new NN-Descent variants that aim to improve NN-Descent on high-dimensional data. The performance of the  proposed algorithms is evaluated with an experimental analysis.Finally, the third part of this thesis is dedicated to k-NNG update algorithms. Namely, in the real world scenarios data often change over time. If data change after k-NNG construction, the graph needs to be updated accordingly. Therefore, in this part of the thesis, two approximation algorithms for k-NNG updates are proposed. They are validated with extensive experiments on time series data.

Graf najbližih suseda modeluje veze između objekata koji su međusobno bliski. Ovi grafovi se koriste u mnogim disciplinama, pre svega u mašinskom učenju, a potom i u pretraživanju informacija, biologiji, računarskoj grafici, geografskim informacionim sistemima, itd. Fokus ove teze je graf k najbližih suseda (k-NN graf), koji predstavlja posebnu klasu grafova najbližih suseda. Svaki čvor k-NN grafa je povezan usmerenim granama sa njegovih k najbližih suseda.Metod grube sile za generisanje k-NN grafova podrazumeva O(n 2 ) računanja razdaljina između dve tačke. Ova teza se bavi  problemom efikasnijeg generisanja k-NN grafova, korišćenjem aproksimativnih  algoritama.Glavni cilj aprokismativnih algoritama za generisanje k-NN grafova jeste smanjivanje ukupnog broja računanja razdaljina između dve tačke, uz održavanje visoke tačnosti krajnje aproksimacije.NN-Descent je jedan takav aproksimativni algoritam za generisanje k-NN grafova. Iako se pokazao kao veoma dobar u većini slučajeva, ovaj al...goritam ne daje dobre rezultate nad visokodimenzionalnim podacima. Unutar prvog dela teze, detaljno je opisana suština problema i objašnjeni su razlozi za njegovo nastajaneU drugom delu predstavljeno je pet različitih modifikacija NN-Descent algoritma, koje za cilj imaju njegovo poboljšavanje pri radu nad visokodimenzionalnim podacima. Evaluacija ovih algoritama je data kroz eksperimentalnu analizu.Treći deo teze se bavi algoritmima za ažuriranje k-NN grafova. Naime,podaci se vrlo često menjaju  vremenom. Ukoliko se izmene podaci nad kojima je prethodno generisan k-NN graf, potrebno je graf ažurirati u skladu sa izmenama. U okviru ovog dela teze predložena su dva aproksimativna algoritma za ažuriranje k-NN grafova. Ovi algoritmi su evaluirani opširnim eksperimentima nad vremenskim serijama.

Faculty:
University of Novi Sad, Faculty of Science
Date:
08-01-2021
Keywords:
k-NN graph, NN-Descent , approximation algorithms, hubness / k-NN graf, NN-Descent , aproksimativni algoritmi, habnes
[ Google Scholar ]
URI
https://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija160284293400033.pdf?controlNumber=(BISIS)115425&fileName=160284293400033.pdf&id=16948&source=NaRDuS&language=sr
https://www.cris.uns.ac.rs/record.jsf?recordId=115425&source=NaRDuS&language=sr
https://www.cris.uns.ac.rs/DownloadFileServlet/IzvestajKomisije160284295201248.pdf?controlNumber=(BISIS)115425&fileName=160284295201248.pdf&id=16949&source=NaRDuS&language=sr
/DownloadFileServlet/IzvestajKomisije160284295201248.pdf?controlNumber=(BISIS)115425&fileName=160284295201248.pdf&id=16949
https://nardus.mpn.gov.rs/handle/123456789/18059

DSpace software copyright © 2002-2015  DuraSpace
About NaRDus | Contact us

OpenAIRERCUBRODOSTEMPUS
 

 

Browse

All of DSpaceUniversities & FacultiesAuthorsMentorCommittee membersSubjectsThis CollectionAuthorsMentorCommittee membersSubjects

DSpace software copyright © 2002-2015  DuraSpace
About NaRDus | Contact us

OpenAIRERCUBRODOSTEMPUS