Search

The objective of our study was to provide practical directions on the storage of genomic information and novel phenotypes (treated here as unstructured data) using a non-relational database. The MongoDB technology was assessed for this purpose, enabling frequent data transactions involving numerous individuals under genetic evaluation. Our study investigated different genomic (Illumina Final Report, PLINK, 0125, FASTQ, and VCF formats) and phenotypic (including media files) information, using both real and simulated datasets. Advantages of our centralized database concept include the sublinear running time for queries after increasing the number of samples/markers exponentially, in addition to the comprehensive management of distinct data formats while searching for specific genomic regions. A comparison of our non-relational and generic solution, with an existing relational approach (developed for tabular data types using 2 bits to store genotypes), showed reduced importing time to handle 50M SNPs (PLINK format) achieved by the relational schema. Our experimental results also reinforce that data conversion is a costly step required to manage genomic data into both relational and non-relational database systems, and therefore, must be carefully treated for large applications.

Data analysis is increasingly being used as an unbiased and accurate way to evaluate many aspects of society and their evolution over the years. This article presents an analysis of student’s characteristics, between 2012 and 2017, in the most important exam for entry into higher education in Brazil, the Exame Nacional do Ensino Médio (ENEM). The intention is to gain insights of Brazilian regions, ENEM’s areas of knowledge, type of school and accessibility, using a clustering method (K-means). An extensive and careful cleaning of the database was made in order to homogenize it and avoid types of statistical bias. The results of this work are presented objectively in the article, so it may be useful and used as a numerical base in works of socio-educational disciplines or studies that are interested in better understanding the evolution of ENEM in recent years. Finally, some discussions and restrictions on grouping results were presented in a timely manner.

Complex networks are commonly used to model urban street networks, which allows aiding the analysis of criminal activities in cities. Despite several works focusing on such application, there is a lack of a clear methodology focused in the analysis of crime behavior. In this sense, we propose a methodology for employing complex networks in the analysis of criminality spread within criminal areas of a city. Here, we evaluate synthetic cases of crime propagation concerning real criminal data from the North American city of San Francisco — CA. Our results confirm the effectiveness of our methodology in analyzing the crime behavior by means of criminality spread. Hence, this paper renders further development and planning on public safety in cities.

Clustering data streams is an important task in data mining research. Recently, some algorithms have been proposed to cluster data streams as a whole, but just few of them deal with multivariate data streams. Even so, these algorithms merely aggregate the attributes without touching upon the correlation among them. In order to overcome this issue, we propose a new framework to cluster multivariate data streams based on their evolving behavior over time, exploring the correlations among their attributes by computing the fractal dimension. Experimental results with climate data streams show that the clusters’ quality and compactness can be improved compared to the competing method, leading to the thoughtfulness that attributes correlations cannot be put aside. In fact, the clusters’ compactness are 7 to 25 times better using our method. Our framework also proves to be an useful tool to assist meteorologists in understanding the climate behavior along a period of time.

Anaglyph reversion aims to recover the best possible approximation of a stereo pair of images from an anaglyph. Possible applications include a range of practical situations like enabling visualization of legacy anaglyphs on the Web, saving storage/transmission bandwidth by encoding stereo pairs as anaglyphs before stereo visualization or enabling users to enjoy stereo visualization using any available device. The recovering process faces a challenging issue: the anaglyphic stereo matching. Different from regular stereo images, corresponding pixels in the left and right views of an anaglyph have dissimilar intensity values, lowering photometric consistency and thus turning the usual stereo matching algorithms not suitable. In this work we propose SIRA, an efficient method for anaglyph reversion, introducing a novel approach to find stereo correspondences based on a pixel descriptor developed to deal with anaglyphic photometric differences. The descriptor core idea is to model stereo pairs as time series, extracted from both views of an anaglyph. The series are then compared through a time series matching algorithm, providing a faster, yet accurate, pixels alignment. Occlusions are dealt with using a colorization strategy based on the nearest neighbor search. We evaluate SIRA’s computational efficiency and both objective and subjective image quality on the well-known Middlebury dataset. We also compared SIRA with state of the art related methods. The results show SIRA achieves equivalent image quality while consuming 26 times less computational resources, on average. Therefore, SIRA shows up as an effective and efficient method to convey anaglyph reversion, advantaging the aforementioned applications.

Complex networks are nowadays employed in several applications. Modeling urban street networks is one of them, and in particular to analyze criminal aspects of a city. Several research groups have focused on such application, but until now, there is a lack of a well-defined methodology for employing complex networks in a whole crime analysis process, i.e. from data preparation to a deep analysis of criminal communities. Furthermore, the “toolset” available for those works is not complete enough, also lacking techniques to maintain up-to-date, complete crime datasets and proper assessment measures. In this sense, we propose a threefold methodology for employing complex networks in the detection of highly criminal areas within a city. Our methodology comprises three tasks: (i) Mapping of Urban Crimes; (ii) Criminal Community Identification; and (iii) Crime Analysis. Moreover, it provides a proper set of assessment measures for analyzing intrinsic criminality of communities, especially when considering different crime types. We show our methodology by applying it to a real crime dataset from the city of San Francisco—CA, USA. The results confirm its effectiveness to identify and analyze high criminality areas within a city. Hence, our contributions provide a basis for further developments on complex networks applied to crime analysis.

This paper discuss how to use the clustering analysis to discover and extract useful information from multi-temporal satellite images with low spatial resolution to improve the agricultural monitoring of sugarcane fields. A large database of satellite images and specific software were used to perform the images pre-processing, time series extraction, clustering method applying and data visualization on several steps throughout the analysis process. The pre-processing phase corresponded to an accurate geometric correction, which is a requirement for applications of time series of satellite images such as the agricultural monitoring. Other steps in the analysis process were accomplished by a graphical interface to improve the interaction with the users. Approach validation was done using NDVI images of sugarcane fields because of their economic importance as source of ethanol and as effective alternative to replace fossil fuels and mitigate greenhouse gases emissions. According to the analysis done, the methodology allowed to identify areas with similar agricultural development patterns, also considering different growing seasons for the crops, covering monthly and annual periods. Results confirm that satellite images of low spatial resolution, such as that from the AVHRR/NOAA sensors, can indeed be satisfactorily used to monitor agricultural crops in regional scale.

Crowdsourcing solutions can be helpful to extract information from disaster-related data during crisis management. However, certain information can only be obtained through similarity operations. Some of them also depend on additional data stored in a Relational Database Management System (RDBMS). In this context, several works focus on crisis management supported by data. Nevertheless, none of them provide a methodology for employing a similarity-enabled RDBMS in disaster-relief tasks. To fill this gap, we introduce a methodology together with the Data-Centric Crisis Management (DCCM) architecture, which employs our methods over a similarity-enabled RDBMS. We evaluate our proposal through three tasks: classification of incoming data regarding current events, identifying relevant information to guide rescue teams; filtering of incoming data, enhancing the decision support by removing near-duplicate data; and similarity retrieval of historical data, supporting analytical comprehension of the crisis context. To make it possible, similarity-based operations were implemented within one popular, open-source RDBMS. Results using real data from Flickr show that our proposal is feasible for real-time applications. In addition to high performance, accurate results were obtained with a proper combination of techniques for each task. Hence, we expect our work to provide a framework for further developments on crisis management solutions.

Este trabalho mostra o desenvolvimento de uma Interface de Programação de Aplicativos (Application Program Interface - API) para um gerenciador de dados orientado a objetos. A API é composta por um conjunto de primitivas que integram a definição e a manipulação de objetos em uma representação compatível com uma linguagem de programação orientada a objetos. A definição da API explora os recursos básicos de modelos de dados orientados a objetos e baseia-se nas extensões de um metamodelo baseado em quatro abstrações: classificação, generalização, agregação e composição. O suporte à abstração de classificação com hierarquias em múltiplos níveis é tratado com especial destaque, pois resulta em uma das características predominantes da API: o tratamento homogêneo de tipos e instâncias em tempo de execução, unificando comandos usualmente separados em DDL (Data Definition Language) e DML (Data Manipulation Language). A implementação da API sobre um gerenciador relacional emula um gerenciador de dados orientado a objetos. Os conceitos envolvidos no trabalho de emulação foram aplicados no desenvolvimento de uma versão com núcleo relacional do Gerenciador de Objetos SIRIUS, criando em ambiente experimental, precursor à versão com núcleo nativo desse gerenciador. A API definida neste trabalho é compatível com ambas as versões do Gerenciador SIRIUS, permitindo que uma aplicação utilize qualquer uma das versões sem alterações em seu código fonte. Para exemplificar a utilização prática da API, foi implementado um utilitário de bases de dados destinado à representação de modelagens baseadas no modelo de dados SIRIUS usando a versão relacional do Gerenciador de Objetos SIRIUS. Esse utilitário, além de demonstrar a utilização da API, demonstra também como as operações típicas da DDL e da DML são integradas em um único conjunto de comandos que não faz diferença entre a definição de tipos e de instâncias.

The dimension of a dataset has major impact on database management, such as indexing and querying processing. The embedding dimension (i.e., the number of attributes of the dataset) usually overestimates the actual contribution of the attributes to the main characteristics of the data, as the typical assumption of uniform distribution and independence between attributes usually does not hold. In fact, due to dependencies and attribute correlations, real data are typically skewed and exhibit intrinsic dimensionality much lower than the embedding dimension. Similarly, the intrinsic dimension can also be applied to improve data stream processing and analysis. Data streams are generated as sequences of events represented by a predetermined number of numerical attributes. Thus, without loss of generality, we can consider events as elements from a dimensional domain. This paper presents a fast, linear algorithm to measure the intrinsic dimension of a data stream on the fly, following its continuously changing behavior. Experimental studies show that the intrinsic dimension can be used to analyze attribute correlations. The results on well-understood datasets closely follow what is expected from the known behavior of the data.

Satellite images time series have been used to study land surface, such as identification of forest, water, urban areas, as well as for meteorological applications. However, for knowledge discovery in large remote sensing databases can be use clustering techniques in multivariate time series. The clustering technique on three-dimensional time series of NDVI, albedo and surface temperature from AVHRR/NOAA satellite images was used, in this study, to map the variability of land use. This approach was suitable to accomplish the temporal analysis of land use. Additionally, this technique can be used to identify and analyze dynamics of land use and cover being useful to support researches in agriculture, even considering low spatial resolution satellite images. The possibility of extracting time series from satellite images, analyzing them through data mining techniques, such as clustering, and visualizing results in geospatial way is an important advance and support to agricultural monitoring tasks.

The amount of data generated and stored in many domains has increased in the last years. In remote sensing, this scenario of bursting data is not different. As the volume of satellite images stored in databases grows, the demand for computational algorithms that can handle and analyze this volume of data and extract useful patterns has increased. In this context, the computational support for satellite images data analysis becomes essential. In this work, we present the SITSMining framework, which applies a methodology based on data clustering and classification to extract patterns and information from time series obtained from satellite images. In Brazil, as the agricultural production provides great part of the national resources, the analysis of satellite images is a valuable way to help crops monitoring over seasons, which is an important task to the economy of the country. Thus, we apply the framework to analyze multitemporal satellite images, aiming to help crop monitoring and forecasting of Brazilian agriculture.

Research on global warming and climate changes has attracted a huge attention of the scientific community and of the media in general, mainly due to the social and economic impacts they pose over the entire planet. Climate change simulation models have been developed and improved to provide reliable data, which are employed to forecast effects of increasing emissions of greenhouse gases on a future global climate. The data generated by each model simulation amount to Terabytes of data, and demand fast and scalable methods to process them. In this context, we propose a new process of analysis aimed at discriminating between the temporal behavior of the data generated by climate models and the real climate observations gathered from ground-based meteorological station networks. Our approach combines fractal data analysis and the monitoring of real and model-generated data streams to detect deviations on the intrinsic correlation among the time series defined by different climate variables. Our measurements were made using series from a regional climate model and the corresponding real data from a network of sensors from meteorological stations existing in the analyzed region. The results show that our approach can correctly discriminate the data either as real or as simulated, even when statistical tests fail. Those results suggest that there is still room for improvement of the state-of-the-art climate change models, and that the fractal-based concepts may contribute for their improvement, besides being a fast, parallelizable, and scalable approach.

This chapter discusses how to take advantage of computational models to analyze and extract useful information from time series of climate data and remote sensing images. This kind of data has been used for researching on climate changes, as well as to help on improving yield forecasting of agricultural crops and increasing the sustainable usage of the soil. The authors present three techniques based on the Fractal Theory, data streams and time series mining: the FDASE algorithm, to identify correlated attributes; a method that combines intrinsic dimension measurements with statistical analysis, to monitor evolving climate and remote sensing data; and the CLIPSMiner algorithm applied to multiple time series of continuous climate data, to identify relevant and extreme patterns. The experiments with real data show that data mining is a valuable tool to help agricultural entrepreneurs and government on monitoring sugar cane areas, helping to make the production more useful to the country and to the environment.

This paper proposes a new analysis process aimed at discriminating the temporal behavior of the data generated by climate models from the real climate observations gathered from ground-based meteorological stations. Our approach combines fractal data analysis and the monitoring of the real and the model-generated data streams to detect deviations considering the intrinsic correlation among climate time series. Experimental studies showed that our approach can discriminate the data either as real or as generated by a model. Those results suggest that there are yet space to improve the climate change models, and that the fractal-based concepts may contribute in this improvement.

This paper discusses how to take advantage of clustering techniques to analyze and extract useful information from multi-temporal images of low spatial resolution satellites to monitor the sugarcane expansion. Additionally, we introduce the SatImagExplorer system that was developed to automatically extract time series from a huge volume of remote sensing images as well as provide algorithms of clustering analysis and geospatial visualization. According to experiments accomplished with spectral images of sugarcane fields, this proposed approach can be satisfactorily used in crop monitoring.

This paper presents the BBS - Biased Box Sampling algorithm, a technique that combines dimensionality reduction with biased sampling, which aims at keeping the skewed clustering from the original data.

The volume and complexity of data collected by modern applications has grown significantly, leading to increasingly costly operations for both data manipulation and analysis. Sampling is an useful technique to support manager a more sensible volume in the data reduction process. Uniform sampling has been widely used but, in datasets exhibiting skewed cluster distribution, biased sampling shows better results. This paper presents the BBS - Biased Box Samplingalgorithm which aims at keeping the skewed tendency of the clusters from the original data. We also present experimental results obtained with the proposed BBS algorithm.

The problem of identifying meaningful patterns in a database lies at the very heart of data mining. A core objective of data mining processes is the recognition of inter-attribute correlations. Not only are correlations necessary for predictions and classifications --- since rules would fail in the absence of pattern --- but also the identification of groups of mutually correlated attributes expedites the selection of a representative subset of attributes, from which existing mappings allow others to be derived. In this paper, we describe a scalable, effective algorithm to identify groups of correlated attributes. This algorithm can handle non-linear correlations between attributes, and is not restricted to a specific family of mapping functions, such as the set of polynomials. We show the results of our evaluation of the algorithm applied to synthetic and real world datasets, and demonstrate that it is able to spot the correlated attributes. Moreover, the execution time of the proposed technique is linear on the number of elements and of correlations in the dataset.

This paper presents a new approach to support Computer-aided Diagnosis (CAD) aiming at assisting the task of classification and similarity retrieval of mammographic mass lesions, based on shape content. We have tested classical algorithms for automatic segmentation of this kind of image, but usually they are not precise enough to generate accurate contours to allow lesion classification based on shape analyses. Thus, in this work, we have used Zernike moments for invariant pattern recognition within regions of interest (ROIs), without previous segmentation of images. A new data mining algorithm that generates statistical-based association rules is used to identify representative features that discriminate the disease classes of images. In order to minimize the computational effort, an algorithm based on fractal theory is applied to reduce the dimension of feature vectors. K-nearest neighbor retrieval was applied to a database containing images excerpted from previously classified digitalized mammograms presenting breast lesions. The results reveal that our approach allows fast and effective feature extraction and is robust and suitable for analyzing this kind of image.

Data streams are fundamental in several data processing applications involving large amount of data generated continuously as a sequence of events. Frequently, such events are not stored, so the data is analyzed and queried as they arrive and discarded right away. In many applications these events are represented by a predetermined number of numerical attributes. Thus, without loss of generality, we can consider events as elements from a dimensional domain. A sequence of events in a data stream can be characterized by its intrinsic dimension, which in dimensional datasets is usually lower than the embedding dimensionality. As the intrinsic dimension can be used to improve the performance of algorithms handling dimensional data (specially query optimization) measuring it is relevant to improve data streams processing and analysis as well. Moreover, it can also be useful to forecast data behavior. Hence, we present an algorithm able to measure the intrinsic dimension of a data stream on the fly, following its continuously changing behavior. We also present experimental studies, using both real and synthetic data streams, showing that the results on well-understood datasets closely follow what is expected from the known behavior of the data.

This work aims at developing an efficient support for retrieval and classification of medical images, introducing an approach that comprises techniques of image processing, data mining and fractal theory, leading to an effective and direct way to compare images. A method of feature extraction and comparison is proposed, which uses Zernike moments for invariant pattern recognition as shape features of images' regions of interest. A new algorithm that generates statistical-based association rules is used to identify representative features that discriminate the disease classes of images. In order to minimize the computational effort, another new algorithm, based on fractal theory, is applied to reduce the dimensionality of the representative feature space. In essence, the proposed method determines the smallest set of relevant features that can properly represent images without loss of precision. In addition, the method discards the need of image segmentation, leading to a simple but effective way to make image retrieval by content. Experiments executing k-nearest neighbor queries on medical images reveal that the process is robust and suitable to perform retrieval combined with classification of this kind of images.

Normalmente, pesquisas acadêmicas coletam um grande acervo de dados. Esses dados, ao longo do tempo, precisam ser acessados e manipulados pelos pesquisadores, de acordo com a natureza de sua investigação. É fundamental que esses dados estejam disponibilizados de maneira simples, com algum suporte computacional para facilitar o trabalho dos pesquisadores. A realidade da pesquisa, de maneira geral, corresponde a recursos escassos e, portanto, o tempo precisa ser otimizado. O presente trabalho propõe uma possível solução que apoie tarefas de análise e descoberta de conhecimento a partir do acervo do Grupo de Estudos Olímpicos da Universidade de São Paulo, utilizando estratégias de anotação semântica baseada em ontologia, aliada com técnicas de mineração de texto. Para isso, foi desenvolvida uma ontologia de domínio chamada OntOlympic, que serviu de base para o processo de anotação semântica. As entrevistas passaram por um processo de mineração de textos (agrupamentos), com e sem anotação semântica. Os resultados mostram que os grupos formados a partir das entrevistas anotadas tem uma tendência de serem melhores agrupamentos do que os grupos formados pelas entrevistas não anotadas. Os resultados, tanto do índice de avaliação (índice de Davies-Bouldin), quanto da análise dos grupos formados se demonstraram ligeiramente melhores. Como perspectiva futura, outros grupos que trabalham com a mesma dinâmica podem utilizar os processos desse trabalho, além de abrir perspectiva de outros testes na área de mineração de textos. Typically, academic research collects a large body of data. This data, over time, needs to be accessed and manipulated by researchers, according to the nature of their investigation. It is critical that these simple data be available in a computer-supported manner to facilitate the work of researchers. The reality, general, research, scarce resources and therefore time needs the optimization to be. The work proposed by the University of São Paulo is a possible solution and supports the tasks of analysis and knowledge discovery from text mining techniques. For this, an Olympic domain ontology was developed, which served as the basis for the semantic annotation process. The interviews interviewed by a mining mining process (clusters), with and without ananotics. The results show that the groups that form the annotated interviews tend to be better groups than the groups that form the unannotated interviews. The results of both the evaluation index (Davies-Buldin index) and the formed groups compare the best of the analysis. As a future perspective, other test groups that work with the same can use the processes of this work, in addition to opening perspective of other text mining groups.

A disponibilização de grandes volumes de dados em diferentes áreas do conhecimento impulsiona o desenvolvimento de novas técnicas computacionais para processar massivas quantidades de dados, considerando as limitações de recursos disponíveis e tempo. Em particular, há domínios de problemas em que os dados são gerados e recebidos constantemente, sendo necessário realizar um processamento contínuo para que a análise possa refletir, com maior exatidão possível, o contexto atual dos dados. Os desafios inerentes a esse cenário motivam trabalhos na área de descoberta de conhecimento em fluxos de dados, definidos como sequências potencialmente infinitas de dados que são gerados continuamente, em geral em alta velocidade, com uma grande capacidade evolutiva, ou seja, mudanças ocorrem em seu comportamento ao longo do tempo. Dentre as tarefas de descoberta de conhecimento em fluxos de dados, uma das mais abordadas na literatura é o agrupamento, que engloba tanto o agrupamento de pontos (objetos ou itens de dado provenientes de um ou mais fluxos de dados), quanto o agrupamento de fluxos de dados (ou seja, das próprias fontes geradoras dos fluxos). Embora diversos métodos de agrupamento desenvolvidos para fluxos de dados suportem evolução dos dados e adaptação de grupos, eles normalmente não são capazes de rastrear as mudanças ocorridas nos grupos ao longo do tempo. Entender como e quando os grupos mudam, conforme os fluxos de dados são processados, pode gerar conhecimento adicional relevante para o entendimento do problema, como padrões de mudança e sazonalidade. Esse rastreamento das mudanças em agrupamentos é chamado de monitoramento de transições. A maioria dos métodos presentes na literatura foram concebidos para serem usados em bases de dados convencionais com características temporais, sendo poucos os direcionados para tarefas com fluxos de dados, principalmente as que buscam agrupar os fluxos de dados em si. Por isso, no escopo deste trabalho, foi desenvolvido a técnica CETra (Cluster Evolution Tracker) para monitoramento e detecção de transições que leva em consideração as características das tarefas de agrupamento de fluxos de dados. Essa técnica detecta diversos tipos de transições intra e inter grupos, considera a evolução gradual inerente aos fluxos de dados e é aplicável qualquer algoritmo de agrupamento de fluxos de dados que gere grupos disjuntos não sumarizados. CETra possui complexidade de tempo de processamento linear, o que a torna mais eficiente que métodos correlatos da literatura. A avaliação experimental realizada com dados sintéticos e dados reais mostram que a CETra é até duas vezes mais rápida que o método correlato aplicável a agrupamento de fluxos de dados. Além disso, CETra detecta transições que métodos correlatos não conseguem detectar pois esses não consideram a evolução gradual dos dados. Por fim, o estudo com dados reais junto a um algoritmo de agrupamento de fluxos de dados mostra que CETra é capaz de acompanhar o processamento e formação de novos agrupamentos sem impactar significativamente no tempo geral dessa tarefa. The availability of large volumes of data in different areas of knowledge drives the development of new computational techniques to process massive amounts of data, considering limitations of resources and time. In particular, problem domains where data is constantly generated and received, requiring continuous processing so that the analysis can reflect, as accurately as possible, the current context of the data. The challenges inherent to this scenario motivate work in the area of knowledge discovery in data streams, defined as potentially infinite sequences of data that are generated continuously, generally at high speed, with a great evolutionary capacity, that is, changes occur in their behavior over time. Among the knowledge discovery tasks in data streams, one of the most discussed in the literature is clustering, which encompasses both the clustering of streaming data objects (data items coming from one or more data streams) and the clustering of streaming data sources (the sources generating the streams). While many clustering methods developed for data streams supports data evolution and cluster adaptation, they are typically not able to track changes in clusters over time. Understanding how and when clusters change as data streams are processed can generate additional knowledge relevant to understanding the problem, such as changes patterns and seasonality. This detection of changes in clusters is called cluster tracking. Most methods present in literature were designed to be used in conventional databases, with few being directed to data streams tasks, especially those that seek to cluster streaming data sources. Therefore, in the scope of this work, the CETra (Cluster Evolution Tracker) technique was developed for monitoring and detecting transitions, which takes into account characteristics of streaming data sources clustering tasks. This technique detects different types of intra and intercluster transitions, considers data streams gradual evolution, and any streaming data sources clustering algorithm that generates non-summarized disjoint clusters is applicable. CETra has linear processing time complexity, which makes it more efficient than related methods in the literature. The experimental evaluation carried out with synthetic data and real data shows that CETra is twice as fast as the applicable related method. Furthermore, CETra detects transitions that correlated methods cannot detect because they do not consider the gradual evolution of data. Finally, the study with real data together with a streaming data sources clustering algorithm shows that CETra is able to follow processing and formation of new clusters without significantly impacting tasks overall time.

Os avanços na tecnologia proporcionaram o aumento crescente na geração de dados e nos novos tipos de dados, tornando necessário estender os SGBDs para possibilitar armazenar, recuperar e organizar novos tipos de dados como imagens, vídeos e áudios, sendo estes conhecidos como dados complexos. Para as consultas em dados complexos, não é adequado comparar objetos utilizando as relações de Ordem e Identidade, sendo então a opção mais utilizada a comparação por similaridade. Dessa maneira, com a necessidade de desenvolver novos índices para as comparações baseadas em similaridade, surgiram os Métodos de Acesso Métricos (MAMs). Entre as diversas estratégias para indexar os dados, as baseadas em árvore se destacam por possibilitar um equilíbrio entre o tempo de construção do índice e a aceleração da consulta, sendo utilizada junto com a estratégia de árvore, uma estratégia para definir a região dos nós. Entre as diversas estratégias para definir regiões, o raio de cobertura está dentre as mais comumente utilizadas por flexibilizar a posição do objeto na estrutura, possibilitando o controle da ocupação dos nós e a redução no custo da construção da estrutura. Porém, esta estratégia possui o problema da sobreposição de nós, que aumenta o custo para obter as respostas exatas ao realizar as consultas por similaridade. Outra estratégia que não possui o problema da sobreposição, mas que sofre com o alto custo de construção, é a baseada no Diagrama de Voronoi. Buscando reduzir o problema da sobreposição de nós, aumentando o mínimo possível o custo da construção da árvore, neste projeto de mestrado foi proposto o MAM VD-Tree que busca acelerar as consultas por similaridade por meio da redução da sobreposição, obtida com reorganizações baseadas no Diagrama de Voronoi. Resultados experimentais mostraram que o método é capaz de acelerar consultas por similaridade e reduzir a sobreposição de nós na maioria dos casos, em comparação com seu principal competidor, o Slim-Tree. A melhora no tempo gasto ocorre devido ao método criar organizações melhores dos objetos na estrutura e reduzir a sobreposição dos nós, com o custo de criar mais nós para indexar os dados. Advances in the information technology have increased the amount of data generated daily and new types of data, making it necessary to extend DBMS to enable storing, retrieving, and organizing new types of data such as images, videos, and audio, known as complex data. It is not suitable for queries on complex data to compare objects using Order or Identity relations, so comparisons by similarity are the most employed option. With the necessity of developing new indices for comparisons based on similarity, many studies proposed several Metric Access Methods (MAMs). One of the most commonly used strategies to index complex data, tree-based strategies are commonly employed since they maintain a balance between the cost to create the index and the cost to execute the queries. Accordingly, together with the tree strategy, it is necessary to use a strategy to define the region of the nodes. Among the several strategies to define regions, the coverage radius strategy is commonly used to make the objects position in the structure more flexible, making it possible to control the occupation of nodes and reduce the cost of building the structure. However, this strategy has the problem of overlapping nodes, which increases the cost of getting the exact answers when performing similarity queries. Another strategy that does not have the overlap problem but suffers from the high construction cost is based on the Voronoi Diagram. Seeking to reduce the problem of overlapping nodes, increasing as little as possible the cost of constructing the tree, we propose here the VD-Tree MAM to speed up similarity queries by reducing the overlap between nodes, obtained with reorganizations based on the Voronoi Diagram. Experimental results showed that the method could speed up similarity queries with better distributions of the objects in the structure and reduce overlapping nodes in most cases, compared to its main competitor Slim-Tree, with the cost of requiring more nodes to index the data.

O crescente avanço na geração de dados advindos de várias fontes, tornou necessário o desenvolvimento de métodos de apoio aos processos de gerenciamento de grandes quantidades de dados complexos, como imagens, vídeos e áudios. Entretanto, a ocorrência de falhas durante os processos de coleta e armazenamento dos dados devido a diversas causas resultam na incompletude dos bancos de dados, afetando negativamente a execução de consultas por similaridade em inúmeras tarefas de recuperação de informação. Especificamente em consultas por similaridade, as funções de distâncias tradicionais, como a Euclidiana, não medem a dissimilaridade entre pares de atributos com valores faltantes. Abordagens existentes na literatura lidam com o problema de bases de dados incompletos por meio do descarte de tuplas com valores faltantes, a imputação de valores por meio de várias heurísticas e a indexação de bases de dados incompletos. No entanto, a aplicação do descarte de dados pode ocasionar a redução significativa do conjunto de dados, imputações de valores podem introduzir distorções no conjunto de dados e a indexação de dados oferece tratamentos específicos ao tratamento de dados faltante e muitas vezes custoso. O objetivo deste trabalho consiste em extrair informações intrínsecas dos dados para auxiliar na execução de consultas por similaridade sobre bases incompletas, sem o descarte de dados e nem a utilização de um método de imputação de valores. Nesse contexto, este trabalho de mestrado propõe o método SOLID (Search Over Correlated and Incomplete Data), que utiliza a correlação entre pares de espaços métricos definidos por um conjunto de representações para gerar fatores de compatibilidade a partir da identificação de atributos complexos mais correlacionados com relação às ocorrências de objetos com valores faltantes. As consultas por similaridade são executadas por meio de uma função de distância, cuja construção inclui propriedades propostas neste trabalho. Ela aplica os fatores de compatibilidade de acordo com o cenário da falta de dados ocorrida e consolida as distâncias resultantes, reduzindo a influência dos dados faltantes. Uma análise experimental realizada com o SOLID mostra que, para diferentes bases de dados de dimensionalidades e cardinalidades distintas, a correlação entre espaços métricos altamente correlacionados pode auxiliar na redução da influência de dados faltantes ao executar consultas por similaridade. O SOLID é mais de 55% mais preciso do que métodos de imputação ao recuperar tuplas sobre bases que podem até mesmo conter grandes quantidades de dados faltantes (50%), além de executar consultas até 100x mais rápido do que seus concorrentes. The growing advances in data generation from various data sources make it necessary to develop methods to support the management processes of large amounts of complex data, such as images, videos, and audio. However, the occurrence of failures during the data collection and storage processes leads to incompleteness, which negatively affects the execution of similarity queries in numerous information retrieval tasks. Specifically, in similarity queries, traditional distance functions, such as Euclidean, do not measure the dissimilarity between pairs of attributes with missing values. Traditional approaches from literature deal with incomplete databases by discarding tuples with missing values, imputing values using several heuristics, and indexing incomplete databases. However, the application of data deletion can cause a significant reduction of the dataset, and imputations of values can introduce distortions in the dataset. This work aims to extract intrinsic information from the data to help execute similarity queries on incomplete databases without discarding data or using a value imputation method. In this context, this masters dissertation proposes the SOLID (Search Over Correlated and Incomplete Data) method, which uses the correlation between pairs of metric spaces defined by a set of data representations to generate compatibility factors from identifying complex attributes correlated concerning occurrences of objects with missing values. Similarity queries are performed when the distance function proposed in this work is employed, which applies the compatibility factors according to the missing data scenario and consolidates the resulting distances, reducing the missing datas influence. Experimental analysis performed with SOLID shows that, for several databases, the correlation between highly correlated metric spaces can reduce the influence of missing data when executing similarity queries. Thus, SOLID is more than 55% better than imputation methods in accurately retrieving tuples over databases even with large amounts of missing data, in addition to executing queries by up to 100x faster than SOLID\'s competitor.

Nas últimas décadas, tem havido um crescente interesse na detecção precoce das doenças que afetam as culturas agrícolas a fim de evitar grandes perdas econômicas devido à contaminação de novas plantas. Dentre essas doenças as que mais se destacam e são mais letais para a citricultura são o cancro cítrico e greening, ambas ameaçando produções do mundo todo, incluindo regiões do Brasil e dos Estados Unidos. Por se tratar de doenças que possuem um alto índice de contaminação, estas levam a uma redução no número de pomares cultivados causando grande dano econômico aos produtores e as industrias relacionadas. Cada vez mais métodos para diagnóstico antecipado são necessários, tornando-se ferramentas importantes para a saudabilidade da lavoura e consequentemente do negócio. Algumas deficiências de solo como a falta de ferro e zinco apresentam sintomas visuais semelhantes nas folhas das plantas com o greening, enquanto que o cancro cítrico pode ser confundido com a verrugose, podendo levar a diagnósticos errôneos. Atualmente, somente testes bioquímicos são capazes de detectar especificamente o cancro cítrico e o greening, e consequentemente diferenciá-los das demais doenças e deficiências de nutricionais. Nesse trabalho, a técnica de espectroscopia por imagens de fluorescência em conjunto com os métodos de aprendizado supervisionado (algoritmos de classificação), foram utilizadas com o objetivo de identificar e discriminar as principais doenças que afetam a citricultura nos estados de São Paulo/Brasil e da Flórida/EUA. As amostras em estudo são cancro cítrico, verrugose, greening e deficiência de zinco. O objetivo principal é discriminar as doenças sem a necessidade de uma prévia avaliação ocular dos sintomas. Os resultados mostram que é possível utilizar a técnica de espectroscopia por imagens de fluorescência em conjunto a uma rede neural covolucional (AlexNet) para discriminação das doenças. O algoritmo apresentou uma elevada acurácia na classificação das amostras para as quatro doenças em questão quando comparado a outros algoritmos e um enorme ganho de tempo e redução de custo quando comparado ao método bioquímoco. In recent decades, there has been a growing interest in the early detection of diseases that affect agricultural crops in order to avoid major economic losses due to the contamination of new plants. Among these diseases, the most prominent and most lethal for citrus crops are citrus and greening cancer, both of which threaten productions worldwide, including regions in Brazil and the United States. As these are diseases that have a high level of contamination, they lead to a reduction in the number of cultivated orchards causing great economic damage to producers and related industries. More and more methods for early diagnosis are needed, becoming important tools for the health of the crop and consequently the business. Some soil deficiencies, such as the lack of iron and zinc, show similar visual symptoms in the leaves of plants with greening, while citrus can be mistaken for warts, which can lead to misdiagnosis. Currently, only biochemical tests are able to specifically detect citrus canker and greening, and consequently differentiate them from other diseases and nutritional deficiencies. In this work, the technique of spectroscopy by fluorescence images in conjunction with supervised learning methods (classification algorithms), were used in order to identify and discriminate the main diseases that affect citrus in the states of São Paulo / Brazil and the Florida / USA. The samples being studied are citrus canker, warts, greening and zinc deficiency. The main objective is to discriminate diseases without the need for prior eye evaluation of symptoms. The results show that it is possible to use the technique of spectroscopy by fluorescence images in conjunction with a covolutional neural network (AlexNet) to discriminate diseases. The algorithm showed a high accuracy in the classification of the samples for the four diseases in question when compared to other algorithms and an enormous gain of time and cost reduction when compared to the biochemical method.

Consultas analíticas sobre data warehouses convencionais possuem alto custo computacional, desde que requerem a realização de caras operações de junção-estrela considerando grandes volumes de dados. Este custo é ainda maior quando se consideram data warehouses de imagens. Além deles serem mais volumosos, as consultas analíticas são estendidas com predicado de similaridade de imagens, o qual também requer a realização de onerosas operações de cálculos de distância. Nesta dissertação de mestrado, investiga-se esse desafio. Considera-se o contexto de imagens médicas, a sua importância para a tomada de decisão analítica e seu impacto para a sociedade. Neste contexto, as aplicações requerem o compartilhamento e o gerenciamento de grandes volumes de dados, sendo necessário o uso de um framework de processamento paralelo e distribuído. Nesta dissertação, são propostos quatro métodos para o processamento eficiente de consultas analíticas estendidas com predicado de similaridade de imagens em Spark. O método BloOmnImg integra a técnica bloom filter cascade join para o processamento da junção-estrela com a técnica Omni para o processamento das operações de distância. Por ser baseado em uma estrutura de dados probabilística, ele é indicado para sistemas computacionais com pouca memória primária disponível. O método BrOmnImg também usa a técnica Omni, porém a integra com a técnica broadcast join. Por ser baseado em uma estrutura de dados exata, ele é indicado para sistemas computacionais cuja memória primária disponível é suficiente para armazenar essa estrutura. O método BrOmnImgCF estende o método BrOmnImg de forma a utilizar também o predicado convencional das consultas para reduzir ainda mais o número de operações de cálculos de distância entre as imagens. Por fim, o método SimSparkOLAP processa eficientemente consultas analíticas estendidas com predicado de similaridade de imagens, geográficos e socioeconômicos. Os métodos propostos foram validados por meio de testes de desempenho experimentais. Os resultados demonstraram que os métodos proveram ganho de desempenho de até 66,93% frente aos trabalhos relacionados existentes na literatura. Adicionalmente, os métodos propostos foram usados para investigar o potencial semântico do processamento destas consultas analíticas, visando mostrar como os resultados obtidos nesta dissertação de mestrado podem ser usados para enriquecer o suporte à tomada de decisão da área médica. Analytical queries over conventional data warehouses have a high computational cost, as they require processing the expensive star join operation considering huge volumes of data. This cost is even greater in image data warehousing environments. First, image data warehouses are more voluminous. Second, analytical queries are extended with similarity search predicate, also requiring the processing of costly operations to calculate the distance between images. In this master thesis, we focus on this challenge. We consider the context of medical images, due to the importance of the analytical decision-making over them and their impact on the society. In this context, medical applications usually share and manage large volumes of data. Thus, they require the use of a parallel and distributed processing framework. We propose four methods for the efficient processing of analytical queries extended with image similarity search predicate in Spark. The first method is BloOmnImg, which is based on the integration of the bloom filter cascade join and the Omni techniques for processing star joins and distance calculations, respectively. BloOmnImg uses a probabilistic structure. Then, it is indicated for computational systems with low primary memory. The second method is BrOmnImg, which also uses the Omni technique, but integrate it with the broadcast join technique. BrOmnImg is based on a exact structure, then it is indicated for computational systems with primary memory enough to store this structure. The BrOmnImgCF method extends BrOmnImg by using the conventional predicate to further reduce the distance calculations between images. Finally, SimSparkOLAP extends BrOmnImg for the efficient processing analytical queries extended with image, geographical and socioeconomic predicates. The proposed methods were validated through performance tests considering different data volumes and configurations for the predicates involved. The results showed the significant performance gain of the methods over related work. The validation of the methods also considered examples of semantic queries and identified their importance to enrich the medical decision-making process.

A tarefa de Descoberta de Regras de Associação tem o objetivo de descobrir relacionamentos úteis e compreensivos em dados frequentes e infrequentes. Enquanto padrões frequentes descrevem um comportamento comum, padrões infrequentes representam comportamentos que raramente ocorrem. O interesse deste trabalho reside em encontrar regras de exceção, isto é, padrões que embora ocorram com pouca frequência, possuem efeitos potencialmente críticos como consequência. As abordagens existentes para Mineração de Regras de Exceção lidam com bases de dados de itemsets, em que as transações são organizadas sem informação temporal. No entanto, a temporalidade pode ser inerente a alguns contextos reais e deve ser considerada para melhorar a qualidade semântica dos resultados. Além disso, a maioria dessas abordagens possui alto custo computacional (de ordem exponencial), tornando-se inviáveis para minerar grandes volumes de dados. Com o objetivo de superar essas limitações, este trabalho propõe TRiER (TempoRal Exception Ruler), um método eficiente e escalável para Mineração de Regras de Exceção Temporais. Especificamente, o método proposto não apenas descobre comportamentos excepcionais e seus respectivos agentes causadores, mas também identifica quanto tempo as consequências demoram para aparecer. Foi realizada uma análise experimental em dados reais para verificar a aplicabilidade prática do TRiER. Os resultados obtidos mostram que o método possui menor custo computacional e é mais escalável do que os métodos correlatos, além de encontrar regras com maior relevância semântica. Association rules are a common task to discover useful and comprehensive relationships among frequent and infrequent items. Frequent patterns describe a common behavior for certain conditions. Infrequent patterns, on the other hand, represent behavior that rarely occurs. Our interest lies in finding exception rules, i.e., patterns that although occurring infrequently have potentially critical effects as a consequence. Existing approaches for exception rule mining usually handle itemsets databases, where transactions are organized with no temporal information. However, temporality may be inherent to some real contexts and should be considered to improve the semantic quality of results. Moreover, most of these approaches have high computational cost (of exponential order), becoming unfeasible for mining large datasets. Aiming to overcome these drawbacks, we propose TRiER (TempoRal Exception Ruler), an efficient method for mining temporal exception rules. Especially, our method does not only discover exceptional behaviors and their causative agents, but also identifies how long consequences take to appear. We performed an extensive experimental analysis in real data to verify the practical applicability of TRiER. Our results shows TRiER has lower computational cost and is more scalable than existing approaches while finding rules with greater semantic relevance

In the last years, we observed a crescent academic interest on nonstationary data. On the one hand, differences between the data that was used to induce a model and the data that is found after the model is deployed cause a decrease of performance for several tasks, such as classification. On the other hand, in several tasks, such as quantification, we are explicitly interested in measuring how a distribution changes over time. For any of these problems, however, we generally run into solutions that rely on strong assumptions, which are impractical or even impracticable in real world applications. In this thesis, we provide solutions that rely on less restrictive and/or more realistic assumptions in order to allow such methods to be employed in real applications. In the concept drift detection area, we introduce unsupervised drift detection methods that allow for performing classification and quantification without ever requesting true labels after deployment. In the quantification area, we bootstrap a new research topic called one-class quantification. Similarly to one-class classification, in one-class quantification we are able to avoid strong assumptions regarding the negative class, which is deemed unpredictable. Our experimental results are promising and provide favorable evidences about the viability of solutions that are focused on solving real-world problems. Nos últimos anos, é crescente a preocupação da academia com dados não estacionários. Por um lado, diferenças entre as distribuições dos dados disponíveis em laboratório, para treino e avaliação, e dos dados encontrados posteriormente, após implantação dos modelos para uso prático na aplicação, levam ao decréscimo de performance em diversas tarefas, como classificação. Por outro, em outras tarefas, como quantificação, há o interesse explícito em mensurar como a distribuição dos dados se altera ao longo do tempo. Em quaisquer casos, porém, é comum a existência de premissas que tornam as soluções disponíveis ao mesmo tempo possíveis em seus campos de estudo, e impráticas para aplicações reais. Esta tese de doutorado propõe soluções com premissas menos restritivas e/ou mais realistas, que possibilitem seu emprego em aplicações reais. Na área de detecção de mudança de conceito, são introduzidas técnicas de detecção não supervisionada que possibilitam classificação e quantificação sem a necessidade de requisitar rótulos verdadeiros após implantação do modelo. Em quantificação, é iniciada uma nova sub-área de pesquisa, one-class quantification. De forma similar à one-class classification, em one-class quantification não é assumida uma distribuição particular para a classe negativa, sendo considerada, portanto, imprevisível. Os resultados obtidos pela avaliação experimental empregada são promissores e demonstram a viabilidade de alternativas mais focadas em solucionar os problemas existentes em aplicações do mundo real.

Nos últimos anos, a visualização das chamadas imagens tridimensionais (3D) voltou a ter destaque, em especial as imagens estereoscópicas. Tal destaque é devido à geração de conteúdos e dispositivos com suporte para tal tecnologia e grande aceitação por parte do público, utilizando uma vasta gama de modos de visualização. Para mimificar a percepção tridimensional, existem as chamadas imagens estéreoscópicas, que são formadas por um par de imagens ligeiramente deslocadas no espaço uma em relação à outra, sendo uma delas enviada para o olho direito e a outra para o olho esquerdo. Um dos métodos mais simples de visualização estereoscópica é obtido por meio da geração do anáglifo, que baseia-se na separação das componentes de cores (RGB), permitindo qualquer permutação entre elas, sem repetição, com uma componente de cor enviada para um dos olhos e duas componentes para o outro olho. O método anaglífico é interessante por duas razões principais, sendo elas o baixo custo de processamento e visualização, já que pode ser visualizado por meio de simples óculos com filtros de cor, e por utilizar metade do volume de dados em relação a outros métodos de visualização. Assim, aplicações e sistemas podem se beneficiar ao utilizar imagens anaglíficas para fins de armazenamento e transmissão. Contudo, como os métodos de visualização existentes são incompatíveis entre si, tais imagens não podem ser visualizadas por métodos mais robustos de visualização. Neste contexto, este trabalho de mestrado propõe uma técnica automática de reversão anaglífica SIRA (Stereo Images Retrieving from Anaglyphs), que utiliza técnicas empregadas na análise de séries temporais. Reverter implica em produzir aproximações das informações descartadas na geração das imagens anaglíficas, obtendo uma aproximação do par estéreo original, a qual pode ser utilizada para fins de visualização por qualquer método. Resultados objetivos e subjetivos apresentados na avaliação experimental indicam que a técnica proposta apresenta qualidade comparável aos trabalhos considerados estado-da-arte, mas com custo computacional significativamente inferior. In the last years, the visualization of the so-called three-dimensional (3D) images is highlighted again, especially stereoscopic images. Such a highlight is due to the generation of content and devices that support such technology and wide acceptance by the public using a variaty of viewing modes. To mimic three-dimensional perception, there are so-called stereoscopic images, which are formed by a pair of images slightly shifted in space relative to each other, one being sent to the right eye and the other to the left eye. One of the simplest stereoscopic visualization methods is obtained by generating an anaglyph, which is based on the separation of color components (RGB), allowing any permutation between them without repetition, such that a color component is sent to one eye and two components to the other eye. The anaglyphic method is interesting for two main reasons, namely the low processing and visualization cost, since it can be viewed through simple glasses with color filters, and the use of half the data volume compared to other visualization methods. Thus, applications and systems can benefited from using anaglyphic images for storage and transmission purposes. However, as existing viewing methods are incompatible with each other, such images cannot be viewed by more robust viewing methods. In this context, this masters work proposes an automatic anaglyphic reversal technique SIRA (Stereo Images Retrieving from Anaglyphs), which uses techniques employed in time series analysis. Reverting implies producing approximations of the information discarded for anaglyph generation, thus obtaining an approximation of the original stereo pair, wich is compatible with any viasualization method. Objective and subjective results achieved in the experimental evaluation indicate that the proposed technique presents quality comparable to considered state-of-the-art works, but with significantly lower computational cost.

The Division operator (&division;) from the Relational Algebra allows simple and intuitive representation of queries with the concept of \"for all\", and thus it is required by many real applications. However, the Relational Division is unable to support the needs of modern applications that manipulate complex data, such as images, audio, long texts, genetic sequences, etc. These data are better compared for similarity, whereas the Division always compares values for equality. Recent works focused on extending the Relational Algebra and database operators to support similarity comparison. This project incorporated the Similarity-Aware Divison Operator in a Relational Database Management System (RDBMS) and studied its relationship with other query operators. We extended a similarity-oriented SQL to represent the Similarity-Aware Division Operator in a simple and intuitive manner and implemented state-of-art algorithms, internal database queries and resources for similarity data manipulation all inside the RDBMS. This solution presents strategies for efficient and improved performance queries. For semantical validation, it was performed a case study of an application that finds prospective companies able to bid in public request for tenders (RFT) using similarity comparison on RFTs documents and companies\'s catalogs. We evaluated the quality of results in a case study with real datasets from request for tenders from public brazilian food companies. In the experiments, the Similarity-Aware Division Operator was able to identify which RFT which company can participate in with 90% recall. O operador de Divisão (&division;) da Álgebra Relacional permite a representação de consultas com o conceito de \"para todos\" de forma simples e intuitiva, e por isso, é empregado em várias aplicações do dia a dia. Entretanto, a Divisão Relacional é incapaz de atender as necessidades de aplicações modernas que manipulam dados complexos como imagens, áudios, textos longos, sequência genéticas, etc. Esses tipos de dados são melhor comparados por similaridade, porém, a Divisão Relacional sempre compara valores por igualdade. Estudos recentes focaram-se em estender a Álgebra Relacional e operadores de banco de dados para suportar comparações por similaridade. Esse projeto incorporou a Divisão Por Similaridade a um Sistema Gerenciador de Banco de Dados Relacional (SGBDR) e estudou seu relacionamento com outros operadores de consulta. Para isso, foi realizada a extensão de um SQL com operadores de similaridade para representar o operador de Divisão Por Similaridade de forma simples e intuitiva e a implementação de algoritmos do estado-da-arte, consultas internas ao banco e recursos para manipulação de dados por similaridade dentro do SGBD. Esta solução apresenta estratégias para execução eficiente de consultas envolvendo este operador. Para avaliação da qualidade de resultados, foi realizado um estudo de caso para encontrar empresas em potencial capazes de participar de licitações públicas através de comparações por similaridade dos documentos de licitação e da lista de produtos das empresas. Nós avaliamos o caso de uso com conjuntos de dados reais de licitações e empresas brasileiras da indústria alimentícia. Nos experimentos, a Divisão por Similaridade foi capaz de indentificar quais licitações cada empresa pode concorrer com uma revocação de 90%.

Devido aos avanços tecnológicos ocorridos nos últimos anos, houve um aumento na quantidade e complexidade de dados gerados. Assim, aprofundou-se a necessidade do desenvolvimento de estratégias eficientes que permitam o armazenamento, a recuperação e a representação resumida desses tipos de dados complexos. Dentre as estratégias exploradas pelos pesquisadores da área para atender a esses propósitos estão os Métodos de Acesso. Esses métodos têm como objetivo indexar os dados de maneira eficaz para reduzir o tempo de consulta. Além disso, eles têm sido aplicados para apoiar o processamento de técnicas de Mineração de Dados, como a Detecção de Agrupamentos. Dentre os métodos de acesso, as estruturas de indexação métrica são construídas usando apenas o critério baseado na distância entre os elementos do conjunto de dados em questão, i.e. operações de similaridade sobre as características intrínsecas dos dados. Desse modo, nem sempre os resultados correspondem ao contexto desejado pelo usuário. Este trabalho explorou o desenvolvimento de algoritmos que permitam aos métodos de acesso métrico processarem detecção de agrupamento de dados para auxiliar o processamento de consultas com maior carga semântica; visando contribuir no tratamento da questão da eficiência de abordagens que envolvam operações por similaridade (por exemplo, técnicas de mineração de dados e consultas por similaridade). Diante deste contexto, foram desenvolvidas três abordagens, a primeira apresenta o método clusMAM (Unsupervised Clustering using Metric Access Methods), o qual tem como objetivo apresentar um agrupamento dos dados com a aplicação de um Método de Acesso Métrico a partir de um conjunto resumido dos dados. A segunda abordagem apresenta a abordagem CCkNN (Class-Constraint k-NN) para lidar com o problema de restrições de múltiplas classes sobre o espaço de busca. Por fim, a terceira abordagem apresenta o método CfQ (Clustering for Querying) realizando a integração das técnicas clusMAM com CCkNN, empregando os pontos positivos de cada estratégia adotada pelos algoritmos. No geral, os experimentos realizados mostram que os métodos propostos contribuem de maneira efetiva na redução de medidas de similaridade requiridas durante um processamento de técnicas que são baseadas em computações de distância. Due to the technological advances over the last years, both the amount and variety of data available have been increased at a fast pace. Thus, this scenario has influenced the development of effective strategies for the processing, summarizing, as well as to provide fast and automatic understanding of such data. The Access Methods are strategies that have been explored by researchers in the area to aid these purposes. These methods aim to effectively index data to reduce the time required for processing similarity querying. In addition, they have been applied to aid the processing of Data Mining techniques, such as Clustering Detection. Among the access methods, the metric structures are constructed applying only the criterion based on the distance computation between the elements of the dataset, i.e. similarity operations on the intrinsic characteristics of the dataset. Thus, the results do not always correspond to the context desired by users. This work explored the development of algorithms that allow metric access methods to process queries with a higher semantic load, aimed at contributing to the treatment of the quality question on the results of approaches that involve similarity operation (for example, data mining techniques and similarity queries). In this context, three approaches have been developed: the first approach presents the method clusMAM (Unsupervised Clustering using Metric Access Methods), which aims to display a clustering from a dataset with the application of a Metric Access Method from a summarized set. The second approach presents the CCkNN approach to dealing with the problem of multi-class constraints on the search space. Finally, the third proposal presents the method CfQ (Clustering for Querying) by integrating the techniques clusMAM with CCkNN, using the positive points of each strategy applied by the algorithms. In general, the experiments carried out showed that the proposed methods can contribute to an effective way of reducing similarity computations, which is required during a processing of techniques that are based on distance computations.

O operador de Junção é um operador importante da Álgebra Relacional que combina os pares de tuplas que atendem a uma dada condição de comparação entre os valores dos atributos de duas relações. Quando a comparação avalia a similaridade entre pares de valores, o operador é chamado Junção por Similaridade. Esse operador tem aplicações em diversos contextos, tais como o suporte de tarefas de mineração e análise de dados em geral, e a detecção de quase-duplicatas, limpeza de dados e casamento de cadeias de caracteres em especial. Dentre os operadores de junção por similaridade existentes, a Junção por Abrangência (range join) é a mais explorada na literatura. Contudo, ela apresenta limitações, tal como a dificuldade para se encontrar um limiar de similaridade adequado. Nesse contexto, a Junção por k-vizinhos mais próximos (knearest neighbor join kNN join) é considerada mais intuitiva, e portanto mais útil que o range join. Entretanto, executar um kNN join é computacionalmente mais caro, o que demanda por abordagens baseadas na técnica de laço aninhado, e as técnicas existentes para a otimização do algoritmo são restritas a um domínio de dados em particular. Visando agilizar e generalizar a execução do kNN join, a primeira contribuição desta tese foi o desenvolvimento do algoritmo QuickNearest, baseado na técnica de divisão e conquista, que é independente do domínio dos dados, independente da função de distância utilizada, e que computa kNNjoins de maneira muito eficiente. Os experimentos realizados apontam que o QuickNearest chega a ser 4 ordens de magnitude mais rápido que os métodos atuais. Além disso, o uso de operadores de junção por similaridade em ambientes relacionais é problemático, principalmente por dois motivos: (i)emgeral o resultado tem cardinalidade muito maior do que o realmente necessário ou esperado pela maioria das aplicações de análise de dados; e (ii) as consultas que os utilizam envolvem também operações de ordenação, embora a ordem seja um conceito não associado à teoria relacional. A segunda contribuição da tese aborda esses dois problemas, tratando os operadores de junção por similaridade existentes como casos particulares de um conjunto mais amplo de operadores binários, para o qual foi definido o conceito de Wide-joins. Os operadores wide-joins recuperam os pares mais similares em geral e incorporam a ordenação como uma operação interna ao processamento, de forma compatível com a teoria relacional e que permite restringir a cardinalidade dos resultados a tuplas de maior interesse para as aplicações. Os experimentos realizados mostram que os wide-joins são rápidos o suficiente para serem usados em aplicações reais, retornam resultados de qualidade melhor do que os métodos concorrentes e são mais adequados para execução num ambiente relacional do que os operadores de junção por similaridade tradicionais. Joins are important Relational Algebra operators. They pair tuples from two relations that meet a given comparison condition between the attribute values. When the evaluation compares the similarity among the values, the operator is called a Similarity Join. This operator has application to a variety of contexts, such as supporting data mining tasks and data analysis in general, and near-duplicate detection, data cleaning and string matching in particular. Among the existing types of similarity joins, the range join is the most explored one in the literature. However, it has several shortcomings, such as the diculty to find adequate similarity thresholds. In such context, the k-nearest neighbors join (kNN join) is considered more intuitive, and therefore more useful than the range join. However, the kNN join execution is computationally well more expensive, thus demanding implementations either based on nested loop techniques, which are generic, or on optimizing techniques but that are specific data given domains. In order to accelerate and generalize kNN join execution, the first contribution of this thesis was the development of the QuickNearest algorithm, based on the divide and conquest approach that is independent of the data domain, independent of the distance function used, and that computes kNN joins very eciently. Experiments performed with the QuickNearest algorithm show that it is up to four orders of magnitude faster than current methods. Nevertheless, using similarity join operators in relational environments remains generally troublesome, due to two main reasons: (i) the result often has a cardinality much larger than what is actually needed or expected by most of the data analysis applications; and (ii) queries that use them almost always also require sorting operations, but order concept is not present in the relational theory. The second contribution of the thesis addresses these two problems through the definition of the concept of Wide-joins, which turns the existing similarity join operators just as particular cases of a more powerful set of binary operators. Awide-join operator retrieves the pairs most similar in general and already incorporates ordering as an internal operation to its processing, what makes it fully compatible with the relational theory. The concept also provides powerful ways to restrict the result cardinality just to tuples really meaningful for the applications. In fact, the experiments have also shown that wide-joins are fast enough to be useful for real applications, they return results of better quality than competing methods, and are more suitable for execution in a relational environment than the traditional similarity join operators.

Realizar o agrupamento de fluxos de dados contínuos e multidimensionais (multidimensional data streams) é uma tarefa dispendiosa, visto que esses tipos de dados podem possuir características peculiares e que precisam ser consideradas, dentre as quais destacam-se: podem ser infinitos, tornando inviável, em muitas aplicações realizar mais de uma leitura dos dados; ponto de dados podem possuir diversas dimensões e a correlação entre as dimensões pode impactar no resultado final da análise e; são capazes de evoluir com o passar do tempo. Portanto, faz-se necessário o desenvolvimento de métodos computacionais adequados a essas características, principalmente nas aplicações em que realizar manualmente tal tarefa seja algo impraticável em razão do volume de dados, por exemplo, na análise e predição do comportamento climático. Nesse contexto, o objetivo desse trabalho de pesquisa foi propor técnicas computacionais, eficientes e eficazes, que contribuíssem para a extração de conhecimento de fluxos de dados com foco na tarefa de agrupamento de fluxos de dados similares. Assim, no escopo deste trabalho, foram desenvolvidos dois métodos para agrupamento de fluxos de dados evolutivos, multidimensionais e potencialmente infinitos, ambos baseados no conceito de dimensão fractal, até então não utilizada nesse contexto na literatura: o eFCDS, acrônimo para evolving Fractal Clustering of Data Streams, e o eFCC, acrônimo para evolving Fractal Clusters Construction. O eFCDS utiliza a dimensão fractal para mensurar a correlação, linear ou não, existente entre as dimensões dos dados de um fluxo de dados multidimensional num período de tempo. Esta medida, calculada para cada fluxo de dados, é utilizada como critério de agrupamento de fluxos de dados com comportamentos similares ao longo do tempo. O eFCC, por outro lado, realiza o agrupamento de fluxos de dados multidimensionais de acordo com dois critérios principais: comportamento ao longo do tempo, considerando a medida de correlação entre as dimensões dos dados de cada fluxo de dados, e a distribuição de dados em cada grupo criado, analisada por meio da dimensão fractal do mesmo. Ambos os métodos possibilitam ainda a identificação de outliers e constroem incrementalmente os grupos ao longo do tempo. Além disso, as soluções propostas para tratamento de correlações em fluxos de dados multidimensionais diferem dos métodos apresentados na literatura da área, que em geral utilizam técnicas de sumarização e identificação de correlações lineares aplicadas apenas à fluxos de dados unidimensionais. O eFCDS e o eFCC foram testados e confrontados com métodos da literatura que também se propõem a agrupar fluxos de dados. Nos experimentos realizados com dados sintéticos e reais, tanto o eFCDS quanto o eFCC obtiveram maior eficiência na construção dos agrupamentos, identificando os fluxos de dados com comportamento semelhante e cujas dimensões se correlacionam de maneira similar. Além disso, o eFCC conseguiu agrupar os fluxos de dados que mantiveram distribuição dos dados semelhante em um período de tempo. Os métodos possuem como uma das aplicações imediatas a extração de padrões de interesse de fluxos de dados proveniente de sensores climáticos, com o objetivo de apoiar pesquisas em Agrometeorologia. To cluster multidimensional data streams is an expensive task since this kind of data could have some peculiarities characteristics that must be considered, among which: they are potencially infinite, making many reads impossible to perform; data can have many dimensions and the correlation among them could have an affect on the analysis; as the time pass through they are capable of evolving. Therefore, it is necessary the development of appropriate computational methods to these characteristics, especially in the areas where performing such task manually is impractical due to the volume of data, for example, in the analysis and prediction of climate behavior. In that context, the research goal was to propose efficient and effective techniques that clusters multidimensional evolving data streams. Among the applications that handles with that task, we highlight the evolving Fractal Clustering of Data Streams, and the eFCC acronym for evolving Fractal Clusters Construction. The eFCDS calculates the data streams fractal dimension to correlate the dimensions in a non-linear way and to cluster those with the biggest similarity over a period of time, evolving the clusters as new data is read. Through calculating the fractal dimension and then cluster the data streams the eFCDS applies an innovative strategy, distinguishing itself from the state-of-art methods that perform clustering using summaries techniques and linear correlation to build their clusters over unidimensional data streams. The eFCDS also identifies those data streams who showed anomalous behavior in the analyzed time period treating them as outliers. The other method devoleped is called eFCC. It also builds data streams clusters, however, they are built on a two premises basis: the data distribution should be likely the same and second the behavior should be similar in the same time period. To perform that kind of clustering the eFCC calculates the clusters fractal dimension itself and the data streams fractal dimension, following the evolution in the data, relocating the data streams from one group to another when necessary and identifying those that become outlier. Both eFCDS and eFCC were evaluated and confronted with their competitor, that also propose to cluster data streams and not only data points. Through a detailed experimental evaluation using synthetic and real data, both methods have achieved better efficiency on building the groups, better identifying data streams with similar behavior during a period of time and whose dimensions correlated in a similar way, as can be observed in the result chapter 6. Besides that, the eFCC also cluster the data streams which maintained similar data distribution over a period of time. As immediate application the methods developed in this thesis can be used to extract patterns of interest from climate sensors aiming to support researches in agrometeorology.

Fluxos de dados são usualmente caracterizados por grandes quantidades de dados gerados continuamente em processos síncronos ou assíncronos potencialmente infinitos, em aplicações como: sistemas meteorológicos, processos industriais, tráfego de veículos, transações financeiras, redes de sensores, entre outras. Além disso, o comportamento dos dados tende a sofrer alterações significativas ao longo do tempo, definindo data streams evolutivos. Estas alterações podem significar eventos temporários (como anomalias ou eventos extremos) ou mudanças relevantes no processo de geração da stream (que resultam em alterações na distribuição dos dados). Além disso, esses conjuntos de dados podem possuir características espaciais, como a localização geográfica de sensores, que podem ser úteis no processo de análise. A detecção dessas variações de comportamento que considere os aspectos da evolução temporal, assim como as características espaciais dos dados, é relevante em alguns tipos de aplicação, como o monitoramento de eventos climáticos extremos em pesquisas na área de Agrometeorologia. Nesse contexto, esse projeto de mestrado propõe uma técnica para auxiliar a análise espaço-temporal em data streams multidimensionais que contenham informações espaciais e não espaciais. A abordagem adotada é baseada em conceitos da Teoria de Fractais, utilizados para análise de comportamento temporal, assim como técnicas para manipulação de data streams e estruturas de dados hierárquicas, visando permitir uma análise que leve em consideração os aspectos espaciais e não espaciais simultaneamente. A técnica desenvolvida foi aplicada a dados agrometeorológicos, visando identificar comportamentos distintos considerando diferentes sub-regiões definidas pelas características espaciais dos dados. Portanto, os resultados deste trabalho incluem contribuições para a área de mineração de dados e de apoio a pesquisas em Agrometeorologia. Data streams are usually characterized by large amounts of data generated continuously in synchronous or asynchronous potentially infinite processes, in applications such as: meteorological systems, industrial processes, vehicle traffic, financial transactions, sensor networks, among others. In addition, the behavior of the data tends to change significantly over time, defining evolutionary data streams. These changes may mean temporary events (such as anomalies or extreme events) or relevant changes in the process of generating the stream (that result in changes in the distribution of the data). Furthermore, these data sets can have spatial characteristics such as geographic location of sensors, which can be useful in the analysis process. The detection of these behavioral changes considering aspects of evolution, as well as the spatial characteristics of the data, is relevant for some types of applications, such as monitoring of extreme weather events in Agrometeorology researches. In this context, this project proposes a technique to help spatio-temporal analysis in multidimensional data streams containing spatial and non-spatial information. The adopted approach is based on concepts of the Fractal Theory, used for temporal behavior analysis, as well as techniques for data streams handling also hierarchical data structures, allowing analysis tasks that take into account the spatial and non-spatial aspects simultaneously. The developed technique has been applied to agro-meteorological data to identify different behaviors considering different sub-regions defined by the spatial characteristics of the data. Therefore, results from this work include contribution to data mining area and support research in Agrometeorology.

Nas últimas décadas, com o crescimento acelerado na geração e armazenamento de dados, houve um aumento na necessidade de criação e gerenciamento de grandes bases de dados. Logo, a utilização de técnicas de mineração de dados adequadas para descoberta de padrões e informações úteis em bases de dados é uma tarefa de interesse. Em especial, bases de séries temporais têm sido alvo de pesquisas em áreas como medicina, economia e agrometeorologia. Em mineração de dados, uma das tarefas mais exploradas é a classificação. Entretanto, é comum em bases de séries temporais, a quantidade e complexidade de dados extrapolarem a capacidade humana de análise manual dos dados, o que torna o processo de supervisão dos dados custoso. Como consequência disso, são produzidos poucos dados rotulados, em comparação a um grande volume de dados não rotulados disponíveis. Nesse cenário, uma abordagem adequada para análise desses dados é a classificação semissupervisionada, que considera dados rotulados e não rotulados para o treinamento do classificador. Nesse contexto, este trabalho de mestrado propõe 1) uma metodologia de análise de dados obtidos a partir de séries temporais de imagens de satélite (SITS) usando tarefas de mineração de dados e 2) uma técnica baseada em grafos para classificação semissupervisionada de séries temporais extraídas de imagens de satélite. A metodologia e a técnica de classificação desenvolvidas são aplicadas na análise de séries temporais de índices de vegetação obtidas a partir de SITS, visando a identificação de áreas de plantio de cana-de-açúcar. Os resultados obtidos em análise experimental, realizada com apoio de especialistas no domínio de aplicação, indicam que a metodologia proposta é adequada para auxiliar pesquisas em agricultura. Além disso, os resultados do estudo comparativo mostram que a técnica de classificação semissupervisionada desenvolvida supera métodos de classificação supervisionada consolidados na literatura e métodos correlatos de classificação semissupervisionada. The amount of digital data generated and stored as well as the need of creation and management of large databases has increased significantly, in the last decades. The possibility of finding valid and potentially useful patterns and information in large databases has attracted the attention of many scientific areas. Time series databases have been explored using data mining methods in serveral domains of application, such as economics, medicine and agrometeorology. Due to the large volume and complexity of some time series databases, the process of labeling data for supervised tasks, such as classification, can be very expensive. To overcome the problem of scarcity of labeled data, semi-supervised classification, which benefits from both labeled and unlabeled data available, can be applied to classify data from large time series databases. In this Master dissertation, we propose 1) a framework for the analysis of data extracted from satellite image time series (SITS) using data mining tasks and 2) a graph-based semi-supervised classification method, developed to classify temporal data obtained from satellite images. According to experts in agrometeorology, the use of the proposed method and framework provides an automatic way of analyzing data extracted from SITS, which is very useful for supporting research in this domain of application. We apply the framework and the proposed semi-supervised classification method in the analysis of vegetation index time series, aiming at identifying sugarcane crop fields, in Brazil. Experimental results indicate that our proposed framework is useful for supporting researches in agriculture, according to experts in the domain of application. We also show that our method is more accurate than traditional supervised methods and related semi-supervised methods.

Uma série temporal é uma sequência ordenada pelo tempo de valores reais. Dado que inúmeros fenômenos do dia-a-dia podem ser representados por séries temporais, há grande interesse na mineração de dados temporais, em especial na tarefa de classificação. Recentemente foi introduzida uma nova primitiva de séries temporais chamada shapelet, que é uma subsequência que permite a classificação de séries temporais de acordo com padrões locais. Na transformada shapelet estas subsequências se tornam atributos em uma matriz de distância que mede a dissimilaridade entre os atributos e as séries temporais. Para obter a transformada é preciso escolher alguns shapelets dos inúmeros possíveis, seja pelo efeito de evitar overfitting ou pelo fato de que é computacionalmente caro obter todos. Sendo assim, foram elaboradas medidas de qualidade para os shapelets. Tradicionalmente tem se utilizado a medida de ganho de informação, porém recentemente foi proposto o uso da f-statistic, e nós propomos neste trabalho uma nova denominada in-class transitions. Em nossos experimentos demonstramos que a inclass transitions costuma obter a melhor acurácia, especialmente quando poucos atributos são utilizados. Além disso, propomos o uso de amostragem aleatória nos shapelets para reduzir o espaço de busca e acelerar o processo de obtenção da transformada. Contrastamos a abordagem de amostragem aleatória contra uma em que só são exploradas shapelets de determinados tamanhos. Nossos experimentos mostraram que a amostragem aleatória é mais rápida e requer a computação de um menor número de shapelets. De fato, obtemos os melhores resultados ao amostrarmos 5% dos shapelets, mas mesmo a uma amostragem de 0,05% não foi possível notar uma degradação significante da acurácia. A time series is a time ordered sequence of real values. Given that numerous daily phenomena that can be described by time series, there is a great interest on its data mining, specially on the task of classification. Recently it was introduced a new time series primitive called shapelets, that is a subsequence that allows the classification of time series by local patterns. On the shapelet transformation these subsequences turn into attributes in a distance matrix that measures the dissimilarity between these attributes and the time series. To obtain the shapelet transformation it is required to choose some shapelets among all of the possible ones, be it to avoid overfitting or because it is too computationally expensive to obtain everyone. Thus, some shapelet quality measurements were created. Traditionally the information gain has been used as the default measurement, however, recently it was proposed to use the f-statistic instead, and in this work we propose a new one called in-class transitions. On our experiments it is shown that usually the in-class transitions achieves the best accuracy, specially when few attributes are used. Moreover, we propose the use of random sampling of shapelets as a way to reduce the search space and to speed up the process of obtaining the shapelet transformation. We contrast this approach with one that explores only shapelets that have a specific length. Our experiments show that random sampling is faster and requires fewer shapelets to be computed. In fact, we got the best results when we sampled 5% of the shapelets, but even at a rate of 0.05% it was not possible to detect a significant degradation of the accuracy.

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

A procedência dos dados consiste no conjunto de metadados que possibilita identificar as fontes e os processos de transformação aplicados aos dados, desde a criação até o estado atual desses dados. Existem diversas motivações para se incorporar a procedência ao processo de integração, tais como avaliar a qualidade dos dados das fontes heterogêneas, realizar processos de auditoria dos dados e de atribuição de autoria aos proprietários dos dados e reproduzir decisões de integração. Nesta dissertação é proposto o MPPI, um modelo de procedência para subsidiar processos de integração. O modelo enfoca sistemas nos quais as fontes de dados podem ser atualizadas somente pelos seus proprietários, impossibilitando que a integração retifique eventuais conflitos de dados diretamente nessas fontes. O principal requisito do MPPI é que ele ofereça suporte ao tratamento de todas as decisões de integração realizadas em processos anteriores, de forma que essas decisões possam ser reaplicadas automaticamente em processos de integração subsequentes. O modelo MPPI possui quatro características. A primeira delas consiste no mapeamento da procedência dos dados em operações de cópia, edição, inserção e remoção, e no armazenamento dessas operações em um repositório de operações. A segunda característica é o tratamento de operações de sobreposição, por meio da proposta das políticas blind, restrict, undo e redo. A terceira característica consiste na identificação de anomalias decorrentes do fato de que fontes de dados autônomas podem alterar os seus dados entre processos de integração, e na proposta de quatro tipos de validação das operações frente a essas anomalias: validação completa, da origem, do destino, ou nenhuma. A quarta característica consiste na reaplicação de operações, por meio da proposta dos métodos VRS (do inglês Validate and Reapply in Separate) e VRT (do inglês Validate and Reapply in Tandem) e da reordenação segura do repositório, os quais garantem que todas as decisões de integração tomadas pelo usuário em processos de integração anteriores sejam resolvidas automaticamente e da mesma forma em processos de integração subsequentes. A validação do modelo MPPI foi realizada por meio de testes de desempenho que investigaram o tratamento de operações de sobreposição, o método VRT e a reordenação segura, considerando como base as demais características do modelo. Os resultados obtidos mostraram a viabilidade de implementação das políticas propostas para tratamento de operações de sobreposição em sistemas de integração reais. Os resultados também mostraram que o método VRT proporcionou ganhos de desempenho significativos frente à coleta quando o objetivo é restabelecer resultados de processos de integração que já foram executados pelo menos uma vez. O ganho médio de desempenho do método VRT foi de pelo menos 93%. Ademais, os testes também mostraram que reordenar as operações antes da reaplicação pode melhorar ainda mais o desempenho do método VRT Data provenance is the set of metadata that allows for the identification of sources and transformations applied to data, since its creation to its current state. There are several advantages of incorporating data provenance into data integration processes, such as to estimate data quality and data reliability, to perform data audit, to establish the copyright and ownership of data, and to reproduce data integration decisions. In this master\'s thesis, we propose the MPPI, a novel data provenance model that supports data integration processes. The model focuses on systems in which only owners can update their data sources, i.e., the integration process cannot correct the sources according to integration decisions. The main goal of the MPPI model is to handle decisions taken by the user in previous integration processes, so they can be automatically reapplied in subsequent integration processes. The MPPI model introduces the following properties. It is based on mapping provenance data into operations of copy, edit, insert and remove, which are stored in an operation repository. It also provides four techniques to handle overlapping operations: blind, restrict, undo and redo. Furthermore, it identifies anomalies generated by sources that are updated between two data integration processes and proposes four validation approaches to avoid these anomalies: full validation, source validation, target validation and no validation. Moreover, it introduces two methods that perform the reapplication of operations according to decisions taken by the user, called the VRS (Validate and Reapply in Separate) and the VRT (Validate and Reapply in Tandem) methods, in addition to extending the VRT method with the safe reordering optimization. The MPPI model was validated through performance tests that investigated overlapping operations, the VRT method and the safe reordering optimization. The tests showed that the techniques proposed to handle overlapping operations are feasible to be applied to real integration systems. The results also demonstrated that the VRT method provided significant performance gains over data gathering when the goal is to reestablish previous integration results. The performance gains were of at least 93%. Furthermore, the performance results also showed that reordering the operations before the reapplication process can improve even more the performance of the VRT method

A demanda por sistemas de informações para Agricultura de Precisão (AP) tem sido crescente nos últimos anos, especialmente sistemas que manipulam informações espaciais e temporais baseados na Web. Normalmente as análises dos dados coletados em campo são realizadas por uma grande diversidade de softwares, muitas vezes proprietários e monolíticos, com pouca capacidade de compartilhamento de informações, além de não atenderem todas as necessidades desse tipo de sistema. A construção de sistemas de informações espaço-temporais para AP que permitem o gerenciamento das atividades agrícolas em uma abordagem integrada exige uma arquitetura flexível, interoperável e componentizada. Nesse contexto, esse trabalho de tese tem como objetivo desenvolver o projeto de uma arquitetura de software que permita a construção de sistemas espaço-temporais voltados para AP baseados na Web. Essa arquitetura é proposta num conjunto de três cenários arquiteturais baseados na plataforma JEE com suas especificações e um catálogo de padrões de análise e padrões de projeto espaço-temporais. Esses padrões definem soluções para problemas de análise e projeto que envolvem manipulação de dados espaço-temporais, possibilitando reutilização de conhecimento especializado e de código. Como resultado, este trabalho apresenta, como estudo de caso, a implementação de um componente para apresentação de mapas de produtividade em interface Web. Esse componente é baseado em um padrão de projeto do catálogo de padrões proposto e mostra como o conhecimento agrícola e o conhecimento técnico podem ser embutidos em um componente para utilização na construção de sistemas de informações espaçotemporais para AP. Lately there has been a growing demand for information systems for Precision Agriculture (P.A.), especially for web-based systems that manipulate both spatial and temporal information. Field-collected data are often analyzed with various kinds of software, usually privately owned or monolithically used, also limited in scope and unable to share information. The development of P.A. spatio-temporal information systems that allow the management of agricultural activities through an integrative approach demands a flexible architecture, interoperable and component-structured. In this context, it is the objective of this thesis to present the development of a software architecture design that allows the construction of web-based spatiotemporal systems for Precision Agriculture. This software architecture is proposed in a set of three architectural scenes based on the JEE platform, with its specifications, and a catalog of both spatio-temporal analysis patterns and spatio-temporal design patterns. Such patterns define solutions to both analysis and design problems that involve spatio-temporal data manipulation, thus making possible the reuse of specialized knowledge and the reuse of code. This work presents as a result, in form of a case study, the implementation of a web-component for the presentation of productivity maps on web-interface. This web-component is based on a design pattern from the patterns catalog proposed in this work and it shows how agricultural understanding and technical understanding can be embedded in a component for construction of spatio-temporal information systems for P. A.