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.

Due to the increasing amount and complexity of data processed in real world applications, similarity search became a vital task to store and retrieve such data. However, missing attribute values are very frequent and metric access methods (MAMs), designed to support similarity search, do not operate on datasets when attribute values are missing. Currently, the approach to use the existing indexing techniques on datasets with missing attribute values just use an indicator to identify the missing values and employ a traditional indexing technique. Although, this approach can be applied over multidimensional indexing techniques, it is impractical for metric access methods. This dissertation presents the results of a research conducted to identify and deal with the issues related to indexing and querying datasets with missing values in metric spaces. An empirical analysis of the metric access methods when applied on incomplete datasets leads us to identify two main issues: distortion of the internal structure of the index when data are missing at random and skew of the index structure when data are not missing at random. Based on those findings, a new variant of the Slim-tree access method, called Hollow-tree, is presented. It employs new techniques that are capable to handle missing data issues when missingness is ignorable. The first technique includes a set of indexing policies that allow to index objects with missing attribute values and prevent distortions to occur in the internal structure of the indexes. The second technique targets the similarity queries to improve the query performance over incomplete datasets. This technique employs the fractal dimension of the dataset and the local density around the query object to estimate an ideal radius able to achieve an accurate query answer, considering data with missing values as a potential response. Results from experiments with a variety of real and synthetic datasets show that Hollow-tree achieves nearly 100% of precision and recall for Range queries and more than 90% for k Nearest Neighbor queries, while Slim-tree access method deteriorates with the increasing amount of missing values. The results confirm that the indexing technique helps to establish consistency in the index structure and the searching technique achieves a remarkable performance. When combined, the new techniques allow to explore properly all the available data even with high amounts of missing attribute values. As they are independent of the underlying access method, they can be adopted by a broad range of metric access methods, allowing to extend the class of MAMs. / O crescimento em quantidade e complexidade dos dados processados e armazenados torna a busca por similaridade uma tarefa fundamental para tratar esses dados. No entanto, atributos faltantes ocorrem freqüentemente, inviabilizando os métodos de acesso métricos (MAMs) projetados para apoiar a busca por similaridade. Assim, técnicas de tratamento de dados faltantes precisam ser desenvolvidas. A abordagem mais comum para executar as técnicas de indexação existentes sobre conjuntos de dados com valores faltantes é usar um indicador de valores faltantes e usar as técnicas de indexação tradicionais. Embora, esta técnica seja útil para os métodos de indexação multidimensionais, é impraticável para os métodos de acesso métricos. Esta dissertação apresenta os resultados da pesquisa realizada para identificar e lidar com os problemas de indexação e recuperação de dados em espaços métricos com valores faltantes. Uma análise experimental dos MAMs aplicados a conjuntos de dados incompletos identificou dois problemas principais: distorção na estrutura interna do índice quando a falta é aleatória e busca tendenciosa na estrutura do índice quando o processo de falta não é aleatório. Uma variante do MAM Slim-tree, chamada Hollow-tree foi proposta com base nestes resultados. A Hollow-tree usa novas técnicas de indexação e de recuperação de dados com valores faltantes quando o processo de falta é aleatório. A técnica de indexação inclui um conjunto de políticas de indexação que visam a evitar distorções na estrutura interna dos índices. A técnica de recuperação de dados melhora o desempenho das consultas por similaridade sobre bases de dados incompletas. Essas técnicas utilizam o conceito de dimensão fractal do conjunto de dados e a densidade local da região de busca para estimar um raio de busca ideal para obter uma resposta mais correta, considerando os dados com valores faltantes como uma resposta potencial. As técnicas propostas foram avaliadas sobre diversos conjuntos de dados reais e sintéticos. Os resultados mostram que a Hollow-tree atinge quase 100% de precisão e revocação para consultas por abrangência e mais de 90% para k vizinhos mais próximos, enquanto a Slim-tree rapidamente deteriora com o aumento da quantidade de valores faltantes. Tais resultados indicam que a técnica de indexação proposta ajuda a estabelecer a consistência na estrutura do índice e a técnica de busca pode ser realizada com um desempenho notável. As técnicas propostas são independentes do MAM básico usado e podem ser aplicadas em uma grande variedade deles, permitindo estender a classe dos MAMs em geral para tratar dados faltantes.

O uso da computação em uma variedade cada vez maior de aplicações fez com que os Sistemas de Gerenciamento de Bases de Dados (SGBD) passassem a ser utilizados para armazenar os mais diversos tipos de dados complexos, como imagens, sons e cadeias de DNA entre outros. Consultas baseadas em relações de ordem total ou igualdade não podem ser aplicadas ou tem aplicações limitadas quando executadas nestes conjuntos de dados. Logo, efetua-se consultas por similaridade baseadas no conteúdo de dados desses tipos. Se tais conjuntos de dados podem ser representados em um espaço métrico, é possível utilizar os Métodos de Acesso Métricos (MAM), como a Slim-Tree, a M-Tree e a DBM-Tree, para otimizar as consultas por similaridade. Porém, os MAM são muito difíceis de compreender e analisar devido à complexidade de suas estruturas. Esta dissertação apresenta um sistema de visualização que permite a inspeção visual da organização e do comportamento de MAM, provendo aos desenvolvedores e administradores de SGBD uma forma rápida e fácil para obter informações essenciais sobre estas estruturas que podem levar a melhorias no desempenho de consultas e outras operações. / The use of computers by an increasing variety of applications led the Database Management Systems (DBMS) to be used to store a wide range of complex data types, such as images, sounds, DNA chains, etc. Queries based on the total order relationship and/or equality can not be applied or have a limited range of applications when performed over these datasets. It is necessary to use similarity queries based on the contents of the data. If these datasets can be represented as metric spaces, it is possible to use the Metric Access Methods (MAM), such as the Slim-Tree, the M-Tree and the DBM-Tree, to optimize similarity queries. However, MAM are very hard to understand and analyze due to their complex structures. This work presents a visualization system that allows the visual inspection of the organization and the behavior of MAM. The usage of this system provides to MAM developers and database administrators, an easy and fast way to acquire information about key aspects of these structures, which can lead to improvements on the performance of queries and other operations.

Shotgun proteomics is a widely known technique for identification of protein and peptide sequences from an "in vitro" sample. A tandem mass spectrometer generates tens of thousands of mass spectra which must be annotated with peptide sequences. For this purpose, the similarity search in a database of theoretical spectra generated from a database of known protein sequences can be utilized. Since the sizes of databases grow rapidly in recent years, there is a demand for utilization of various database indexing techniques. We investigate the capabilities of (non)metric access methods as the database indexing techniques for fast and approximate similarity retrieval in mass spectra databases. We show that the method for peptide sequences identification is more than 100x faster than a sequential scan over the entire database while more than 90% of spectra are correctly annotated with peptide sequences. Since the method is currently suitable for small mixtures of proteins, we also utilize a precursor mass filter as the database indexing technique for complex mixtures of proteins. The precursor mass filter followed by ranking of spectra by a modification of the parametrized Hausdorff distance outperforms state-of-the-art tools in the number of identified peptide sequences and the speed of search. The...

Os sistemas Gerenciadores de Bases de Dados (SGBDs) foram desenvolvidos para manipular domínios de dados numéricos e/ou pequenas seqüencias de caracteres (palavras) e não foram projetados prevendo a manipulação de dados complexos, como por exemplo dados multimídia. Os operadores em domínios de dados que requisitam a relação de ordem têm pouca utilidade para manipular operações que envolvem dados complexos. Uma classe de operadores que se adequa melhor para manipular esses dados são os operadores por similaridade: consulta por abrangência (``range queries') e consulta de vizinhos mais próximos (``k-nearest neighbor queries'). Embora muitos resultados já tenham sido obtidos na elaboração de algoritmos de busca por similaridade, todos eles consideram uma única função para a medida de similaridade, que deve ser universalmente aplicável a todos os pares de elementos do conjunto de dados. Este projeto propõe explorar a possibilidade de trabalhar com estruturas de dados concebidas dentro dos conceitos de dados em domínios métricos, mas que admitam o uso de uma função de distância adaptável, ou seja, que mude para determinados grupos de objetos, dependendo de algumas características universais, e assim permitindo acomodar características que sejam particulares a algumas classes de imagens e não de todo o conjunto delas, classificando as imagens em uma hierarquia de tipos, onde cada tipo está associado a uma função de distância diferente e vetores de características diferentes, todos indexados numa mesma árvore. / The DBMS were developed to manipulate data in numeric domains and short strings, not considering the manipulation of complex data, like multimidia data. The operators em data domain which requests for the total order property have no use to handle complex data. An operator class that fit well to handle this type of data are the similarity operators: range query and nearest neighbor query. Although many results have been shown in research to answer similarity queries, all use only one distance function to measure the similarity, which must be applicable to all pairs of elements of the set. The goal of this work is to explore the possibility of deal with complex data in metric domains, that uses a suitable distance function, that changes its behavior for certain groups of data, depending of some universal features, allowing them to use specific features of some classes of data, not shared for the entire set. This flexibility will allow to reduce the set of useful features of each element in the set individually, relying in the values obtainded for one or few features extracted in first place. This values will guide the others important features to extract from data.

Made available in DSpace on 2016-06-02T19:06:10Z (GMT). No. of bitstreams: 1 5601.pdf: 3183108 bytes, checksum: 0ac17d1e4d1f1556e3258bf2bd169cf2 (MD5) Previous issue date: 2013-08-27 / The Onion-tree is an efficient metric access method based on main memory for similarity search. The Onion-tree has already provided algorithms for insertion and processing of similarity queries (range query and k-nearest neighbors query). However, in the literature no algorithm has been proposed for removing elements in Onion-tree. For this index be incorporated into a database management system, it is necessary the proposal and implementation of at least one algorithm of deletion. This master's research focused primarily on the implementation and performance evaluation of the algorithms proposed for logical deletion in (CARÉLO et al., 2011). The proposal presented in (CARÉLO et al., 2011) led to the implementation of three algorithms, called LogicalDelete, ReplaceReducing and ReplaceGrowing. The first algorithm applies the logic deletion, while the other two algorithms are specializations adding special treatment for the deletion of elements in internal nodes with children exclusively leaf. The ReplaceReducing algorithm allows the reduction of the radius of the node that contains de deleted element. On the other hand, the ReplaceGrowing algorithm allows increasing this radius. In addition, algorithms have been proposed and evaluated for physical deletion that can be applied at any level of the Onion-tree. The algorithm ReorgAll rearranges all the elements in the hierarchy of the node that contains de deleted element, by physically removing the elements and reinserting them using the insertion algorithm, and algorithm PromoteNode, which extends the algorithm ReorgAll, promotes, when exists conditions for such operation, other node to replace the one that contains the deleted element. Experimental evaluation of the algorithms LogicalDelete, ReplaceReducing and ReplaceGrowing showed that the algorithm LogicalDelete is more cost effective than the algorithms ReplaceReducing and ReplaceGrowing in query processing after the deletion of elements. Experimental evaluation of physical removal algorithms showed that the promotion of a node to replace the removed node has advantages over the simple reorganization of the hierarchy of the node that contains the deleted element. Besides presenting lower cost of deletion of elements, the algorithm PromoteNode also outperformed the algorithm ReorgAll in query processing after removing elements. When compared with the logic deletion algorithm, for a large amount of deletion operations, the algorithms ReorgAll and PromoteNode produced performance gain of 21.6% in range query processing. However, in the same comparison, these algorithms have a much higher cost of deletion. / A Onion-tree é um método de acesso métrico eficiente baseado em memória primária para pesquisa por similaridade. Esta estrutura de indexação já provê algoritmos para a inserção de elementos e o processamento de consultas por similaridade dos tipos Range Query (consulta por abrangência) e KNN (consulta aos k-vizinhos mais próximos). Entretanto, ainda não foi proposto na literatura um algoritmo para a remoção de elementos na Onion-tree. Para que a Onion-tree possa ser efetivamente incorporada a um Sistema Gerenciador de Banco de Dados, portanto, é necessário a proposta e a implementação de, pelo menos, um algoritmo de remoção. Esta pesquisa de mestrado se concentrou primeiramente na implementação e na avaliação de desempenho do algoritmo de remoção lógica proposto em (CARÉLO et al., 2011). A proposta feita em (CARÉLO et al., 2011) deu origem à implementação de três algoritmos de remoção lógica, denominados LogicalDelete, ReplaceReducing e ReplaceGrowing. O algoritmo LogicalDelete aplica a remoção lógica, enquanto os algoritmos ReplaceReducing e ReplaceGrowing são especializações da remoção lógica, adicionando tratamento especial para a remoção de elementos em nós internos com filhos exclusivamente folha. O algoritmo ReplaceReducing permite a diminuição do raio do nó que sofreu a remoção. De forma antagônica, o algoritmo ReplaceGrowing permite o aumento deste raio. Adicionalmente, foram propostos e avaliados algoritmos de remoção física que podem ser aplicados em qualquer nível da estrutura da Onion-tree: O algoritmo ReorgAll reorganiza todos os elementos da hierarquia do nó que sofreu a remoção, removendo-os fisicamente e reinserindo-os no índice usando o algoritmo de inserção de elementos; e o algoritmo PromoteNode, o qual estende o algoritmo ReorgAll, promovendo, quando houver condições para tal, outro nó em substituição àquele que sofreu a remoção. Os testes experimentais dos algoritmos de remoção LogicalDelete, ReplaceReducing e ReplaceGrowing mostraram que o algoritmo LogicalDelete tem melhor relação custo/benefício que os algoritmos ReplaceReducing e ReplaceGrowing no processamento de consultas por abrangência após a remoção de elementos. Os testes experimentais dos algoritmos de remoção física mostraram que a promoção de um nó, em substituição ao nó removido, efetuada pelo algoritmo PromoteNode apresenta vantagens em relação a simples reorganização da hierarquia que sofreu a remoção. Além de apresentar menor custo de remoção dos elementos no índice, o algoritmo PromoteNode também apresenta desempenho superior no processamento de consultas por abrangência após a remoção de elementos. Quando comparados com o algoritmo de remoção lógica, para uma grande quantidade de operações de remoção, os algoritmos ReorgAll e PromoteNode produziram melhora de 21,6% no desempenho do processamento de consultas por abrangência. Porém, na mesma comparação, estes algoritmos apresentaram custo de remoção muito maior.

Os sistemas Gerenciadores de Bases de Dados (SGBDs) foram desenvolvidos para manipular domínios de dados numéricos e/ou pequenas seqüencias de caracteres (palavras) e não foram projetados prevendo a manipulação de dados complexos, como por exemplo dados multimídia. Os operadores em domínios de dados que requisitam a relação de ordem têm pouca utilidade para manipular operações que envolvem dados complexos. Uma classe de operadores que se adequa melhor para manipular esses dados são os operadores por similaridade: consulta por abrangência (``range queries') e consulta de vizinhos mais próximos (``k-nearest neighbor queries'). Embora muitos resultados já tenham sido obtidos na elaboração de algoritmos de busca por similaridade, todos eles consideram uma única função para a medida de similaridade, que deve ser universalmente aplicável a todos os pares de elementos do conjunto de dados. Este projeto propõe explorar a possibilidade de trabalhar com estruturas de dados concebidas dentro dos conceitos de dados em domínios métricos, mas que admitam o uso de uma função de distância adaptável, ou seja, que mude para determinados grupos de objetos, dependendo de algumas características universais, e assim permitindo acomodar características que sejam particulares a algumas classes de imagens e não de todo o conjunto delas, classificando as imagens em uma hierarquia de tipos, onde cada tipo está associado a uma função de distância diferente e vetores de características diferentes, todos indexados numa mesma árvore. / The DBMS were developed to manipulate data in numeric domains and short strings, not considering the manipulation of complex data, like multimidia data. The operators em data domain which requests for the total order property have no use to handle complex data. An operator class that fit well to handle this type of data are the similarity operators: range query and nearest neighbor query. Although many results have been shown in research to answer similarity queries, all use only one distance function to measure the similarity, which must be applicable to all pairs of elements of the set. The goal of this work is to explore the possibility of deal with complex data in metric domains, that uses a suitable distance function, that changes its behavior for certain groups of data, depending of some universal features, allowing them to use specific features of some classes of data, not shared for the entire set. This flexibility will allow to reduce the set of useful features of each element in the set individually, relying in the values obtainded for one or few features extracted in first place. This values will guide the others important features to extract from data.