Operadores físicos binários para consultas por similaridade em SGBDR (2018)
- Authors:
- Autor USP: CARVALHO, LUIZ OLMES - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: MINERAÇÃO DE DADOS; ANÁLISE DE DADOS; BANCO DE DADOS; BANCO DE DADOS RELACIONAIS
- Keywords: Junção por similaridade; kNN; kNN; Operadores relacionais; QuickNearest; QuickNearest; Relational operators; Similarity join; Wide-join; Wide-join
- Agências de fomento:
- Language: Português
- Abstract: 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. Osexperimentos 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.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2018
- Data da defesa: 26.03.2018
-
ABNT
CARVALHO, Luiz Olmes. Operadores físicos binários para consultas por similaridade em SGBDR. 2018. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16102018-105516/. Acesso em: 25 jan. 2026. -
APA
Carvalho, L. O. (2018). Operadores físicos binários para consultas por similaridade em SGBDR (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16102018-105516/ -
NLM
Carvalho LO. Operadores físicos binários para consultas por similaridade em SGBDR [Internet]. 2018 ;[citado 2026 jan. 25 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16102018-105516/ -
Vancouver
Carvalho LO. Operadores físicos binários para consultas por similaridade em SGBDR [Internet]. 2018 ;[citado 2026 jan. 25 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16102018-105516/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
