O operador de agrupamento e as funções de agregação são as principais ferramentas utilizadas para sumarizar dados em um Sistema de Gerenciamento de Base de Dados Relacionais (SGBDR). O operador de agrupamento funciona criando partições nos dados utilizando comparações por identidade, e permite que sejam aplicadas funções de agregação que retornam um único valor representando o grupo como um todo. Entretanto, para dados métricos, agrupamento utilizando identidade tem pouca utilidade. Neste caso, adotar o conceito de similaridade é frequentemente uma abordagem mais promissora. A literatura apresenta alguns operadores que podem agrupar os dados utilizando similaridade. Todos eles utilizam um limiar de valor de distância para atribuir os elementos aos grupos. No entanto, estes operadores não obtêm resultados satisfatórios quando a distribuição dos dados apresenta variações significativas na densidade de objetos em diferentes regiões do espaço. Para alcançar melhores resultados nestas situações, propusemos um novo operador que atribui os grupos utilizando uma eleição envolvendo grupos já atribuídos. Também propusemos generalizações, para os operadores existentes e propostos, para trabalhar com uma quantidade de vizinhos mais próximos e aproximação dos vizinhos mais próximos ao invés de um limiar de distância. Para possibilitar a inclusão destes operadores em SGBDR, propusemos uma extensão à Structured Query Language (SQL) e novas funções de agregação. Implementamos estes operadores em nosso framework em C++ usando a biblioteca Arboretum. Para avaliar os métodos propostos, analisamos tanto qualidade dos resultados quanto tempo de execução, utilizando conjuntos de dados reais e sintéticos. Os operadores propostos alcançaram melhores resultados quanto à qualidade de resultados, e mantiveram os tempos de execução similares. Os operadores que utilizam aproximação aos vizinhos mais próximos produziram resultados de qualidade similar quando comparados aos operadores que utilizando os vizinhos mais próximos, podendo ser executados em menor tempo que estes. / The grouping operator and aggregation functions are the primary tools used to summarize data inside a Relational Database Management Systems (RDBMS). The grouping operator works creating partitions in data using identity comparisons, and allow applying aggregation functions that return a single value that represent the entire group. However, for metric data, grouping by identity is seldom useful. In this case, adopting the concept of the similarity is often a better approach. The literature presents few operators that can group data using similarity. All of them use a distance threshold value to assign the elements in groups. However, these operators do not achieve satisfactory results when the data distribution present a significant variation in the density of objects in different regions of the space. To achieve better results in these situations, we have proposed a novel operator that assign groups using an election involving already assigned groups. We also proposed generalizations to existing and proposed operators to work with an amount of nearest neighbors and approximate neighbors instead of a distance threshold. To support these operators in RDBMS, we propose an extension to Structured Query Language (SQL) and new aggregation functions. Our proposed algorithms can run the proposed and existing operators. We implemented these operators in our framework in C++ using Arboretum library. To evaluate the proposed methods, we assess both results quality and the execution time, using both real and synthetic datasets. The proposed operators achieved better results comparing the quality and maintained similar executing time. The operators that use the approximate nearest neighbors produced similar quality results comparing with the operators that use the exact neighbors and can execute faster than that.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-22102018-172305 |
| Date | 16 May 2018 |
| Creators | Laverde, Natan de Almeida |
| Contributors | Traina Junior, Caetano |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0021 seconds