Acceleration of Binning Nearest Neighbour Methods

  1. (PDF, 275 KB)
AuthorSearch for: ; Search for: ; Search for:
ConferenceProceedings of Vision Interface 2000, May 14-17, 2000., Montréal, Québec, Canada
AbstractA new solution method to the Nearest Neighbour Problem is presented. The method is based upon the triangle inequality and works well for small point sets, where traditional solutions are particularly ineffective. Its performance is characterized experimentally and compared with k-d tree and Elias approaches. A hybrid approach is proposed wherein the triangle inequality method is applied to the k-d tree and Elias bin sets. The hybridization is shown to accelerate the k-d tree for large point sets, resulting in 20% improvement in time performance. The space efficiencies for both the k-d tree and Elias methods also improve under the hybrid scheme.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number44167
NPARC number5763679
Export citationExport as RIS
Report a correctionReport a correction
Record identifiera4dfbe41-b704-487a-8f19-884197124ff5
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: