Operação de busca exata aos k-vizinhos mais próximos reversos em espaços métricos

• Processo: 07/02158-0
• Linha de fomento: Bolsas no Brasil - Mestrado
• Vigência (Início): 01 de outubro de 2007
• Vigência (Término): 30 de novembro de 2008
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: Caetano Traina Junior
• Beneficiário: Willian Dener de Oliveira
• Instituição-sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Bases de dados Consultas por similaridade

Resumo

A complexidade dos dados armazenados em grandes bases de dados aumenta cada vez mais, criando a necessidade de novas operações de consulta. Uma classe de operações que tem apresentado interesse crescente são as chamadas Consultas por Similaridade, sendo as mais conhecidas as consultas por Abrangência (Rq) e por k-Vizinhos mais Próximos (kNNq), sendo que esta última obtém quais são os k elementos armazenados mais similares a um dado elemento de referência.Uma outra consulta que é interessante tanto para consultas diretas quanto como parte de operações de análises mais complexas é a operação de consulta aos k-Vizinhos mais Próximos Reversos (RkNNq). Seu objetivo é obter todos os elementos armazenados que têm um dado elemento de referência como um dos seus k elementos mais similares.Devido á complexidade de execução da operação de RkNNq, a grande maioria das soluções existentes restringem-se a dados representados em espaços multi-dimensionais Euclidianos (nos quais estão definidas também operações cardinais e topológicas, além de se considerar a similaridade como sendo a distância Euclidiana entre dois elementos), ou então obtêm apenas respostas aproximadas, sujeitas à existência de falsos negativos.Várias aplicações de análise de dados científicos, médicos, de engenharia, financeiros, etc. requerem soluções eficientes para o problema da operação de RkNNq sobre dados representados em espaços métricos, onde os elementos não podem ser considerados estar em um espaço nem Euclidiano nem multi-dimensional. Num espaço métrico, além dos próprios elementos armazenados existe apenas uma função de comparação métrica entre pares de objetos. Este Projeto de Mestrado visa desenvolver uma técnica para obter a resposta exata de operações de consulta aos k-Vizinhos mais Próximos Reversos em Espaços Métricos, utilizando métodos de acesso métrico que permitam podas no espaço de busca e permitam uma execução eficiente.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

OLIVEIRA, Willian Dener de. Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos. 2010. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação São Carlos.