Efficient nearest neighbor searches in N-ABLE.

Mackey, Greg Edward

关键词: POPULATION DENSITY;    DISTRIBUTION;    DISTANCE;    COMPUTER CALCULATIONS;    TRANSPORTATION SYSTEMS;    COMPUTERIZED SIMULATION Transportation-Data processing.;    Transportation;   

DOI  :  10.2172/992313
RP-ID  :  SAND2010-4313
PID  :  OSTI ID: 992313
Others  :  TRN: US201022%%355

美国|英语

来源: SciTech Connect

【 摘 要 】

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 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.