Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-03-17T12:24:22Z No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-04-24T13:10:09Z (GMT) No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-04-24T13:10:17Z (GMT) No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) / Made available in DSpace on 2017-04-24T13:13:58Z (GMT). No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) Previous issue date: 2016-11-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The expansion of different areas of knowledge through many types of information brought the necessity to support complex data (images, sounds, videos, strings, DNA chains, etc.), that do not have a Total Order Relationship and need other management mechanisms, like the contentbased retrieval. In general, they are represented in metric space domains, where we have only the elements and the distances between them. Through the characteristics extracted from them, we perform the similarity search. Considering the necessity to associate temporal information on these data in many applications, this work aims to analyze the temporal evolve of metric data. One alternative for this is embedding them into a multidimensional space to allow trajectories estimates. We studied different methods of embedding and analyzed how this affected the data’s distribution and, consequently, the estimates. Two new methods were purposed to estimate an element’s status on a different time from that available in database, in order to reduce the number of non-relevant elements on search results. These methods are based on radius search reduction (range) and evaluation of retrieved element’s proximity by using an approximation of reverse k- NN. We performed experiments which showed that purposed methods could improve the estimate’s result, that used to be performed only using k-NN searches. / A expansão de diferentes áreas do conhecimento com os diversos tipos de informação tornou necessário o suporte a dados complexos (imagens, sons, vídeos, cadeias de DNA, entre outros), que por não possuírem uma Relação de Ordem Total (ROT), necessitam de outros mecanismos de gerenciamento, como a recuperação por conteúdo. Em geral, esses dados são representados em domínios de espaços métricos, onde apenas se tem os elementos e as distâncias entre eles. Através das características extraídas dos mesmos, realiza-se consultas por similaridade. Considerando a necessidade de associar a informação temporal a esses dados em muitas aplicações, este trabalho visa analisar a evolução temporal dos dados métricos. Para isso, uma alternativa é mapeá-los para um espaço multidimensional, a fim possibilitar a estimativa de trajetórias. Neste trabalho, foram estudados diferentes métodos de mapeamento, sendo também analisado como o mapeamento afetou a distribuição dos mesmos e, por conseguinte, a realização das estimativas. Foram propostos dois novos métodos para estimar o estado de um elemento em um tempo diferente daqueles disponíveis na base de dados, com o objetivo de reduzir no conjunto resposta a quantidade de elementos não relevantes. Os métodos propostos são baseados na redução do raio de consulta na região estimada pela delimitação do raio de consulta (range) e a avaliação da proximidade dos elementos retornados utilizando verificação (aproximação) do k-NN reverso. Foram realizados experimentos que mostraram que os métodos propostos melhoraram o resultado final das estimativas, que anteriormente eram realizadas apenas com consultas aos vizinhos mais próximos.

Atualmente, a Onion-tree [Carélo et al., 2009] é o método de acesso métrico baseado em memória primária mais eficiente para pesquisa por similaridade disponível na literatura. Ela indexa dados complexos por meio da divisão do espaço métrico em regiões (ou seja, subespaços) disjuntas, usando para isso dois pivôs por nó. Para prover uma boa divisão do espaço métrico, a Onion-tree introduz as seguintes características principais: (i) procedimento de expansão, o qual inclui um método de particionamento que controla o número de subespaços disjuntos gerados em cada nó; (ii) técnica de substituição, a qual pode alterar os pivôs de um nó durante operações de inserção baseado em uma política de substituição que garante uma melhor divisão do espaço métrico, independente da ordem de inserção dos elementos; e (iii) algoritmos para a execução de consultas por abrangência e aos k-vizinhos mais próximos, de forma que esses tipos de consulta possam explorar eficientemente o método de particionamento da Onion-tree. Entretanto, a Onion-tree apenas oferece funcionalidades voltadas à inserção dos dados um-a-um em sua estrutura. Ela não oferece, portanto, uma operação de bulk-loading que construa o índice considerando todos os elementos do conjunto de dados de uma única vez. A principal vantagem dessa operação é analisar os dados antecipadamente para garantir melhor particionamento possível do espaço métrico. Com isto, a carga inicial de grandes volumes de dados pode ser melhor realizada usando a operação de bulk-loading. Este projeto de mestrado visa suprir a falta da operação de bulk-loading para a Onion-tree, por meio da proposta de algoritmos que exploram as características intrínsecas desse método de acesso métrico. No total, são propostos três algoritmos de bulk-loading, denominados GreedyBL, SampleBL e HeightBL, os quais utilizam respectivamente as seguintes abordagens: gulosa, amostragem e de estimativa da altura do índice. Testes experimentais realizados sobre conjuntos de dados com volume variando de 2.536 a 102.240 imagens e com dimensionalidade variando de 32 a 117 dimensões mostraram que os algoritmos propostos introduziram vantagens em relação à estrutura criada pelo algoritmo de inserção um-a-um da Onion-tree. Comparado com a inserção um-a-um, o tamanho do índice foi reduzido de 9% até 88%. Em consultas por abrangência, houve redução de 16% até 99% no número de cálculos de distância e de 9% a 99% no tempo gasto em relação à inserção. Em consultas aos k-vizinhos mais próximos, houve redução de 13% a 86% em número de cálculos de distância e de 9% até 63% no tempo gasto / The main-memory Onion-tree [Carélo et al., 2009] is the most efficient metric access method to date. It indexes complex data by dividing the metric space into several disjoint regions (i.e. subspaces) by using two pivots per node. To provide a good division of the metric space, the Onion-tree introduces the following characteristics: (i) expansion procedure, which provides a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) replacement technique, which can replace the pivots of a leaf node during insert operations based on a replacement policy that ensures a better division of the metric space, regardless of the insertion order of the elements; and (iii) algorithms for processing range and k-NN queries, so that these types of query can efficiently use the partitioning method of the Onion-tree. However, the Onion-tree only performs element-by-element insertions into its structure. Another important issue is the mass loading technique, called bulk-loading, which builds the index considering all elements of the dataset at once. This technique is very useful in the case of reconstructing the index or inserting a large number of elements simultaneously. Despite the importance of this technique, to the best of our knowledge, there are not in the literature bulk-loading algorithms for the Onion-tree. In this masters thesis, we fill this gap. We propose three algorithms for bulk-loading Onion-trees: the GreedyBL algorithm, the SampleBL algorithm and the HeightBL algorithm. These algorithms are based on the following approaches, respectively: greedy, sampling and estime height of the index. Performance tests with real-world data with different volumes (ranging from 2,536 to 102,240 images) and different dimensionalities (ranging from 32 to 117 dimensions) showed that the indices produced by the proposed algorithms are very compact. Compared with the element-by-element insertion, the size of the index reduced from 9% up to 88%. The proposed algorithms also provided a great improvement in query processing. They required from 16% up to 99% less distance calculations and were from 9% up to 99% faster than the element-by-element insertion to process range queries. Also, they required from 13% up to 86% less distance calculations and were from 9% up to 63% faster than the element-by-element insertion to process k-NN queries

Os Sistemas de Gerenciamento de Bases de Dados devem atualmente ser capazes de gerenciar dados complexos, como dados multimídia, sequências genéticas, séries temporais, além dos dados tradicionais. Em consultas em grandes coleções de dados complexos, a similaridade entre os dados é o fator mais importante, e pode ser adequadamente expressada quando esses dados são representados em espaços métricos. Independentemente do domínio de um tipo de dados, existem aplicações que devem acompanhar a evolução temporal dos elementos de dados. Porém, os Métodos de Acesso Métrico existentes consideram que os dados são imutáveis com o decorrer do tempo. Visando o tratamento do tempo e dinamicidade em dados representados em espaços métricos, o trabalho apresentado nesta tese foi desenvolvido em duas frentes principais de atividades. A primeira frente tratou da inclusão das operações de remoção e atualização em métodos de acesso métrico, e visa atender às necessidades de domínios de aplicação em que dados em espaços métricos sofram atualização frequente, independentemente de necessitarem de tratamento temporal. Desta frente de atividades também resultou um novo método de otimização de àrvores métricas, baseado no algoritmo de remoção desenvolvido. A segunda frente de atividades aborda a inclusão do conceito de evolução temporal em dados representados em espaços métricos. Para isso foi proposto o Espaço Métrico-temporal, um modelo de representação de dados que permite a comparação de elementos métricos associado a informações temporais. O modelo conta com um método para identificar as contribuições relativas das componentes métrica e temporal no cálculo da similaridade. Também foram apresentadas estratégias para análise de trajetórias de dados métricos com o decorrer do tempo, através da imersão de espaços métrico-temporais em espaços dimensionais. Por fim, foi apresentado um novo método de balanceamento de múltiplos descritores para representação de imagens, fruto de modificações no método proposto para identificar as contribuições das componentes que podem formar um espaço métrico-temporal / Nowadays, the Database Management Systems (DBMS) must be able to manage complex data, such as multimedia data, genetic sequences, temporal series, besides the traditional data. For queries on large collections of complex data, the similarity among elements is the most relevant concept, and it can be adequately expressed when data are represented in metric spaces. Regardless of the data domain, there are applications that must tracking the evolution of data over time However, the existing Metric Access Methods assume that the data elements are immutable. Aiming at both treating time and allowing changes in metric data, the work presented in this thesis consisted of two main parts. The first part addresses the inclusion of the operations for element remotion and updating in metric access methods. These operations are meant to application domains that work with metric data that changes over time, regardless of the needed to manage temporal information. A new method for metric trees optimization was also developed in this part of the work. It was based on the proposed remotion algorithm. The second part of the thesis addresses including the temporal evolution concept in data represented in metric spaces. The Metric-Temporal Space was proposed, a representation model to allow comparing elements consisting of metric data with temporal information associated. The model includes a method to identify the relative contributions of the temporal and the metric components in the final similarity calculation. Strategies for trajectory analysis of metric data over time was also presented, through the immersion of metric-temporal spaced in dimensional spaces. Finally, a new method for weighting multiple image descriptors was presented. It was derived from changes in the proposed method to identify the contributions of the components of the metric-temporal space

This thesis is focused on comparing methods for similarity image retrieval. Common techniques and testing sets are introduced. The testing sets are there to measure the accuracy of the searching systems based on similarity image retrieval. Measurements are done on those models which are implemented on the basis of presented techniques. These measurements examine their results depending on the input data, used components and parameters settings, especially the impact of image resolution on the retrieval precision is examined. These results are analysed and the models are compared. Powered by TCPDF (www.tcpdf.org)

Sistemas de recuperação de imagens por conteúdo (Content-based image retrieval { CBIR) e de classificação dependem fortemente de vetores de características que são extraídos das imagens considerando critérios visuais específicos. É comum que o tamanho dos vetores de características seja da ordem de centenas de elementos. Conforme se aumenta o tamanho (dimensionalidade) do vetor de características, também se aumentam os graus de irrelevâncias e redundâncias, levando ao problema da \"maldição da dimensionalidade\". Desse modo, a seleção das características relevantes é um passo primordial para o bom funcionamento de sistemas CBIR e de classificação. Nesta tese são apresentados novos métodos de seleção de características baseados em algoritmos genéticos (do inglês genetic algorithms - GA), visando o aprimoramento de consultas por similaridade e modelos de classificação. A família Fc (\"Fitness coach\") de funções de avaliação proposta vale-se de funções de avaliação de ranking, para desenvolver uma nova abordagem de seleção de características baseada em GA que visa aprimorar a acurácia de sistemas CBIR. A habilidade de busca de GA considerando os critérios de avaliação propostos (família Fc) trouxe uma melhora de precisão de consultas por similaridade de até 22% quando comparado com métodos wrapper tradicionais para seleção de características baseados em decision-trees (C4.5), naive bayes, support vector machine, 1-nearest neighbor e mineração de regras de associação. Outras contribuições desta tese são dois métodos de seleção de características baseados em filtragem, com aplicações em classificação de imagens, que utilizam o cálculo supervisionado da estatística de silhueta simplificada como função de avaliação: o silhouette-based greedy search (SiGS) e o silhouette-based genetic algorithm search (SiGAS). Os métodos propostos superaram os métodos concorrentes na literatura (CFS, FCBF, ReliefF, entre outros). É importante também ressaltar que o ganho em acurácia obtido pela família Fc, e pelos métodos SiGS e SiGAS propostos proporcionam também um decréscimo significativo no tamanho do vetor de características, de até 90% / Content-based image retrieval (CBIR) and classification systems rely on feature vectors extracted from images considering specific visual criteria. It is common that the size of a feature vector is of the order of hundreds of elements. When the size (dimensionality) of the feature vector is increased, a higher degree of redundancy and irrelevancy can be observed, leading to the \"curse of dimensionality\" problem. Thus, the selection of relevant features is a key aspect in a CBIR or classification system. This thesis presents new methods based on genetic algorithms (GA) to perform feature selection. The Fc (\"Fitness coach\") family of fitness functions proposed takes advantage of single valued ranking evaluation functions, in order to develop a new method of genetic feature selection tailored to improve the accuracy of CBIR systems. The ability of the genetic algorithms to boost feature selection by employing evaluation criteria (fitness functions) improves up to 22% the precision of the query answers in the analyzed databases when compared to traditional wrapper feature selection methods based on decision-tree (C4.5), naive bayes, support vector machine, 1-nearest neighbor and association rule mining. Other contributions of this thesis are two filter-based feature selection algorithms for classification purposes, which calculate the simplified silhouette statistic as evaluation function: the silhouette-based greedy search (SiGS) and the silhouette-based genetic algorithm search (SiGAS). The proposed algorithms overcome the state-of-the-art ones (CFS, FCBF and ReliefF, among others). It is important to stress that the gain in accuracy of the proposed methods family Fc, SiGS and SIGAS is allied to a significant decrease in the feature vector size, what can reach up to 90%

The main focus of my research is to design effective learning techniques for information retrieval and mining in high-dimensional databases. There are two main aspects in the retrieval and mining research: accuracy and efficiency. The accuracy problem is how to return results which can better match the ground truth, and the efficiency problem is how to evaluate users' requests and execute learning algorithms as fast as possible. However, these problems are non-trivial because of the complexity of the high-level semantic concepts, the heterogeneous natures of the feature space, the high dimensionality of data representations and the size of the databases. My dissertation is dedicated to addressing these issues. Specifically, my work has five main contributions as follows. The first contribution is a novel manifold learning algorithm, Local and Global Structures Preserving Projection (LGSPP), which defines salient low-dimensional representations for the high-dimensional data. A small number of projection directions are sought in order to properly preserve the local and global structures for the original data. Specifically, two groups of points are extracted for each individual point in the dataset: the first group contains the nearest neighbors of the point, and the other set are a few sampled points far away from the point. These two point sets respectively characterize the local and global structures with regard to the data point. The objective of the embedding is to minimize the distances of the points in each local neighborhood and also to disperse the points far away from their respective remote points in the original space. In this way, the relationships between the data in the original space are well preserved with little distortions. The second contribution is a new constrained clustering algorithm. Conventionally, clustering is an unsupervised learning problem, which systematically partitions a dataset into a small set of clusters such that data in each cluster appear similar to each other compared with those in other clusters. In the proposal, the partial human knowledge is exploited to find better clustering results. Two kinds of constraints are integrated into the clustering algorithm. One is the must-link constraint, indicating that the involved two points belong to the same cluster. On the other hand, the cannot-link constraint denotes that two points are not within the same cluster. Given the input constraints, data points are arranged into small groups and a graph is constructed to preserve the semantic relations between these groups. The assignment procedure makes a best effort to assign each group to a feasible cluster without violating the constraints. The theoretical analysis reveals that the probability of data points being assigned to the true clusters is much higher by the new proposal, compared to conventional methods. In general, the new scheme can produce clusters which can better match the ground truth and respect the semantic relations between points inferred from the constraints. The third contribution is a unified framework for partition-based dimension reduction techniques, which allows efficient similarity retrieval in the high-dimensional data space. Recent similarity search techniques, such as Piecewise Aggregate Approximation (PAA), Segmented Means (SMEAN) and Mean-Standard deviation (MS), prove to be very effective in reducing data dimensionality by partitioning dimensions into subsets and extracting aggregate values from each dimension subset. These partition-based techniques have many advantages including very efficient multi-phased pruning while being simple to implement. They, however, are not adaptive to different characteristics of data in diverse applications. In this study, a unified framework for these partition-based techniques is proposed and the issue of dimension partitions is examined in this framework. An investigation of the relationships of query selectivity and the dimension partition schemes discovers indicators which can predict the performance of a partitioning setting. Accordingly, a greedy algorithm is designed to effectively determine a good partitioning of data dimensions so that the performance of the reduction technique is robust with regard to different datasets. The fourth contribution is an effective similarity search technique in the database of point sets. In the conventional model, an object corresponds to a single vector. In the proposed study, an object is represented by a set of points. In general, this new representation can be used in many real-world applications and carries much more local information, but the retrieval and learning problems become very challenging. The Hausdorff distance is the common distance function to measure the similarity between two point sets, however, this metric is sensitive to outliers in the data. To address this issue, a novel similarity function is defined to better capture the proximity of two objects, in which a one-to-one mapping is established between vectors of the two objects. The optimal mapping minimizes the sum of distances between each paired points. The overall distance of the optimal matching is robust and has high retrieval accuracy. The computation of the new distance function is formulated into the classical assignment problem. The lower-bounding techniques and early-stop mechanism are also proposed to significantly accelerate the expensive similarity search process. The classification problem over the point-set data is called Multiple Instance Learning (MIL) in the machine learning community in which a vector is an instance and an object is a bag of instances. The fifth contribution is to convert the MIL problem into a standard supervised learning in the conventional vector space. Specially, feature vectors of bags are grouped into clusters. Each object is then denoted as a bag of cluster labels, and common patterns of each category are discovered, each of which is further reconstructed into a bag of features. Accordingly, a bag is effectively mapped into a feature space defined by the distances from this bag to all the derived patterns. The standard supervised learning algorithms can be applied to classify objects into pre-defined categories. The results demonstrate that the proposal has better classification accuracy compared to other state-of-the-art techniques. In the future, I will continue to explore my research in large-scale data analysis algorithms, applications and system developments. Especially, I am interested in applications to analyze the massive volume of online data.

Técnicas de projeção desempenham papel importante na análise e exploração de dados multidimensionais, já que permitem visualizar informações muitas vezes ocultas na alta dimensão. Esta tese explora o potencial destas técnicas para resolver problemas relacionados à: 1) identificação de agrupamentos e 2) busca por similaridade em dados multidimensionais. Para identificação de agrupamentos foi desenvolvida uma técnica de projeção local e interativa que, além de projetar dados com ótima preservação de distâncias, permite que o usuário modifique o layout da projeção, agrupando um número reduzido de amostras representativas no espaço visual, de acordo com suas características. Os mapeamentos produzidos tendem a seguir o layout das amostras organizadas pelo usuário, facilitando a organização dos dados e identificação de agrupamentos. Contudo, nem sempre é possível selecionar ou agrupar amostras com base em suas características visuais de forma confiável, principalmente quando os dados não são rotulados. Para estas situações, um novo método para identificação de agrupamentos baseado em projeção foi proposto, o qual opera no espaço visual, garantindo que os grupos obtidos não fiquem fragmentados durante a visualização. Além disso, é orientado por um mecanismo de amostragem determinístico, apto a identificar instâncias que representam bem o conjunto de dados como um todo e capaz de operar mesmo em conjuntos de dados desbalanceados. Para o segundo problema: busca por similaridade em dados multidimensionais, uma família de métricas baseada em classes foi construída para projetar os dados, com o objetivo de minimizar a dissimilaridade entre pares de objetos pertencentes à mesma classe e, ao mesmo tempo, maximizá-la para objetos pertencentes a classes distintas. As métricas classes-específicas são avaliadas no contexto de recuperação de imagens com base em conteúdo. Com o intuito de aumentar a precisão da família de métricas classes-específicas, outra técnica foi desenvolvida, a qual emprega a teoria dos conjuntos fuzzy para estimar um valor de incerteza que é transferido para a métrica, aumentando sua precisão. Os resultados confirmam a efetividade das técnicas desenvolvidas, as quais representam significativa contribuição na tarefa de identificação de grupos e busca por similaridade em dados multidimensionais. / Projection techniques play an important role in multidimensional data analysis and exploration, since they allow to visualize information frequently hidden in high-dimensional spaces. This thesis explores the potential of those techniques to solve problems related to: 1) clustering and 2) similarity search in multidimensional data. For clustering data, a local and interactive projection technique capable of projecting data with effective preservation of distances was developed. This one allows the user to manipulate a reduced number of representative samples in the visual space so as to better organize them. The final mappings tend to follow the layout of the samples organized by the user, therefore, the user can interactively steer the projection. This makes it easy to organize and group large data sets. However, it is not always possible to select or group samples visually, in a reliable manner, mainly when handling unlabeled data. For these cases, a new clustering method based on multidimensional projection was proposed, which operates in the visual space, ensuring that clusters are not fragmented during the visualization. Moreover, it is driven by a deterministic sampling mechanism, able to identify instances that are good representatives for the whole data set. The proposed method is versatile and robust when dealing with unbalanced data sets. For the second problem: similarity search in multidimensional data, we build a family of class-specific metrics to project data. Such metrics were tailored to minimize the dissimilarity measure among objects from the same class and, simultaneously to maximize the dissimilarity among objects in distinct classes. The class-specific metrics are assessed in the context of content-based image retrieval. With the aim of increasing the precision of the class-specific metrics, another technique was developed. This one, uses the fuzzy set theory to estimate a degree of uncertainty, which is embedded in the metric, increasing its precision. The results confirm the effectiveness of the developed techniques, which represent significant contributions for clustering and similarity search in multidimensional data.

A análise automática da similaridade entre imagens depende fortemente de descritores que consigam caracterizar o conteúdo das imagens em dados compactos e discriminativos. Esses dados extraídos e representados em um vetor-de-características tem o objetivo de representar as imagens nos processos de mineração e análise para classificação e/ou recuperação. Neste trabalho foi explorado o uso de dicionários visuais e contexto para representar e recuperar as características locais das imagens utilizando formalismos estendidos com alto poder descritivo. Esta tese apresenta em destaque três novas propostas que contribuem competitivamente com outros trabalhos da literatura no avanço do estado-da-arte, desenvolvendo novas metodologias para a caracterização de imagens e para o processamento de consultas por similaridade. A primeira proposta estende a modelagem Bag-of-Visual-Words, permitindo codificar a interação entre palavras-visuais e suas disposições espaciais na imagem. Para tal fim, três novas abordagem são apresentadas: (i) Weighted Histogram (WE); (ii) Bunch-of-2-grams e (iii) Global Spatial Arrangement (GSA). Cada uma dessas técnicas permitem extrair informações semanticamente complementares, que enriquecem a representação final das imagens descritas em palavras-visuais. A segunda proposta apresenta um novo descritor, chamado de Bag-of-Salience-Points (BoSP), que caracteriza e analisa a dissimilaridade de formas (silhuetas) de objetos explorando seus pontos de saliências. O descritor BoSP se apoia no uso de um dicionário de curvaturas e em histogramas espaciais para representar sucintamente as saliências de um objeto em um único vetor-de-características de tamanho fixo, permitindo recuperar formas usando funções de distâncias computacionalmente rápidas. Por fim, a terceira proposta apresenta um novo modelo de consulta por similaridade, denominada Similarity Based on Dominant Images (SimDIm), baseada no conceito de Imagens Dominantes, que é um conjunto que representa, de uma maneira mais diversificada e reduzida, toda a coleção de imagens da base de dados. Tal conceito permite dar mais eficiência quando se deseja analisar o contexto da coleção, que é o objetivo da proposta. Os experimentos realizados mostram que os métodos propostos contribuem de maneira efetiva para caracterizar e quantificar a similaridade entre imagens por meio de abordagens estendidas baseadas em dicionários visuais e análise contextual, reduzindo a lacuna semântica existente entre a percepção humana e a descrição computacional. / The automatic similarity analysis between images depends heavily on the use of descriptors that should be able to characterize the images\' content in compact and discriminative features. These extracted features are represented by a feature-vector employed to represent the images in the process of mining and analysis for classification and/or retrieval. This work investigated the use of visual dictionaries and context to represent and retrieve the local image features using extended formalism with high descriptive power. This thesis presents three new proposals that contribute in advancing the state-of-the-art by developing new methodologies for characterizing images and for processing similarity queries by content. The first proposal extends the Bag-of-Visual-Words model, by encoding the interaction between the visual words and their spatial arrangements in the image space. For this, three new techniques are presented: (i) Weighted Histogram (WE); (ii) Bunch-of--grams and (iii) Global Spatial Arrangement (GSA). These three techniques allow to extract additional semantically information that enrich the final image representation described in visual-words. The second proposal introduces a new descriptor, called Bag-of-Salience-Points (BoSP), which characterizes and analyzes the dissimilarity of shapes (silhouettes) exploring their salient point. The BoSP descriptor is based on using a dictionary of curvatures and spatial-histograms to represent succinctly the saliences of a shape into a single fixed-length feature-vector, allowing to retrieve shapes using distance functions computationally fast. Finally, the third proposal introduces a new similarity query model, called Similarity based on Dominant Images (SimDIm), based on the concept of dominant images, which is a set of images representing the entire collection of images of the database in a more diversified and reduced manner. This concept allows to efficiently analyze the context of the entire collection, which is the final goal. The experiments showed that the proposed methods effectively contributed to characterize and quantify the similarity between images using extended approaches based on visual dictionaries and contextual analysis, reducing the semantic gap between human perception and computational description.

Eine Zeitreihe ist eine zeitlich geordnete Folge von Datenpunkten. Zeitreihen werden typischerweise über Sensormessungen oder Experimente erfasst. Sensoren sind so preiswert geworden, dass sie praktisch allgegenwärtig sind. Während dadurch die Menge an Zeitreihen regelrecht explodiert, lag der Schwerpunkt der Forschung in den letzten Jahrzehnten auf der Analyse von (a) vorgefilterten und (b) kleinen Zeitreihendatensätzen. Die Analyse realer Zeitreihendatensätze wirft zwei Probleme auf: Erstens setzen aktuelle Ähnlichkeitsmodelle eine Vorfilterung der Zeitreihen voraus. Das beinhaltet die Extraktion charakteristischer Teilsequenzen und das Entfernen von Rauschen. Diese Vorverarbeitung muss durch einen Spezialisten erfolgen. Sie kann zeit- und kostenintensiver als die anschließende Analyse und für große Datensätze unrentabel werden. Zweitens führte die Verbesserung der Genauigkeit aktueller Ähnlichkeitsmodelle zu einem unverhältnismäßig hohen Anstieg der Komplexität (quadratisch bis biquadratisch). Diese Dissertation behandelt beide Probleme. Es wird eine symbolische Zeitreihenrepräsentation vorgestellt. Darauf aufbauend werden drei verschiedene Ähnlichkeitsmodelle eingeführt. Diese erweitern den aktuellen Stand der Forschung insbesondere dadurch, dass sie vorverarbeitungsfrei, unempfindlich gegenüber Rauschen und skalierbar sind. Anhand von 91 realen Datensätzen und Benchmarkdatensätzen wird zusätzlich gezeigt, dass die hier eingeführten Modelle auf den meisten Datenätzen die höchste Genauigkeit im Vergleich zu 15 aktuellen Ähnlichkeitsmodellen liefern. Sie sind teilweise drei Größenordnungen schneller und benötigen kaum Vorfilterung. / A time series is a collection of values sequentially recorded from sensors or live observations over time. Sensors for recording time series have become cheap and omnipresent. While data volumes explode, research in the field of time series data analytics has focused on the availability of (a) pre-processed and (b) moderately sized time series datasets in the last decades. The analysis of real world datasets raises two major problems: Firstly, state-of-the-art similarity models require the time series to be pre-processed. Pre-processing aims at extracting approximately aligned characteristic subsequences and reducing noise. It is typically performed by a domain expert, may be more time consuming than the data mining part itself, and simply does not scale to large data volumes. Secondly, time series research has been driven by accuracy metrics and not by reasonable execution times for large data volumes. This results in quadratic to biquadratic computational complexities of state-of-the-art similarity models. This dissertation addresses both issues by introducing a symbolic time series representation and three different similarity models. These contribute to state of the art by being pre-processing-free, noise-robust, and scalable. Our experimental evaluation on 91 real-world and benchmark datasets shows that our methods provide higher accuracy for most datasets when compared to 15 state-of-the-art similarity models. Meanwhile they are up to three orders of magnitude faster, require less pre-processing for noise or alignment, or scale to large data volumes.

Os volumes de dados armazenados em grandes bases de dados aumentam em ritmo sempre crescente, pressionando o desempenho e a flexibilidade dos Sistemas de Gerenciamento de Bases de Dados (SGBDs). Os problemas de se tratar dados em grandes quantidades, escopo, complexidade e distribuição vêm sendo tratados também sob o tema de big data. O aumento da complexidade cria a necessidade de novas formas de busca - representar apenas números e pequenas cadeias de caracteres já não é mais suficiente. Buscas por similaridade vêm se mostrando a maneira por excelência de comparar dados complexos, mas até recentemente elas não estavam disponíveis nos SGBDs. Agora, com o início de sua disponibilidade, está se tornando claro que apenas os operadores de busca por similaridade fundamentais não são suficientes para lidar com grandes volumes de dados. Um dos motivos disso é que similaridade\' é, usualmente, definida considerando seu significado quando apenas poucos estão envolvidos. Atualmente, o principal foco da literatura em big data é aumentar a eficiência na recuperação dos dados usando paralelismo, existindo poucos estudos sobre a eficácia das respostas obtidas. Esta tese visa propor e desenvolver variações dos operadores de busca por similaridade para torná-los mais adequados para processar big data, apresentando visões mais abrangentes da base de dados, aumentando a eficácia das respostas, porém sem causar impactos consideráveis na eficiência dos algoritmos de busca e viabilizando sua execução escalável sobre grandes volumes de dados. Para alcançar esse objetivo, este trabalho apresenta quatro frentes de contribuições: A primeira consistiu em um modelo de diversificação de resultados que pode ser aplicado usando qualquer critério de comparação e operador de busca por similaridade. A segunda focou em definir técnicas de amostragem e de agrupamento de dados com o modelo de diversificação proposto, acelerando o processo de análise dos conjuntos de resultados. A terceira contribuição desenvolveu métodos de avaliação da qualidade dos conjuntos de resultados diversificados. Por fim, a última frente de contribuição apresentou uma abordagem para integrar os conceitos de mineração visual de dados e buscas por similaridade com diversidade em sistemas de recuperação por conteúdo, aumentando o entendimento de como a propriedade de diversidade pode ser aplicada. / The data being collected and generated nowadays increase not only in volume, but also in complexity, requiring new query operators. Health care centers collecting image exams and remote sensing from satellites and from earth-based stations are examples of application domains where more powerful and flexible operators are required. Storing, retrieving and analyzing data that are huge in volume, structure, complexity and distribution are now being referred to as big data. Representing and querying big data using only the traditional scalar data types are not enough anymore. Similarity queries are the most pursued resources to retrieve complex data, but until recently, they were not available in the Database Management Systems. Now that they are starting to become available, its first uses to develop real systems make it clear that the basic similarity query operators are not enough to meet the requirements of the target applications. The main reason is that similarity is a concept formulated considering only small amounts of data elements. Nowadays, researchers are targeting handling big data mainly using parallel architectures, and only a few studies exist targeting the efficacy of the query answers. This Ph.D. work aims at developing variations for the basic similarity operators to propose better suited similarity operators to handle big data, presenting a holistic vision about the database, increasing the effectiveness of the provided answers, but without causing impact on the efficiency on the searching algorithms. To achieve this goal, four mainly contributions are presented: The first one was a result diversification model that can be applied in any comparison criteria and similarity search operator. The second one focused on defining sampling and grouping techniques with the proposed diversification model aiming at speeding up the analysis task of the result sets. The third contribution concentrated on evaluation methods for measuring the quality of diversified result sets. Finally, the last one defines an approach to integrate the concepts of visual data mining and similarity with diversity searches in content-based retrieval systems, allowing a better understanding of how the diversity property is applied in the query process.