Efficient Nearest Neighbor Searches in N-ABLE™

The nearest neighbor search is a significant problem in transportation modeling and simulation. This paper describes how the nearest neighbor search is implemented efficiently with respect to running time in the National Infrastructure Simulation and Analysis Center (NISAC) Agent-Based Laboratory for Economics. The paper shows two methods to optimize running time of the nearest neighbor search. The first optimization uses a different distance metric that is more computationally efficient. The concept of a magnitude-comparable distance is described, and the paper gives a specific magnitude-comparable distance that is more computationally efficient than the actual distance function. The paper also shows how the given magnitude-comparable distance can be used to speed up the actual distance calculation. The second optimization reduces the number of points the search examines by using a spatial data structure. The paper concludes with testing of the different techniques discussed and the results.

Language

  • English

Media Info

  • Media Type: Print
  • Features: Figures; References; Tables;
  • Pagination: 22p

Subject/Index Terms

Filing Info

  • Accession Number: 01341113
  • Record Type: Publication
  • Report/Paper Numbers: SAND2010-4313
  • Contract Numbers: DE-AC04-94AL85000
  • Files: TRIS
  • Created Date: May 26 2011 2:43PM