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.

• Record URL:
  http://prod.sandia.gov/techlib/access-control.cgi/2010/104313.pdf
• 
• Corporate Authors:

  Sandia National Laboratories

  P.O. Box 5800
  Albuquerque, NM  United States  87185

  Department of Energy

  1000 Independence Avenue, SW
  Washington, DC  United States  20585
• Authors:
  • Mackey, Greg E
• Publication Date: 2010-7

Language

• English

Media Info

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

Subject/Index Terms

• TRT Terms: Calculation; Distance; Information processing; Mathematical models; Optimization; Running time; Simulation; Spatial analysis
• Uncontrolled Terms: Nearest neighbor searching
• Subject Areas: Data and Information Technology; Planning and Forecasting; I72: Traffic and Transport Planning;

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