Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/48509
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)

Files in This Item:
File Description SizeFormat 
SCE11-0299.pdf
  Restricted Access
FYP Report: Find Your Neighbors (Quickly!)1.51 MBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.