%0 Journal Article
%4 sid.inpe.br/mtc-m21b/2017/05.31.19.12
%2 sid.inpe.br/mtc-m21b/2017/05.31.19.12.01
%@doi 10.1007/s12145-016-0282-2
%@issn 1865-0473
%@issn 1865-0481
%F self-archiving-INPE-MCTI-GOV-BR
%T An approximate nearest neighbors search algorithm for low-dimensional grid locations
%D 2017
%8 June
%9 journal article
%A Petry, Adriano,
%A Pereira, André Grahl,
%A Souza, Jonas Rodrigues de,
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation Universidade Federal do Rio Grande do Sul (UFRGS)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@electronicmailaddress adriano.petry@inpe.br
%@electronicmailaddress agpereira@inf.ufrgs.br
%@electronicmailaddress jonas.souza@inpe.br
%B Earth Science Informatics
%V 10
%N 2
%P 183-196
%K Approximate nearest neighbors, Ionosphere dynamics, Spatial interpolation.
%X 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 Earths 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.
%@language en
%3 petry_an.pdf