Aceleração de uma variação do problema k-nearest neighbors
Carregando...
Data
2014-01-29
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
Let M be a metric space and let P be a subset of M. The well known k-nearest neighbors
problem (KNN) consists in finding, given q 2 M, the k elements of P with are closest to
q according to the metric of M. We discuss a variation of KNN for a particular class of
pseudo-metric spaces, described as follows. Let m 2 N be a natural number and let d be
the Euclidean distance in Rm. Given p 2 Rm:
p := (p1; : : : ; pm)
let C (p) be the set of the m rotations of p’s coordinates:
C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm1)g
we define the special distance de as:
de(p;q) := min
p02C (p)
d(p0;q):
de is a pseudo-metric, and (Rm;de) is a pseudo-metric space. The class of pseudo-metric
spaces under discussion is
f(Rm;de) j m 2 N:g
The brute force approach is too costly for instances of practical size. We present a more
efficient solution employing parallelism, the FFT (fast Fourier transform) and the fast
elimination of unfavorable training vectors.We describe a program—named CyclicKNN
—which implements this solution.We report the speedup of this program over serial brute
force search, processing reference datasets.
Descrição
Palavras-chave
Aceleração , Análise de dados multidimensionais , K-nearest neighbors , K vizinhos mais próximos , Matriz circulante , Processamento de imagem , Programação paralela , Transformada rápida de Fourier , Acceleration , K-nearest neighbors , Circulant matrix , Image processing , Fast Fourier transform , Multidimensional data analysis , Parallel programming
Citação
MORAIS NETO, Jorge Peixoto de. Aceleração de uma variação do problema k-nearest neighbors. 2014. 97 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2014.