Detalhes bibliográficos
| Ano de defesa: |
2018 |
| Autor(a) principal: |
Carvalho, Luiz Olmes |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Tese
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16102018-105516/
|
Resumo: |
O operador de Junção é um operador importante da Álgebra Relacional que combina os pares de tuplas que atendem a uma dada condição de comparação entre os valores dos atributos de duas relações. Quando a comparação avalia a similaridade entre pares de valores, o operador é chamado Junção por Similaridade. Esse operador tem aplicações em diversos contextos, tais como o suporte de tarefas de mineração e análise de dados em geral, e a detecção de quase-duplicatas, limpeza de dados e casamento de cadeias de caracteres em especial. Dentre os operadores de junção por similaridade existentes, a Junção por Abrangência (range join) é a mais explorada na literatura. Contudo, ela apresenta limitações, tal como a dificuldade para se encontrar um limiar de similaridade adequado. Nesse contexto, a Junção por k-vizinhos mais próximos (knearest neighbor join kNN join) é considerada mais intuitiva, e portanto mais útil que o range join. Entretanto, executar um kNN join é computacionalmente mais caro, o que demanda por abordagens baseadas na técnica de laço aninhado, e as técnicas existentes para a otimização do algoritmo são restritas a um domínio de dados em particular. Visando agilizar e generalizar a execução do kNN join, a primeira contribuição desta tese foi o desenvolvimento do algoritmo QuickNearest, baseado na técnica de divisão e conquista, que é independente do domínio dos dados, independente da função de distância utilizada, e que computa kNNjoins de maneira muito eficiente. Os experimentos realizados apontam que o QuickNearest chega a ser 4 ordens de magnitude mais rápido que os métodos atuais. Além disso, o uso de operadores de junção por similaridade em ambientes relacionais é problemático, principalmente por dois motivos: (i)emgeral o resultado tem cardinalidade muito maior do que o realmente necessário ou esperado pela maioria das aplicações de análise de dados; e (ii) as consultas que os utilizam envolvem também operações de ordenação, embora a ordem seja um conceito não associado à teoria relacional. A segunda contribuição da tese aborda esses dois problemas, tratando os operadores de junção por similaridade existentes como casos particulares de um conjunto mais amplo de operadores binários, para o qual foi definido o conceito de Wide-joins. Os operadores wide-joins recuperam os pares mais similares em geral e incorporam a ordenação como uma operação interna ao processamento, de forma compatível com a teoria relacional e que permite restringir a cardinalidade dos resultados a tuplas de maior interesse para as aplicações. Os experimentos realizados mostram que os wide-joins são rápidos o suficiente para serem usados em aplicações reais, retornam resultados de qualidade melhor do que os métodos concorrentes e são mais adequados para execução num ambiente relacional do que os operadores de junção por similaridade tradicionais. |
