首页 | 本学科首页   官方微博 | 高级检索  
     检索      


An approximate nearest neighbors search algorithm for low-dimensional grid locations
Authors:Adriano Petry  André Grahl Pereira  Jonas Rodrigues de Souza
Institution:1.Southern Regional Space Research Center,National Institute for Space Research,Santa Maria,Brazil;2.Institute of Informatics,Federal University of Rio Grande do Sul,Porto Alegre,Brazil;3.Aeronomy Division,National Institute for Space Research,S?o José dos Campos,Brazil
Abstract:We propose a new algorithm for the problem of approximate nearest neighbors (ANN) search in a regularly spaced low-dimensional grid for interpolation applications. It associates every sampled point to its nearest interpolation location, and then expands its influence to neighborhood locations in the grid, until the desired number of sampled points is achieved on every grid location. Our approach makes use of knowledge on the regular grid spacing to avoid measuring the distance between sampled points and grid locations. We compared our approach with four different state-of-the-art ANN algorithms in a large set of computational experiments. In general, our approach requires low computational effort, especially for cases with high density of sampled points, while the observed error is not significantly different. At the end, a case study is shown, where the ionosphere dynamics is predicted daily using samples from a mathematical model, which runs in parallel at 56 different longitude coordinates, providing sampled points not well distributed that follow Earth’s magnetic field-lines. Our approach overcomes the comparative algorithms when the ratio between the number of sampled points and grid locations is over 2849:1.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号