Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-25T13:07:50Z
No. of bitstreams: 2
Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-25T14:42:09Z (GMT) No. of bitstreams: 2
Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-25T14:42:09Z (GMT). No. of bitstreams: 2
Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2014-01-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / Seja M um espaço métrico e P um subconjunto de M. O conhecido problema k vizinhos
mais próximos (k-neareast neighbors, KNN) consiste em encontrar, dado q 2 M, os k
elementos de P mais próximos de q conforme a métrica de M. Abordamos uma variação
do problema KNN para uma classe particular de espaços pseudo-métricos, descrita a
seguir. Seja m 2 N um natural e seja d a distância euclidiana em Rm. Dado um vetor
p 2 Rm:
p := (p1; : : : ; pm)
seja C (p) o conjunto das m rotações das coordenadas de p:
C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm1)g
definimos a distância especial de como:
de(p;q) := min
p02C (p)
d(p0;q):
de é uma pseudo-métrica, e (Rm;de) é um espaço pseudo-métrico. A classe de espaços
pseudo-métricos abordada é
(Rm;de) j m 2 N:
A solução por força bruta é cara demais para instâncias de tamanho prático. Nós apresentamos
uma solução mais eficiente empregando paralelismo, a FFT (transformada rápida
de Fourier) e a eliminação rápida de vetores de treinamento desfavoráveis. Desenvolvemos
um programa—chamado CyclicKNN—que implementa essa solução. Reportamos
o speedup desse programa em comparação com a força bruta sequencial, processando
bases de dados de referência.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3687 |
| Date | 29 January 2014 |
| Creators | Morais Neto, Jorge Peixoto de |
| Contributors | Martins, Wellington Santos, Longo, Humberto José, Foulds, Leslie Richard, Longo, Humberto José, Rodrigues, Rosiane de Freitas, Silva, EdCarlos Domingos da |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0031 seconds