A quantidade de dados complexos (imagens, vídeos, séries temporais e outros) tem crescido rapidamente. Dados complexos são adequados para serem recuperados por similaridade, o que significa definir consultas de acordo com um dado critério de similaridade. Além disso, dados complexos usualmente são associados com outras informações, geralmente de tipos de dados convencionais, que devem ser utilizadas em conjunto com operações por similaridade para responder a consultas complexas. Vários trabalhos propuseram técnicas para busca por similaridade, entretanto, a maioria das abordagens não foi concebida para ser integrada com um SGBD, tratando consultas por similaridade como operações isoladas, disassociadas do processador de consultas. O objetivo principal desta tese é propor alternativas algébricas, estruturas de dados e algoritmos para permitir um uso abrangente de consultas por similaridade associadas às demais operações de busca disponibilizadas pelos SGBDs relacionais e executar essas consultas compostas eficientemente. Para alcançar este objetivo, este trabalho apresenta duas contribuições principais. A primeira contribuição é a proposta de uma nova operação por similaridade, chamada consulta aos k-vizinhos mais próximos estendida com condições (ck-NNq), que estende a consulta aos k-vizinhos mais próximos (k-\'NN SUB. q\') de maneira a fornecer uma condição adicional, modificando a semântica da operação. A operação proposta permite representar consultas demandadas por várias aplicações, que não eram capazes de ser representadas anteriormente, e permite homogeneamente integrar condições de filtragem complementares à k-\'NN IND.q\'. A segunda contribuição é o desenvolvimento do FMI-SiR (user-defined Features, Metrics and Indexes for Similarity Retrieval ), que é um módulo de banco de dados que permite executar consultas por similaridade integradas às demais operações do SGBD. O módulo permite incluir métodos de extração de características e funções de distância definidos pelo usuário no núcleo do gerenciador de banco de dados, fornecendo grande exibilidade, e também possui um tratamento especial para imagens médicas. Além disso, foi verificado através de experimentos sobre bancos de dados reais que a implementação do FMI-SiR sobre o SGBD Oracle é capaz de consultar eficientemente grandes bancos de dados complexos / The amount of complex data (images, videos, time series and others) has been growing at a very fast pace. Complex data are well-suited to be searched by similarity, which means to define queries according to a given similarity criterion. Moreover, complex data are usually associated with other information, usually of conventional data types, which must be employed in conjunction with similarity operations to answer complex queries. Several works proposed techniques for similarity searching, however, the majority of the approaches was not conceived to be integrated into a DBMS, treating similarity queries as isolated operations detached from the query processor. The main objective of this thesis is to propose algebraic alternatives, data structures and algorithms to allow a wide use of similarity queries associated to the search operations provided by the relational DBMSs and to execute such composite queries eficiently. To reach this goal, this work presents two main contributions. The first contribution is the proposal of a new similarity operation, called condition-extended k-Nearest Neighbor query (ck-\'NN IND. q\'), that extends the k-Nearest Neighbor query (k-\'NN IND. q\') to provide an additional conditio modifying the operation semantics. The proposed operation allows representing queries required by several applications, which were not able to be represented before, and allows to homogeneously integrate complementary filtering conditions to the k-\'NN IND. q\'. The second contribution is the development of the FMI-SiR(user-defined Features, Metrics and Indexes for Similarity Retrieval), which is a database module that allows executing similarity queries integrated to the DBMS operations. The module allows including user-defined feature extraction methods and distance functions into the database core, providing great exibility, and also has a special treatment for medical images. Moreover, it was verified through experiments over real datasets that the implementation of FMI-SiR over the Oracle DBMS is able to eficiently search very large complex databases

A quantidade de dados complexos (imagens, vídeos, séries temporais e outros) tem crescido rapidamente. Dados complexos são adequados para serem recuperados por similaridade, o que significa definir consultas de acordo com um dado critério de similaridade. Além disso, dados complexos usualmente são associados com outras informações, geralmente de tipos de dados convencionais, que devem ser utilizadas em conjunto com operações por similaridade para responder a consultas complexas. Vários trabalhos propuseram técnicas para busca por similaridade, entretanto, a maioria das abordagens não foi concebida para ser integrada com um SGBD, tratando consultas por similaridade como operações isoladas, disassociadas do processador de consultas. O objetivo principal desta tese é propor alternativas algébricas, estruturas de dados e algoritmos para permitir um uso abrangente de consultas por similaridade associadas às demais operações de busca disponibilizadas pelos SGBDs relacionais e executar essas consultas compostas eficientemente. Para alcançar este objetivo, este trabalho apresenta duas contribuições principais. A primeira contribuição é a proposta de uma nova operação por similaridade, chamada consulta aos k-vizinhos mais próximos estendida com condições (ck-NNq), que estende a consulta aos k-vizinhos mais próximos (k-\'NN SUB. q\') de maneira a fornecer uma condição adicional, modificando a semântica da operação. A operação proposta permite representar consultas demandadas por várias aplicações, que não eram capazes de ser representadas anteriormente, e permite homogeneamente integrar condições de filtragem complementares à k-\'NN IND.q\'. A segunda contribuição é o desenvolvimento do FMI-SiR (user-defined Features, Metrics and Indexes for Similarity Retrieval ), que é um módulo de banco de dados que permite executar consultas por similaridade integradas às demais operações do SGBD. O módulo permite incluir métodos de extração de características e funções de distância definidos pelo usuário no núcleo do gerenciador de banco de dados, fornecendo grande exibilidade, e também possui um tratamento especial para imagens médicas. Além disso, foi verificado através de experimentos sobre bancos de dados reais que a implementação do FMI-SiR sobre o SGBD Oracle é capaz de consultar eficientemente grandes bancos de dados complexos / The amount of complex data (images, videos, time series and others) has been growing at a very fast pace. Complex data are well-suited to be searched by similarity, which means to define queries according to a given similarity criterion. Moreover, complex data are usually associated with other information, usually of conventional data types, which must be employed in conjunction with similarity operations to answer complex queries. Several works proposed techniques for similarity searching, however, the majority of the approaches was not conceived to be integrated into a DBMS, treating similarity queries as isolated operations detached from the query processor. The main objective of this thesis is to propose algebraic alternatives, data structures and algorithms to allow a wide use of similarity queries associated to the search operations provided by the relational DBMSs and to execute such composite queries eficiently. To reach this goal, this work presents two main contributions. The first contribution is the proposal of a new similarity operation, called condition-extended k-Nearest Neighbor query (ck-\'NN IND. q\'), that extends the k-Nearest Neighbor query (k-\'NN IND. q\') to provide an additional conditio modifying the operation semantics. The proposed operation allows representing queries required by several applications, which were not able to be represented before, and allows to homogeneously integrate complementary filtering conditions to the k-\'NN IND. q\'. The second contribution is the development of the FMI-SiR(user-defined Features, Metrics and Indexes for Similarity Retrieval), which is a database module that allows executing similarity queries integrated to the DBMS operations. The module allows including user-defined feature extraction methods and distance functions into the database core, providing great exibility, and also has a special treatment for medical images. Moreover, it was verified through experiments over real datasets that the implementation of FMI-SiR over the Oracle DBMS is able to eficiently search very large complex databases

The complexity of data stored in large databases has increased at very fast paces. Hence, operations more elaborated than traditional queries are essential in order to extract all required information from the database. Therefore, the interest of the database community in similarity search has increased significantly. Two of the well-known types of similarity search are the Range (\'R IND. q\') and the k-Nearest Neighbor (\'kNN IND. q\') queries, which, as any of the traditional ones, can be sped up by indexing structures of the Database Management System (DBMS). Another way of speeding up queries is to perform query optimization. In this process, metrics about data are collected and employed to adjust the parameters of the search algorithms in each query execution. However, although the integration of similarity search into DBMS has begun to be deeply studied more recently, the query optimization has been developed and employed just to answer traditional queries. The execution of similarity queries, even using efficient indexing structures, tends to present higher computational cost than the execution of traditional ones. Two strategies can be applied to speed up the execution of any query, and thus they are worth to employ to answer also similarity queries. The first strategy is query rewriting based on algebraic properties and cost functions. The second technique is when external query factors are applied, such as employing the semantic expected by the user, to prune the answer space. This thesis aims at contributing to the development of novel techniques to improve the similarity-based query optimization processing, exploiting both algebraic properties and semantic restrictions as query refinements / A complexidade dos dados armazenados em grandes bases de dados tem aumentado sempre, criando a necessidade de novas operações de consulta. Uma classe de operações de crescente interesse são as consultas por similaridade, das quais as mais conhecidas são as consultas por abrangência (\'R IND. q\') e por k-vizinhos mais próximos (\'kNN IND. q\'). Qualquer consulta e agilizada pelas estruturas de indexação dos Sistemas de Gerenciamento de Bases de Dados (SGBDs). Outro modo de agilizar as operações de busca e a manutenção de métricas sobre os dados, que são utilizadas para ajustar parâmetros dos algoritmos de busca em cada consulta, num processo conhecido como otimização de consultas. Como as buscas por similaridade começaram a ser estudadas seriamente para integração em SGBDs muito mais recentemente do que as buscas tradicionais, a otimização de consultas, por enquanto, e um recurso que tem sido utilizado para responder apenas a consultas tradicionais. Mesmo utilizando as melhores estruturas existentes, a execução de consultas por similaridade tende a ser mais custosa do que as operações tradicionais. Assim, duas estratégias podem ser utilizadas para agilizar a execução de qualquer consulta e, assim, podem ser empregadas também para responder às consultas por similaridade. A primeira estratégia e a reescrita de consultas baseada em propriedades algébricas e em funções de custo. A segunda técnica faz uso de fatores externos à consulta, tais como a semântica esperada pelo usuário, para restringir o espaço das respostas. Esta tese pretende contribuir para o desenvolvimento de técnicas que melhorem o processo de otimização de consultas por similaridade, explorando propriedades algebricas e restrições semânticas como refinamento de consultas

The complexity of data stored in large databases has increased at very fast paces. Hence, operations more elaborated than traditional queries are essential in order to extract all required information from the database. Therefore, the interest of the database community in similarity search has increased significantly. Two of the well-known types of similarity search are the Range (\'R IND. q\') and the k-Nearest Neighbor (\'kNN IND. q\') queries, which, as any of the traditional ones, can be sped up by indexing structures of the Database Management System (DBMS). Another way of speeding up queries is to perform query optimization. In this process, metrics about data are collected and employed to adjust the parameters of the search algorithms in each query execution. However, although the integration of similarity search into DBMS has begun to be deeply studied more recently, the query optimization has been developed and employed just to answer traditional queries. The execution of similarity queries, even using efficient indexing structures, tends to present higher computational cost than the execution of traditional ones. Two strategies can be applied to speed up the execution of any query, and thus they are worth to employ to answer also similarity queries. The first strategy is query rewriting based on algebraic properties and cost functions. The second technique is when external query factors are applied, such as employing the semantic expected by the user, to prune the answer space. This thesis aims at contributing to the development of novel techniques to improve the similarity-based query optimization processing, exploiting both algebraic properties and semantic restrictions as query refinements / A complexidade dos dados armazenados em grandes bases de dados tem aumentado sempre, criando a necessidade de novas operações de consulta. Uma classe de operações de crescente interesse são as consultas por similaridade, das quais as mais conhecidas são as consultas por abrangência (\'R IND. q\') e por k-vizinhos mais próximos (\'kNN IND. q\'). Qualquer consulta e agilizada pelas estruturas de indexação dos Sistemas de Gerenciamento de Bases de Dados (SGBDs). Outro modo de agilizar as operações de busca e a manutenção de métricas sobre os dados, que são utilizadas para ajustar parâmetros dos algoritmos de busca em cada consulta, num processo conhecido como otimização de consultas. Como as buscas por similaridade começaram a ser estudadas seriamente para integração em SGBDs muito mais recentemente do que as buscas tradicionais, a otimização de consultas, por enquanto, e um recurso que tem sido utilizado para responder apenas a consultas tradicionais. Mesmo utilizando as melhores estruturas existentes, a execução de consultas por similaridade tende a ser mais custosa do que as operações tradicionais. Assim, duas estratégias podem ser utilizadas para agilizar a execução de qualquer consulta e, assim, podem ser empregadas também para responder às consultas por similaridade. A primeira estratégia e a reescrita de consultas baseada em propriedades algébricas e em funções de custo. A segunda técnica faz uso de fatores externos à consulta, tais como a semântica esperada pelo usuário, para restringir o espaço das respostas. Esta tese pretende contribuir para o desenvolvimento de técnicas que melhorem o processo de otimização de consultas por similaridade, explorando propriedades algebricas e restrições semânticas como refinamento de consultas

Sistemas de recuperação de imagens por conteúdo (do inglês Content-based ImageRetrieval - CBIR) têm sido cada vez mais utilizados em diversas aplicações de tratamento e análise de imagens, devido a dois fatores: CBIR é um procedimento que pode ser feito automaticamente, permitindo tratar o grande volume de imagens adquiridos em hospitais, e também é a base para o processamento de consultas por similaridade. No contexto médico tais sistemas auxiliam em diversas tarefas, desde treinamento de profissionais até em sistemas de auxílio a diagnóstico (do inglês Computer-Aided Diagnosis - CAD). Um sistema computacional capaz de comparar e classificar imagens obtidas em exames de pacientes utilizando uma base prévia de conhecimento poderia agilizar o atendimento da população e fornecer aos especialistas informações relevantes de forma rápida e simples. Neste trabalho, o foco foi na análise de imagens de úlceras venosas. Foram desenvolvidas duas técnicas para classificação dessas imagens. A primeira, denominada Counting-Labels Similarity Measure (CL-Measure) possuia vantagem de lidar com imagens segmentadas de forma automática, por superpixels, e ser versátil o suficiente para permitir adaptação para outros domínios. A ideia principal do CL-Measure consiste na criação de sub-imagens baseadas em uma classificação prévia, calcular a distância entre elas e agregar as distâncias parciais obtidas a partir de uma função apropriada. A segunda técnica, denominada Quality of Tissues from Dermatological Ulcers(QTDU), faz uso de redes convolucionais (CNNs) para rotulação dos superpixels com a vantagem de compor todo o processo de identificação de características e classificação, dispensando a necessidade de identificar qual o extrator de características mais adequado para o contexto em questão. Experimentos realizados sobre a base de imagens analisada, utilizando 179572 super pixels divididos em 4 classes, indicam que a QTDU é a abordagem mais eficaz até o momento para o contexto de classificação de imagens dermatológicas, com médias de AUC=0,986, sensitividade = 0,97,e especificidade=0,974 superando as abordagens anteriores baseadas em aprendizado de máquina em 11;7% e 8;2% considerando o coeficiente KAPPAeF-Measure, respectivamente. / Content-based Image Retrieval (CBIR) systems have been increasingly used in many image processing and analysis applications because of two factors: CBIR is a procedure that can be done automatically, allowing to handle the large volume of images acquired in hospitals, and it is also the basis for processing similarity queries. In the medical context, such systems assist in various tasks, from training of professionals to develop Computer-Aided Diagnosis CAD systems. A computer system capable of comparing and classifying images obtained from patient exams using a prior knowledge base could expedite the care of the population and provide specialists with relevant information quickly. In this study, the focus was on the analysis of images of venous ulcers. Two techniques were developed to classify these images. The first, called Counting-Labels Similarity Measure (CL-Measure) has the advantage of dealing with automatically segmented images by superpixels, and is versatile enough to allow adaptation to other domains. The main idea of CL-Measure is to create sub-images based on a previous classification, calculate the distance between them and add the partial distances obtained from an appropriate function. The second technique, called Quality of Tissues from Dermatological Ulcers (QTDU), makes use of convolutional networks (CNNs) for superpixels labeling, with the advantage of encompassing the whole process of identification of features and classification, without the need of identifying which extractor would be the best for the context in question. Experiments carried out on the image database using 179,572 superpixels divided into 4 classes, indicate that the QTDU is the most effective approach to date for the context of classification of dermatological ulcer images, with averages of AUC = 0.986, sensitivity = 0.97 , and specificity = 0.974, surpassing previous approaches based on machine learning in 11.7% and 8.2% considering the KAPPA and F-Measure coefficients, respectively.

A complexidade dos dados armazenados em grandes bases de dados aumenta sempre, criando a necessidade de novas formas de consulta. As consultas por similaridade vêm apresentando crescente interesse para tratar de dados complexos, sendo as mais representativas a consulta por abrangência (\'R IND. q\' Range query) e a consulta aos k-vizinhos mais próximos (k-\'NN IND. q\' k-Nearest Neighboor query). Até recentemente, essas consultas não estavam disponíveis nos Sistemas de Gerenciamento de Bases de Dados (SGBD). Agora, com o início de sua disponibilidade, tem se tornado claro que os operadores de busca fundamentais usados para executá-las não são suficientes para atender às necessidades das aplicações que as demandam. Assim, estão sendo estudadas variações e extensões aos operadores fundamentais, em geral voltados às necessidades de domínios de aplicações específicas. Além disso, os seguintes problemas vêm impactando diretamente sua aceitação por parte dos usuários e, portanto, sua usabilidade: (i) os operadores fundamentais são pouco expressivos em situações reais; (ii) a cardinalidade dos resultados tende a ser grande, obrigando o usuário analisar muitos elementos; e (iii) os resultados nem sempre atendem ao interesse do usuário, implicando na reformulação e ajuste frequente das consultas. O objetivo desta dissertação é o desenvolvimento de uma técnica inédita para exibir um grau de variedade nas respostas às consultas aos k-vizinhos mais próximos em domínios de dados métricos, explorando aspectos de diversidade em extensões dos operadores fundamentais usando apenas as propriedades básicas do espaço métrico sem a solicitação de outra informação por parte do usuário. Neste sentido, são apresentados: a formalização de um modelo de variedade que possibilita inserir diversidade nas consultas por similaridade sem a definição de parâmetros por parte do usuário; um algoritmo incremental para responder às consultas aos k-vizinhos mais próximos com variedade; um método de avaliação de sobreposição de variedade para as consultas por similaridade. As propriedades desses resultados permitem usar as técnicas desenvolvidas para apoiar a propriedade de variedade nas consultas aos k-vizinhos mais próximos em Sistemas de Gerenciamento de Bases de Dados / The data being collected and generated nowadays increases not only in volume, but also in complexity, leading to the need of new query operators. Similarity queries are one of the most pursued resources to retrieve complex data. The most studied operators to perform similarity are the Range Query (\'R IND.q\') and the k-Nearest Neighbor Query (k-\'NN IND. q\'). Until recently, those queries were not available in the Database Management Systems. Now they are starting to become available, but since its earliest applications to develop real systems, it became clear that the basic similarity query operators are not enough to meet the requirements of the target applications. Therefore, new variations and extensions to the basic operators are being studied, although every work up to now is only pursuing the requirements of specific application domains. Furthermore, the following issues are directly impacting their acceptance by users and therefore its usability: (i) the basic operators are not expressive in real situations, (ii) the result-set cardinality tends to be large, imposing to the user the need to analyze to many elements, and (iii) the results do not always meet the users interest, resulting in the reformulation and adjustment of the queries. The goal of this dissertation is the development of a novel technique to enable a degree of variety the answers of k-nearest neighbor queries in metric spaces, investigating aspects of diversity in extensions of the basic operators using only the properties of metric spaces, never requesting extra information from the user. In this monograph, we present: the formalization of the variety model that allows to support diversity in similarity queries without requiring diversification parameters from the user; a greedy algorithm to obtain answers for similarity queries to the k-nearest neighbors with variety; an evaluation method to assess the diversification ratio existing on a subset of elements in metric space. The properties of those results allow using our proposed techniques to support variety in k-nearest neighbor queries in Database Management Systems

Os Sistemas de Gerenciamento de Bases de Dados (SGBD) foram desenvolvidos para armazenar e recuperar de maneira eficiente dados formados apenas por números ou cadeias de caracteres. Entretanto, nas últimas décadas houve um aumento expressivo, não só da quantidade, mas da complexidade dos dados manipulados em bases de dados, dentre eles os de natureza multimídia (como imagens, áudio e vídeo), informações geo-referenciadas, séries temporais, entre outros. Assim, surgiu a necessidade do desenvolvimento de novas técnicas que permitam a manipulação eficiente de tipos de dados complexos. Para atender às buscas necessárias às aplicações de base de dados modernas é preciso que os SGBD ofereçam suporte para buscas por similaridade ? consultas que realizam busca por objetos da base similares a um objeto de consulta, de acordo com uma certa medida de similaridade. Outro fator importante que veio contribuir para a necessidade de suportar a realização de consultas por similaridade em SGBD está relacionado à integração de técnicas de mineração de dados. É fundamental para essa integração o fornecimento de recursos pelos SGBD que permitam a realização de operações básicas para as diversas técnicas de mineração de dados existentes. Uma operação básica para várias dessas técnicas, tais como a técnica de detecção de agrupamentos de dados, é justamente o cálculo de medidas de similaridade entre pares de objetos de um conjunto de dados. Embora haja necessidade de fornecer suporte para a realização desse tipo de consultas em SGBD, o atual padrão da linguagem SQL não prevê a realização de consultas por similaridade. Esta tese pretende contribuir para o fornecimento desse suporte, incorporando ao SQL recursos capazes de permitir a realização de operações de consulta por similaridade sobre grandes bases de dados complexos de maneira totalmente integrada com os demais recursos da linguagem / Database Management Systems (DBMS) were developed to store and efficiently retrieve only data composed by numbers and small strings. However, over the last decades, there was an expressive increase in the volume and complexity of the data being managed, such as multimedia data (images, audio tracks and video), geo-referenced information and time series. Thus, the need to develop new techniques that allow the efficient handling of complex data types also increased. In order to support these data and the corresponding applications, the DBMS needs to support similarity queries, i.e., queries that search for objects similar to a query object according to a similarity measure. The need to support similarity queries in DBMS is also related to the integration of data mining techniques, which requires the DBMS acting as the provider for resources that allow the execution of basic operations for several existing data mining techniques. A basic operation for several of these techniques, such as clustering detection, is again the computation of similarity measures among pairs of objects of a data set. Although there is a need to execute these kind of queries in DBMS, the SQL standard does not allow the specification of similarity queries. Hence, this thesis aims at contributing to support such queries, integrating to the SQL the resources capable to execute similarity query operations over large sets of complex data

Consultas por similaridade constituem um paradigma de busca que fornece suporte à diversas tarefas computacionais, tais como agrupamento, classificação e recuperação de informação. Neste contexto, medir a similaridade entre objetos requer comparar a distância entre eles, o que pode ser formalmente modelado pela teoria de espaços métricos. Recentemente, um grande esforço de pesquisa tem sido dedicado à inclusão de consultas por similaridade em Sistemas Gerenciadores de Bases de Dados (SGBDs), com o objetivo de (i) permitir a combinação de comparações por similaridade com as comparações por identidade e ordem já existentes em SGBDs e (ii) obter escalabilidade para grandes bases de dados. Nesta tese, procuramos dar um próximo passo ao estendermos também o otimizador de consultas de um SGBD. Em particular, propomos a ampliação de dois módulos do otimizador: o módulo de Espaço de Distribuição de Dados e o módulo de Modelo de Custo. Ainda que o módulo de Espaço de Distribuição de Dados permita representar os dados armazenados, essas representações são insuficientes para modelar o comportamento das comparações em espaços métricos, sendo necessário estender este módulo para contemplar distribuições de distância. De forma semelhante, o módulo Modelo de Custo precisa ser ampliado para dar suporte à modelos de custo que utilizem estimativas sobre distribuições de distância. Toda a investigação aqui conduzida se concentra em cinco contribuições. Primeiro, foi criada uma nova sinopse para distribuições de distância, o Histograma Compactado de Distância (CDH), de onde é possível inferir valores de seletividade e raios para consultas por similaridade. Uma comparação experimental permitiu mostrar os ganhos das estimativas da sinopse CDH com relação à diversos competidores. Também foi proposto um modelo de custo baseado na sinopse CDH, o modelo Stockpile, cujas estimativas se mostraram mais precisas na comparação com outros modelos. Os Histogramas-Omni são apresentados como a terceira contribuição desta tese. Estas estruturas de indexação, construídas a partir de restrições de particionamento de histogramas, permitem a execução otimizada de consultas que mesclam comparações por similaridade, identidade e ordem. A quarta contribuição de nossa investigação se refere ao modelo RVRM, que é capaz de indicar quanto é possível empregar as estimativas das sinopses de distância para otimizar consultas por similaridade em conjuntos de dados de alta dimensionalidade. O modelo RVRM se mostrou capaz de identificar intervalos de dimensões para os quais essas consultas podem ser executadas eficientes. Finalmente, a última contribuição desta tese propõe a integração das sinopses e modelos revisados em um sistema com sintaxe de alto nível que pode ser acoplado em um otimizador de consultas. / Similarity searching is a foundational paradigm for many modern computer applications, such as clustering, classification and information retrieval. Within this context, the meaning of similarity is related to the distance between objects, which can be formally expressed by the Metric Spaces Theory. Many studies have focused on the inclusion of similarity search into Database Management Systems (DBMSs) for (i) enabling similarity comparisons to be combined with the DBMSs identity and order comparisons and (ii) providing scalability for very large databases. As a step further, we propose the extension of the DBMS Query Optimizer and, particularly, the extension of two modules of the Query Optimizer, namely Data Distribution Space and Cost Model modules. Although the Data Distribution Space enables representations of stored data, such representations are unsuitable for modeling the behavior of similarity comparisons, which requires the extension of the module to support distance distributions. Likewise, the Cost Model module must be extended to support cost models that depend on distance distributions. Our study is based on five contributions. A new synopsis for distance distributions, called Compact-Distance Histogram (CDH), is proposed and enables radius and selectivity estimation for similarity searching. An experimental comparison showed the gains of the estimates drawn from CDH in comparison to several competitors. A cost model based on the CDH synopsis and with accurate estimates, called Stockpile, is also proposed. Omni-Histograms are presented as the third contribution of the thesis. Such indexing structures are constructed according to histogram partition constraints and enable the optimization of queries that combine similarity, identity and order comparisons. The fourth contribution refers to the model RVRM, which indicates the possible use of the estimates obtained from distance-based synopses for the query optimization of high-dimensional datasets and identifies intervals of dimensions where similarity searching can be efficiently executed. Finally, the thesis proposes the integration of the reviewed synopses and cost models into a single system with a high-level language that can be coupled to a DBMS Query Optimizer.

Os Sistemas de Gerenciamento de Bases de Dados Relacionais (SGBDR) foram concebidos para o armazenamento e recuperação de grandes volumes de dados. Tradicionalmente, estes sistemas suportam números, pequenas cadeias de caracteres e datas (que podem ser comparados por identidade ou por relações de ordem { RO), porém vem se tornando necessário organizar, armazenar e recuperar dados mais complexos, como por exemplo dados multimídia (imagens, áudio e vídeo), séries temporais etc. Quando se trata de dados complexos há uma mudança de paradigma, pois as comparações entre elementos são feitas por similaridade em vez das RO utilizadas tradicionalmente, tendo como mais frequentemente utilizados os operadores de comparação por abrangência (Rq) e por k-vizinhos mais próximos (k-NN). Embora muitos estudos estejam sendo feitos nessa área, quando lidando com consultas por similaridade grande parte do esforço é direcionado para criar as estruturas de indexação e dar suporte às operações necessárias para executar apenas o aspecto da consulta que trata da similaridade, sem focar em realizar uma integração homogênea das consultas que envolvam ambos os tipos de operadores simultaneamente nos ambientes dos SGDBRs. Um dos principais problemas nessa integração é lidar com as peculiaridades do operador de busca por k-NN. Todos os operadores de comparação por identidade e por RO são comutativos e associativos entre si. No entanto o operador de busca por k-NN não atende a nenhuma dessas propriedades. Com isso, a expressão de consultas em SQL, que usualmente pode ser feita sem que a expressão da ordem entre os predicados seja importante, precisa passar a considerar a ordem. Além disso, consultas que utilizam comparações por k-NN podem gerar múltiplos empates, e a falta de uma metodologia para resolvê-los pode levar a um processo de desempate arbitrário ou insensível ao contexto da consulta, onde usuários não tem poder para intervir de maneira significativa. Em alguns casos, isso pode levar a uma mesma consulta a retornar resultados distintos em casos onde a estrutura interna dos dados estiver sujeita a modificações, como por exemplo em casos de transações concorrentes em um SGBDR. Este trabalho aborda os problemas gerados pela inserção de operadores de busca por similaridade nos SGBDR, mais especificamente o k-NN, e propõe novas maneiras de representação de consultas com múltiplos predicados, por similaridade ou RO, assim como novos operadores derivados do k-NN que são mais adequados para um ambiente relacional que permita consultas híbridas, e permitem também controle sobre o tratamento de empates. / The Relational Database Management Systems (RDBMS) were originally conceived to store and retrieve large volumes of data. Traditionally, these systems support only numbers, small strings of characters and dates (which could be compared by identity and a Order Relationship { OR). However it has been increasingly necessary to organize, store and retrieve more complex data, such as multimedia (images, audio and video), time series etc. Dealing with those data types requires a paradigm shift, as the comparisons between each element are made by similarity, and not by the traditionally used identity or OR, with the most common similarity operators used being the range (Rq) and k-Nearest Neighbors (k-NN). Despite many studies in the field, when dealing with similarity queries a large part of the effort has been directed towards the data structures and the necessary operations to execute only the similarity side of the query, not paying attention to a more homogenous integration of queries that involve both operator types simultaneously in RDBMS environments. One of the main problems for such integration is the peculiarities of the k-NN operator. Both identity and OR operators possess the commutative and associative properties amongst themselves, but the k-NN operator does not. As such, expressing SQL queries, that usually can disregard the order in which predicates appear, now needs to be aware of the ordering. Furthermore, queries that use k-NN might generate multiple ties, and the lack of a methodology to solve them might lead to an arbitrary or context-detached untying process, where users have little or no control to intervene. In some applications, the lack of a controlled untying process may even lead to each query yielding distinct results if the underlying structures ought be subject to change, as it is be the case of the concurrent transactions in a relational database management system (RDBMS). This work focuses on the problems that arise from the integration of similarity based operators into RDBMS, more specifically the k-NN, and proposes new ways to represent queries with multiple predicates, including similarity, identity or OR, as well as new operators derived from k-NN that are better suited for a RDBMS environment containing hybrid queries, and also enable control over the untying process.

Esta tese apresenta um modelo de custo para estimar o número de acessos a disco (custo de I/O) e o número de cálculos de distância (custo de CPU) para consultas por similaridade executadas sobre métodos de acesso métricos dinâmicos. O objetivo da criação do modelo é a otimização de consultas por similaridade em Sistemas de Gerenciamento de Bases de Dados relacionais e objeto-relacionais. Foram considerados dois tipos de consultas por similaridade: consulta por abrangência e consulta aos k-vizinhos mais próximos. Como base para a criação do modelo de custo foi utilizado o método de acesso métrico dinâmico Slim-Tree. O modelo estima a dimensão intrínseca do conjunto de dados pela sua dimensão de correlação fractal. A validação do modelo é confirmada por experimentos com conjuntos de dados sintéticos e reais, de variados tamanhos e dimensões, que mostram que as estimativas obtidas em geral estão dentro da faixa de variação medida em consultas reais / This thesis presents a cost model to estimate the number of disk accesses (I/O costs) and the number of distance calculations (CPU costs) to process similarity queries over data indexed by dynamic metric access methods. The goal of the model is to optimize similarity queries on relational and object-relational Database Management Systems. Two types of similarity queries were taken into consideration: range queries and k-nearest neighbor queries. The dynamic metric access method Slim-Tree was used as the basis for the creation of the cost model. The model takes advantage of the intrinsic dimension of the data set, estimated by its correlation fractal dimension. Experiments were performed on real and synthetic data sets, with different sizes and dimensions, in order to validate the proposed model. They confirmed that the estimations are accurate, being always within the range achieved executing real queries