Detalhes bibliográficos
| Ano de defesa: |
2014 |
| Autor(a) principal: |
Morais Neto, Jorge Peixoto de
 |
| Orientador(a): |
Martins, Wellington Santos
|
| Banca de defesa: |
Longo, Humberto José,
Rodrigues, Rosiane de Freitas,
Silva, EdCarlos Domingos da |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Universidade Federal de Goiás
|
| Programa de Pós-Graduação: |
Programa de Pós-graduação em Ciência da Computação (INF)
|
| Departamento: |
Instituto de Informática - INF (RG)
|
| País: |
Brasil
|
| Palavras-chave em Português: |
|
| Palavras-chave em Inglês: |
|
| Área do conhecimento CNPq: |
|
| Link de acesso: |
http://repositorio.bc.ufg.br/tede/handle/tede/3687
|
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. |
