Aceleração de uma variação do problema k-nearest neighbors
dc.contributor.advisor-co1 | Longo, Humberto José | |
dc.contributor.advisor-co2 | Foulds, Leslie Richard | |
dc.contributor.advisor1 | Martins, Wellington Santos | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/3041686206689904 | por |
dc.contributor.referee1 | Longo, Humberto José | |
dc.contributor.referee2 | Rodrigues, Rosiane de Freitas | |
dc.contributor.referee3 | Silva, EdCarlos Domingos da | |
dc.creator | Morais Neto, Jorge Peixoto de | |
dc.creator.Lattes | http://lattes.cnpq.br/7912605507453462 | por |
dc.date.accessioned | 2014-11-25T14:42:09Z | |
dc.date.issued | 2014-01-29 | |
dc.description.abstract | 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. | eng |
dc.description.provenance | 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) | eng |
dc.description.provenance | 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) | eng |
dc.description.provenance | 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 | eng |
dc.description.resumo | 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. | por |
dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES | por |
dc.format | application/pdf | * |
dc.identifier.citation | 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. | por |
dc.identifier.uri | http://repositorio.bc.ufg.br/tede/handle/tede/3687 | |
dc.language | por | por |
dc.publisher | Universidade Federal de Goiás | por |
dc.publisher.country | Brasil | por |
dc.publisher.department | Instituto de Informática - INF (RG) | por |
dc.publisher.initials | UFG | por |
dc.publisher.program | Programa de Pós-graduação em Ciência da Computação (INF) | por |
dc.rights | Acesso Aberto | por |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
dc.subject | Aceleração | por |
dc.subject | Análise de dados multidimensionais | por |
dc.subject | K-nearest neighbors | por |
dc.subject | K vizinhos mais próximos | por |
dc.subject | Matriz circulante | por |
dc.subject | Processamento de imagem | por |
dc.subject | Programação paralela | por |
dc.subject | Transformada rápida de Fourier | por |
dc.subject | Acceleration | eng |
dc.subject | K-nearest neighbors | eng |
dc.subject | Circulant matrix | eng |
dc.subject | Image processing | eng |
dc.subject | Fast Fourier transform | eng |
dc.subject | Multidimensional data analysis | eng |
dc.subject | Parallel programming | eng |
dc.subject.cnpq | CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | por |
dc.thumbnail.url | http://repositorio.bc.ufg.br/tede/retrieve/12815/Disserta%c3%a7%c3%a3o%20-%20Jorge%20Peixoto%20de%20Morais%20Neto%20-%202014.pdf.jpg | * |
dc.title | Aceleração de uma variação do problema k-nearest neighbors | por |
dc.title.alternative | Acceleration of a variation of the K-nearest neighbors problem | eng |
dc.type | Dissertação | por |
Arquivos
Pacote Original
1 - 1 de 1
Carregando...
- Nome:
- Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf
- Tamanho:
- 1.51 MB
- Formato:
- Adobe Portable Document Format
- Descrição:
Licença do Pacote
1 - 1 de 1
Nenhuma Miniatura disponível
- Nome:
- license.txt
- Tamanho:
- 2.11 KB
- Formato:
- Item-specific license agreed upon to submission
- Descrição: