Soluções aproximadas para algoritmos escaláveis de mineração de dados em domínios de dados complexos usando GPGPU (2011)
- Authors:
- Autor USP: MAMANI, ALEXANDER VICTOR OCSA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: MINERAÇÃO DE DADOS; FRACTAIS (TEORIA); BANCO DE DADOS
- Keywords: Busca ao vizinho mais próximo; Busca por similaridade aproximada; Complex data; CUDA; CUDA; Dados complexos; Data mining; Descoberta der motifs; GPGPU; GPGPU; Mineração de dados; Motif-discovery; Nearest neighbor search; Projeção aleatória; Random projection; Similarity serach
- Language: Português
- Abstract: A crescente disponibilidade de dados em diferentes domínios tem motivado o desenvolvimento de técnicas para descoberta de conhecimento em grandes volumes de dados complexos. Trabalhos recentes mostram que a busca em dados complexos é um campo de pesquisa importante, já que muitas tarefas de mineração de dados, como classificação, detecção de agrupamentos e descoberta de motifs, dependem de algoritmos de busca ao vizinho mais próximo. Para resolver o problema da busca dos vizinhos mais próximos em domínios complexos muitas abordagens determinísticas têm sido propostas com o objetivo de reduzir os efeitos da maldição da alta dimensionalidade. Por outro lado, algoritmos probabilísticos têm sido pouco explorados. Técnicas recentes relaxam a precisão dos resultados a fim de reduzir o custo computacional da busca. Além disso, em problemas de grande escala, uma solução aproximada com uma análise teórica sólida mostra-se mais adequada que uma solução exata com um modelo teórico fraco. Por outro lado, apesar de muitas soluções exatas e aproximadas de busca e mineração terem sido propostas, o modelo de programação em CPU impõe restrições de desempenho para esses tipos de solução. Uma abordagem para melhorar o tempo de execução de técnicas de recuperação e mineração de dados em várias ordens de magnitude é empregar arquiteturas emergentes de programação paralela, como a arquitetura CUDA. Neste contexto, este trabalho apresenta uma proposta para buscas kNN de alto desempenho baseadanuma técnica de hashing e implementações paralelas em CUDA. A técnica proposta é baseada no esquema LSH, ou seja, usa-se projeções em subespaços. O LSH é uma solução aproximada e tem a vantagem de permitir consultas de custo sublinear para dados em altas dimensões. Usando implementações massivamente paralelas melhora-se tarefas de mineração de dados. Especificamente, foram desenvolvidos soluções de alto desempenho para algoritmos de descoberta de motifs baseados em implementações paralelas de consultas kNN. As implementações massivamente paralelas em CUDA permitem executar estudos experimentais sobre grandes conjuntos de dados reais e sintéticos. A avaliação de desempenho realizada neste trabalho usando GeForce GTX470 GPU resultou em um aumento de desempenho de até 7 vezes, em média sobre o estado da arte em buscas por similaridade e descoberta de motifs
- Imprenta:
- Publisher place: São Carlos
- Date published: 2011
- Data da defesa: 22.09.2011
-
ABNT
MAMANI, Alexander Victor Ocsa. Soluções aproximadas para algoritmos escaláveis de mineração de dados em domínios de dados complexos usando GPGPU. 2011. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2011. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-22112011-132339/. Acesso em: 29 maio 2024. -
APA
Mamani, A. V. O. (2011). Soluções aproximadas para algoritmos escaláveis de mineração de dados em domínios de dados complexos usando GPGPU (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-22112011-132339/ -
NLM
Mamani AVO. Soluções aproximadas para algoritmos escaláveis de mineração de dados em domínios de dados complexos usando GPGPU [Internet]. 2011 ;[citado 2024 maio 29 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-22112011-132339/ -
Vancouver
Mamani AVO. Soluções aproximadas para algoritmos escaláveis de mineração de dados em domínios de dados complexos usando GPGPU [Internet]. 2011 ;[citado 2024 maio 29 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-22112011-132339/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
