Please use this identifier to cite or link to this item:
|Title:||Find your neighbors (quickly!)||Authors:||Wong, Wei Tian.||Keywords:||DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity||Issue Date:||2011||Abstract:||In many computer vision problems, answering the nearest neighbor queries efficiently, especially in higher dimensions over a large dataset is a difficult task and highly time consuming. The brute force method to find the nearest neighbor to a point q requires a linear scan of all objects in S. However this method would prove too inefficient for large datasets with large d dimensional vectors. Therefore in recent years, the approximate nearest neighbor solution was proposed to mitigate the curse of dimensionality issue. These approximate algorithms are known to provide large speedups with a minor tradeoff between the loss of efficiency or accuracy. In this project, we compare and evaluate 3 approximate nearest neighbor algorithmic implementations against each other as well as the linear brute force search. The 3 algorithms that will be studied intensively throughout are the following: • ϵ-approximate nearest neighbor method that implements the k-d tree with a priority search tree. • Randomized k-d tree and Hierarchical kmeans tree algorithm||URI:||http://hdl.handle.net/10356/48509||Rights:||Nanyang Technological University||Fulltext Permission:||restricted||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SCSE Student Reports (FYP/IA/PA/PI)|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.