In Relational Algebra, the operator Division (÷) is an intuitive tool used to write queries with the concept of for all, and thus, it is constantly required in real applications. However, as we demonstrate in this MSc work, the division does not support many of the needs common to modern applications, particularly those that involve complex data analysis, such as processing images, audio, genetic data, large graphs, fingerprints, and many other non-traditional data types. The main issue is the existence of intrinsic comparisons of attribute values in the operator, which, by definition, are always performed by identity (=), despite the fact that complex data must be compared by similarity. Recent works focus on supporting similarity comparison in relational operators, but no one treats the division. MSc work proposes the new Similarity-aware Division (÷) operator. Our novel operator is naturally well suited to answer queries with an idea of candidate elements and exigencies to be performed on complex data from real applications of high-impact. For example, it is potentially useful to support agriculture, genetic analyses, digital library search, and even to help controlling the quality of manufactured products and identifying new clients in industry. We validate our proposal by studying the first two of these applications. / O operador de Divisão (÷) da Álgebra Relacional permite representar de forma simples consultas com o conceito de para todos, e por isso é requerido em diversas aplicações reais. Entretanto, evidencia-se neste trabalho de mestrado que a divisão não atende às necessidades de diversas aplicações atuais, principalmente quando estas analisam dados complexos, como imagens, áudio, textos longos, impressões digitais, entre outros. Analisando o problema verifica-se que a principal limitação é a existência de comparações de valores de atributos intrínsecas à Divisão Relacional, que, por definição, são efetuadas sempre por identidade (=), enquanto objetos complexos devem geralmente ser comparados por similaridade. Hoje, encontram-se na literatura propostas de operadores relacionais com suporte à similaridade de objetos complexos, entretanto, nenhuma trata a Divisão Relacional. Este trabalho de mestrado propõe investigar e estender o operador de Divisão da Álgebra Relacional para melhor adequá-lo às demandas de aplicações atuais, por meio de suporte a comparações de valores de atributos por similaridade. Mostra-se aqui que a Divisão por Similaridade é naturalmente adequada a responder consultas diversas com um conceito de elementos candidatos e exigências descrito na monografia, envolvendo dados complexos de aplicações reais de alto impacto, com potencial por exemplo, para apoiar a agricultura, análises de dados genéticos, buscas em bibliotecas digitais, e até mesmo para controlar a qualidade de produtos manufaturados e a identificação de novos clientes em indústrias. Para validar a proposta, propõe-se estudar as duas primeiras aplicações citadas.

In Relational Algebra, the operator Division (÷) is an intuitive tool used to write queries with the concept of for all, and thus, it is constantly required in real applications. However, as we demonstrate in this MSc work, the division does not support many of the needs common to modern applications, particularly those that involve complex data analysis, such as processing images, audio, genetic data, large graphs, fingerprints, and many other non-traditional data types. The main issue is the existence of intrinsic comparisons of attribute values in the operator, which, by definition, are always performed by identity (=), despite the fact that complex data must be compared by similarity. Recent works focus on supporting similarity comparison in relational operators, but no one treats the division. MSc work proposes the new Similarity-aware Division (÷) operator. Our novel operator is naturally well suited to answer queries with an idea of candidate elements and exigencies to be performed on complex data from real applications of high-impact. For example, it is potentially useful to support agriculture, genetic analyses, digital library search, and even to help controlling the quality of manufactured products and identifying new clients in industry. We validate our proposal by studying the first two of these applications. / O operador de Divisão (÷) da Álgebra Relacional permite representar de forma simples consultas com o conceito de para todos, e por isso é requerido em diversas aplicações reais. Entretanto, evidencia-se neste trabalho de mestrado que a divisão não atende às necessidades de diversas aplicações atuais, principalmente quando estas analisam dados complexos, como imagens, áudio, textos longos, impressões digitais, entre outros. Analisando o problema verifica-se que a principal limitação é a existência de comparações de valores de atributos intrínsecas à Divisão Relacional, que, por definição, são efetuadas sempre por identidade (=), enquanto objetos complexos devem geralmente ser comparados por similaridade. Hoje, encontram-se na literatura propostas de operadores relacionais com suporte à similaridade de objetos complexos, entretanto, nenhuma trata a Divisão Relacional. Este trabalho de mestrado propõe investigar e estender o operador de Divisão da Álgebra Relacional para melhor adequá-lo às demandas de aplicações atuais, por meio de suporte a comparações de valores de atributos por similaridade. Mostra-se aqui que a Divisão por Similaridade é naturalmente adequada a responder consultas diversas com um conceito de elementos candidatos e exigências descrito na monografia, envolvendo dados complexos de aplicações reais de alto impacto, com potencial por exemplo, para apoiar a agricultura, análises de dados genéticos, buscas em bibliotecas digitais, e até mesmo para controlar a qualidade de produtos manufaturados e a identificação de novos clientes em indústrias. Para validar a proposta, propõe-se estudar as duas primeiras aplicações citadas.

It is well-known that the existing theoretical models for outlier detection make assumptions that may not reflect the true nature of outliers in every real application. This dissertation describes an empirical study performed on unsupervised outlier detection using 8 algorithms from the state-of-the-art and 8 datasets that refer to a variety of real-world tasks of practical relevance, such as spotting cyberattacks, clinical pathologies and abnormalities occurring in nature. We present our lowdown on the results obtained, pointing out to the strengths and weaknesses of each technique from the application specialists point of view, which is a shift from the designer-based point of view that is commonly adopted. Many of the techniques had unfeasibly high runtime requirements or failed to spot what the specialists consider as outliers in their own data. To tackle this issue, we propose MetricABOD: a novel ABOD-based algorithm that makes the analysis up to thousands of times faster, still being in average 26% more accurate than the most accurate related work. This improvement is tantamount to practical outlier detection in many real-world applications for which the existing methods present unstable accuracy or unfeasible runtime requirements. Finally, we studied two collections of text data to show that our MetricABOD works also for adimensional, purely metric data. / É conhecido e notável que os modelos teóricos existentes empregados na detecção de outliers realizam assunções que podem não refletir a verdadeira natureza dos outliers em cada aplicação. Esta dissertação descreve um estudo empírico sobre detecção de outliers não-supervisionada usando 8 algoritmos do estado-da-arte e 8 conjuntos de dados que foram extraídos de uma variedade de tarefas do mundo real de relevância prática, tais como a detecção de ataques cibernéticos, patologias clínicas e anormalidades naturais. Apresentam-se considerações sobre os resultados obtidos, apontando os pontos positivos e negativos de cada técnica do ponto de vista do especialista da aplicação, o que representa uma mudança do embasamento rotineiro no ponto de vista do desenvolvedor da técnica. A maioria das técnicas estudadas apresentou requerimentos de tempo impraticáveis ou falhou em encontrar o que os especialistas consideram como outliers nos conjuntos de dados confeccionados por eles próprios. Para lidar-se com esta questão, foi desenvolvido o método MetricABOD: um novo algoritmo baseado no ABOD que torna a análise milhares de vezes mais veloz, sendo ainda em média 26% mais acurada do que o trabalho relacionado mais acurado. Esta melhoria equivale a tornar a busca por outliers uma tarefa factível em muitas aplicações do mundo real para as quais os métodos existentes apresentam resultados instáveis ou requerimentos de tempo impassíveis de realização. Finalmente, foram também estudadas duas coleções de dados adimensionais para mostrar que o novo MetricABOD funciona também para dados puramente métricos.

Made available in DSpace on 2016-06-02T19:06:16Z (GMT). No. of bitstreams: 1 6270.pdf: 1934927 bytes, checksum: f1e2441b9a2d898dfdbfdefc98c82a23 (MD5) Previous issue date: 2014-03-14 / Universidade Federal de Sao Carlos / Complex data, like images, face semantic problems in your queries that might compromise results quality. Such problems have their source on the differences found between the semantic interpretation of the data and its low level machine language. In this representation are utilized feature vectors that describe intrinsic characteristics (like color, shape and texture) into qualifying attributes. Analyzing the similarity in complex data, perceives that these intrinsic characteristics complemented the representation of data, as well as is carried out by human perception and for this reason the use of multiple descriptors tend to improve the ability of discrimination data. In this context, another relevant fact is that in a data set, some subsets may present essential specific intrinsic characteristics to better show their rest of the data elements. Based in such premises, this work proposes the use of boundary conditions to identify these subsets and then use the best descriptor combination balancing for each of these, aiming to decrease the existing semantic gap in similarity queries. Throughout the conducted experiments the use of the proposed technique had better results when compared to use individual descriptor using the same boundary conditions and also using descriptors combination for the whole set without the use of boundary conditions. / Dados complexos, como imagens, enfrentam problemas semânticos em suas consultas que comprometem a qualidade dos resultados. Esses problemas são caracterizados pela divergência entre a interpretação semântica desses dados e a forma como são representados computacionalmente em características de baixo nível. Nessa representação são utilizados vetores de características que descrevem características intrínsecas (como cor, forma e textura) em atributos qualificadores. Ao analisar a similaridade em dados complexos percebe-se que essas características intrínsecas se complementam na representação do dado, bem como é realizada pela percepção humana e por este motivo a utilização de múltiplos descritores tende a melhorar a capacidade de discriminação dos dados. Nesse contexto, outro fato relevante é que em um conjunto de dados, alguns subconjuntos podem apresentar características intrínsecas específicas essenciais que melhor evidenciam seus elementos do restante dos dados. Com base nesses preceitos, este trabalho propõe a utilização de condições de contorno para delimitar estes subconjuntos e determinar o melhor balanceamento de múltiplos descritores para cada um deles, com o objetivo de diminuir o gap semântico nas consultas por similaridade. Em todos os experimentos realizados a utilização da técnica proposta sempre apresentou melhores resultados. Em comparação a utilização de descritores individuais com as mesmas condições de contorno e sem condições de contorno, e também a combinação de descritores para o conjunto todo sem a utilização de condições de contorno.

Made available in DSpace on 2014-12-17T14:55:09Z (GMT). No. of bitstreams: 1 DanielSAA_TESE_inicio_pag67.pdf: 3521346 bytes, checksum: 030bba7c8ca800b8151b345676b6759c (MD5) Previous issue date: 2013-03-18 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Currently, one of the biggest challenges for the field of data mining is to perform cluster analysis on complex data. Several techniques have been proposed but, in general, they can only achieve good results within specific areas providing no consensus of what would be the best way to group this kind of data. In general, these techniques fail due to non-realistic assumptions about the true probability distribution of the data. Based on this, this thesis proposes a new measure based on Cross Information Potential that uses representative points of the dataset and statistics extracted directly from data to measure the interaction between groups. The proposed approach allows us to use all advantages of this information-theoretic descriptor and solves the limitations imposed on it by its own nature. From this, two cost functions and three algorithms have been proposed to perform cluster analysis. As the use of Information Theory captures the relationship between different patterns, regardless of assumptions about the nature of this relationship, the proposed approach was able to achieve a better performance than the main algorithms in literature. These results apply to the context of synthetic data designed to test the algorithms in specific situations and to real data extracted from problems of different fields / Atualmente, um dos maiores desafios para o campo de minera??o de dados ? realizar a an?lise de agrupamentos em dados complexos. At? o momento, diversas t?cnicas foram propostas mas, em geral, elas s? conseguem atingir bons resultados dentro de dom?nios espec?ficos, n?o permitindo, dessa maneira, que exista um consenso de qual seria a melhor forma para agrupar dados. Essas t?cnicas costumam falhar por fazer suposi??es nem sempre realistas sobre a distribui??o de probabilidade que modela os dados. Com base nisso, o trabalho proposto neste documento cria uma nova medida baseada no Potencial de Informa??o Cruzado que utiliza pontos representativos do conjunto de dados e a estat?stica extra?da diretamente deles para medir a intera??o entre grupos. A abordagem proposta permite usar todas as vantagens desse descritor de informa??o e contorna as limita??es impostas a ele pela sua pr?pria forma de funcionamento. A partir disso, duas fun??es custo de otimiza??o e tr?s algoritmos foram constru?dos para realizar a an?lise de agrupamentos. Como o uso de Teoria da Informa??o permite capturar a rela??o entre diferentes padr?es, independentemente de suposi??es sobre a natureza dessa rela??o, a abordagem proposta foi capaz de obter um desempenho superior aos principais algoritmos citados na literatura. Esses resultados valem tanto para o contexto de dados sint?ticos desenvolvidos para testar os algoritmos em situa??es espec?ficas quanto em dados extra?dos de problemas reais de diferentes naturezas

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 baseada numa 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 subespac¸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 / The increasing availability of data in diverse domains has created a necessity to develop techniques and methods to discover knowledge from huge volumes of complex data, motivating many research works in databases, data mining and information retrieval communities. Recent studies have suggested that searching in complex data is an interesting research field because many data mining tasks such as classification, clustering and motif discovery depend on nearest neighbor search algorithms. Thus, many deterministic approaches have been proposed to solve the nearest neighbor search problem in complex domains, aiming to reduce the effects of the well-known curse of dimensionality. On the other hand, probabilistic algorithms have been slightly explored. Recently, new techniques aim to reduce the computational cost relaxing the quality of the query results. Moreover, in large-scale problems, an approximate solution with a solid theoretical analysis seems to be more appropriate than an exact solution with a weak theoretical model. On the other hand, even though several exact and approximate solutions have been proposed, single CPU architectures impose limits on performance to deliver these kinds of solution. An approach to improve the runtime of data mining and information retrieval techniques by an order-of-magnitude is to employ emerging many-core architectures such as CUDA-enabled GPUs. In this work we present a massively parallel kNN query algorithm based on hashing and CUDA implementation. Our method, based on the LSH scheme, is an approximate method which queries high-dimensional datasets with sub-linear computational time. By using the massively parallel implementation we improve data mining tasks, specifically we create solutions for (soft) realtime time series motif discovery. Experimental studies on large real and synthetic datasets were carried out thanks to the highly CUDA parallel implementation. Our performance evaluation on GeForce GTX 470 GPU resulted in average runtime speedups of up to 7x on the state-of-art of similarity search and motif discovery solutions

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-05-03T20:33:15Z No. of bitstreams: 1 DissASA.pdf: 6143481 bytes, checksum: ae99305f43474756b358bade1f0bd0c7 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-04T13:50:02Z (GMT) No. of bitstreams: 1 DissASA.pdf: 6143481 bytes, checksum: ae99305f43474756b358bade1f0bd0c7 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-04T13:50:10Z (GMT) No. of bitstreams: 1 DissASA.pdf: 6143481 bytes, checksum: ae99305f43474756b358bade1f0bd0c7 (MD5) / Made available in DSpace on 2017-05-04T13:53:49Z (GMT). No. of bitstreams: 1 DissASA.pdf: 6143481 bytes, checksum: ae99305f43474756b358bade1f0bd0c7 (MD5) Previous issue date: 2016-01-05 / Não recebi financiamento / Context: MDD (Model-Driven Development) is a software development paradigm in which the main artefacts are models, from which source code or other artefacts are generated. Even though MDD allows different views of how to decompose a problem and how to design a software to solve it, this paradigm introduces new challenges related to the input models, transformations and output artefacts. Problem Statement: Thus, software testing is a fundamental activity to reveal defects and improve confidence in the software products developed in this context. Several techniques and testing criteria have been proposed and investigated. Among them, functional testing has been extensively explored primarily in the M2M (Model-to-Model) transformations, while structural testing for M2T (Model-to-Text) transformations still poses challenges and lacks appropriate approaches. Objective: This work aims to to present a proposal for the structural testing of M2T transformations through the characterisation of input models as complex data, templates and output artefacts involved in this process. Method: The proposed approach was organised in five phases. Its strategy proposes that the complex data (grammars and metamodels) are represented by directed hypergraphs, allowing that a combinatorial-based traversal algorithm creates subsets of the input models that will be used as test cases for the M2T transformations. In this perspective, we carried out two exploratory studies with the specific purpose of feasibility analysis of the proposed approach. Results and Conclusion: The evaluation of results from the exploratory studies, through the analysis of some testing coverage criteria, demonstrated the relevance and feasibility of the approach for characterizing complex data for M2T transformations testing. Moreover, structuring the testing strategy in phases enables the revision and adjustment of activities, in addition to assisting the replication of the approach within different applications that make use of the MDD paradigm. / Contexto: O MDD (Model-Driven Development ou Desenvolvimento Dirigido por Modelos) e um paradigma de desenvolvimento de software em que os principais artefatos são os modelos, a partir dos quais o código ou outros artefatos são gerados. Esse paradigma, embora possibilite diferentes visões de como decompor um problema e projetar um software para soluciona-lo, introduz novos desafios, qualificados pela complexidade dos modelos de entrada, as transformações e os artefatos de saída. Definição do Problema: Dessa forma, o teste de software e uma atividade fundamental para revelar defeitos e aumentar a confiança nos produtos de software desenvolvidos nesse contexto. Diversas técnicas e critérios de teste vem sendo propostos e investigados. Entre eles, o teste funcional tem sido bastante explorado primordialmente nas transformações M2M (Model-to-Model ou Modelo para Modelo), enquanto que o teste estrutural em transformações M2T (Model-to-Text ou Modelo para Texto) ainda possui alguns desafios e carência de novas abordagens. Objetivos: O objetivo deste trabalho e apresentar uma proposta para o teste estrutural de transformações M2T, por meio da caracterização dos dados complexos dos modelos de entrada, templates e artefatos de saída envolvidos neste processo. Metodologia: A abordagem proposta foi organizada em cinco fases e sua estratégia propõe que os dados complexos (gramáticas e metamodelos) sejam representados por meio de hipergrafos direcionados, permitindo que um algoritmo de percurso em hipergrafos, usando combinatória, crie subconjuntos dos modelos de entrada que serão utilizados como casos de teste para as transformações M2T. Nesta perspectiva, realizou-se dois estudos exploratórios com propósito específico da analise de viabilidade quanto a abordagem proposta. Resultados: A avaliação dos estudos exploratórios proporcionou, por meio da analise dos critérios de cobertura aplicados, um conjunto de dados que demonstram a relevância e viabilidade da abordagem quanto a caracterização de dados complexos para os testes em transformações M2T. A segmentação das estratégias em fases possibilita a revisão e adequação das atividades do processo, além de auxiliar na replicabilidade da abordagem em diferentes aplicações que fazem uso do paradigma MDD.

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 baseada numa 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 subespac¸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 / The increasing availability of data in diverse domains has created a necessity to develop techniques and methods to discover knowledge from huge volumes of complex data, motivating many research works in databases, data mining and information retrieval communities. Recent studies have suggested that searching in complex data is an interesting research field because many data mining tasks such as classification, clustering and motif discovery depend on nearest neighbor search algorithms. Thus, many deterministic approaches have been proposed to solve the nearest neighbor search problem in complex domains, aiming to reduce the effects of the well-known curse of dimensionality. On the other hand, probabilistic algorithms have been slightly explored. Recently, new techniques aim to reduce the computational cost relaxing the quality of the query results. Moreover, in large-scale problems, an approximate solution with a solid theoretical analysis seems to be more appropriate than an exact solution with a weak theoretical model. On the other hand, even though several exact and approximate solutions have been proposed, single CPU architectures impose limits on performance to deliver these kinds of solution. An approach to improve the runtime of data mining and information retrieval techniques by an order-of-magnitude is to employ emerging many-core architectures such as CUDA-enabled GPUs. In this work we present a massively parallel kNN query algorithm based on hashing and CUDA implementation. Our method, based on the LSH scheme, is an approximate method which queries high-dimensional datasets with sub-linear computational time. By using the massively parallel implementation we improve data mining tasks, specifically we create solutions for (soft) realtime time series motif discovery. Experimental studies on large real and synthetic datasets were carried out thanks to the highly CUDA parallel implementation. Our performance evaluation on GeForce GTX 470 GPU resulted in average runtime speedups of up to 7x on the state-of-art of similarity search and motif discovery solutions