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

Searching relevant information based on content features in video databases is an interesting and challenging research topic that has drawn lots of attention recently. Video similarity search has many practical applications such as TV broadcast monitoring, copyright compliance enforcement and search result clustering, etc. However, existing studies are limited to provide fast and accurate solutions due to the diverse variations among the videos in large collections. In this thesis, we introduce the database support for effective and efficient video similarity search from various sources, even if there exists some transformation distortion, partial content re-ordering, insertion, deletion or replacement. Specifically, we focus on processing two different types of content-based queries: video clip retrieval in a large collection of segmented short videos, and video subsequence identification from a long unsegmented stream. The first part of the thesis investigates the problem of how to process a number of individual kNN searches on the same database simultaneously to reduce the computational overhead of current content-based video search systems. We propose a Dynamic Query Ordering (DQO) algorithm for efficiently processing Batch Nearest Neighbor (BNN) search in high-dimensional space, with advanced optimizations of both I/O cost and CPU cost. The second part of the thesis challenges an unstudied problem of temporal localization of similar content from a long unsegmented video sequence, with extension to identify the occurrence of potentially different ordering or length with respect to query due to video content editing. A graph transformation and matching approach supported by the above BNN search is proposed, as a filter-and-refine query processing strategy to effectively but still efficiently identify the most similar subsequence. The third part of the thesis extends the method of Bounded Coordinate System (BCS) we introduced earlier for video clip retrieval. A novel collective perspective of exploiting the distributional discrepancy of samples for assessing the similarity between two video clips is presented. Several ideas of non-parametric hypothesis tests in statistics are utilized to check the hypothesis whether two ensembles of points are from a same distribution. The proposed similarity measures can provide a more comprehensive analysis that captures the essence of invariant distribution information for retrieving video clips. For each part, we demonstrate comprehensive experimental evaluations, which show improved performance compared with state-of-the-art methods. In the end, some scheduled extensions of this work are highlighted as future research objectives.

Rendre les données multimédias disponibles en ligne devient moins cher et plus pratique sur une base quotidienne, par exemple par les utilisateurs eux-mêmes. Des phénomènes du Web comme Facebook, Twitter et Flickr bénéficient de cette évolution. Ces phénomènes et leur acceptation accrue conduisent à une multiplication du nombre d’images disponibles en ligne. La taille cumulée de ces images souvent publiques et donc consultables, est de l’ordre de plusieurs zettaoctets. L’exécution d’une requête de similarité sur de tels volumes est un défi que la communauté scientifique commence à cibler. Une approche envisagée pour faire face à ce problème propose d’utiliser un système distribué et hétérogène de recherche d’images basé sur leur contenu (CBIRs). De nombreux problèmes émergent d’un tel scénario. Un exemple est l’utilisation de formats de métadonnées distincts pour décrire le contenu des images; un autre exemple est l’information technique et structurelle inégale. Les métriques individuelles qui sont utilisées par les CBIRs pour calculer la similarité entre les images constituent un autre exemple. Le calcul de bons résultats dans ce contexte s’avère ainsi une tàche très laborieuse qui n’est pas encore scientifiquement résolue. Le problème principalement abordé dans cette thèse est la recherche de photos de CBIRs similaires à une image donnée comme réponse à une requête multimédia distribuée. La contribution principale de cette thèse est la construction d’un réseau de CBIRs sensible à la sémantique des contenus (CBIRn). Ce CBIRn sémantique est capable de collecter et fusionner les résultats issus de sources externes spécialisées. Afin d’être en mesure d’intégrer de telles sources extérieures, prêtes à rejoindre le réseau, mais pas à divulguer leur configuration, un algorithme a été développé capable d’estimer la configuration d’un CBIRS. En classant les CBIRs et en analysant les requêtes entrantes, les requêtes d’image sont exclusivement transmises aux CBIRs les plus appropriés. De cette fac ̧on, les images sans intérêt pour l’utilisateur peuvent être omises à l’avance. Les images retournées cells sont considérées comme similaires par rapport à l’image donnée pour la requête. La faisabilité de l’approche et l’amélioration obtenue par le processus de recherche sont démontrées par un développement prototypique et son évaluation utilisant des images d’ImageNet. Le nombre d’images pertinentes renvoyées par l’approche de cette thèse en réponse à une requête image est supérieur d’un facteur 4.75 par rapport au résultat obtenu par un réseau de CBIRs predéfini. / Making multimedia data available online becomes less expensive and more convenient on a daily basis. This development promotes web phenomenons such as Facebook, Twitter, and Flickr. These phenomena and their increased acceptance in society in turn leads to a multiplication of the amount of available images online. This vast amount of, frequently public and therefore searchable, images already exceeds the zettabyte bound. Executing a similarity search on the magnitude of images that are publicly available and receiving a top quality result is a challenge that the scientific community has recently attempted to rise to. One approach to cope with this problem assumes the use of distributed heterogeneous Content Based Image Retrieval system (CBIRs). Following from this anticipation, the problems that emerge from a distributed query scenario must be dealt with. For example the involved CBIRs’ usage of distinct metadata formats for describing their content, as well as their unequal technical and structural information. An addition issue is the individual metrics that are used by the CBIRs to calculate the similarity between pictures, as well as their specific way of being combined. Overall, receiving good results in this environment is a very labor intensive task which has been scientifically but not yet comprehensively explored. The problem primarily addressed in this work is the collection of pictures from CBIRs, that are similar to a given picture, as a response to a distributed multimedia query. The main contribution of this thesis is the construction of a network of Content Based Image Retrieval systems that are able to extract and exploit the information about an input image’s semantic concept. This so called semantic CBIRn is mainly composed of CBIRs that are configured by the semantic CBIRn itself. Complementarily, there is a possibility that allows the integration of specialized external sources. The semantic CBIRn is able to collect and merge results of all of these attached CBIRs. In order to be able to integrate external sources that are willing to join the network, but are not willing to disclose their configuration, an algorithm was developed that approximates these configurations. By categorizing existing as well as external CBIRs and analyzing incoming queries, image queries are exclusively forwarded to the most suitable CBIRs. In this way, images that are not of any use for the user can be omitted beforehand. The hereafter returned images are rendered comparable in order to be able to merge them to one single result list of images, that are similar to the input image. The feasibility of the approach and the hereby obtained improvement of the search process is demonstrated by a prototypical implementation. Using this prototypical implementation an augmentation of the number of returned images that are of the same semantic concept as the input images is achieved by a factor of 4.75 with respect to a predefined non-semantic CBIRn.

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

La forte augmentation du volume de données multimédia impose la mise au point de solutions adaptées pour une exploration visuelle efficace des bases multimédia. Après avoir examiné les processus de visualisation mis en jeu, nous remarquons que ceci demande une structuration des données. L’objectif principal de cette thèse est de proposer et d’étudier ces méthodes de structuration des bases multimédia en vue de leur exploration visuelle.Nous commençons par un état de l’art détaillant les données et les mesures que nous pouvons produire en fonction de la nature des variables décrivant les données. Suit un examen des techniques de structuration par projection et classification. Nous présentons aussi en détail la technique du Clustering Spectral sur laquelle nous nous focaliserons ensuite.Notre première réalisation est une méthode originale de production et fusion de métriques par corrélation de rang. Nous testons cette première méthode sur une base multimédia issue de la vidéothèque d’un festival de films. Nous continuons ensuite par la mise au point d’une méthode de classification supervisée par corrélation que nous testons avec les données vidéos d’un challenge de la communauté multimédia. Ensuite nous nous focalisons sur les techniques du Clustering Spectral. Nous testons une technique de Clustering Spectral supervisée que nous comparons aux techniques de l’état de l’art. Et pour finir nous examinons des techniques du Clustering Spectral semi-supervisé actif. Dans ce contexte, nous proposons et validons des techniques de propagation d’annotations et des stratégies permettant d’améliorer la convergence de ces méthodes de classement. / The large increase in multimedia data volume requires the development of effective solutions for visual exploration of multimedia databases. After reviewing the visualization process involved, we emphasis the need of data structuration. The main objective of this thesis is to propose and study clustering and classification of multimedia database for their visual exploration.We begin with a state of the art detailing the data and the metrics we can produce according to the nature of the variables describing each document. Follows a review of the projection and classification techniques. We also present in detail the Spectral Clustering method.Our first contribution is an original method that produces fusion of metrics using rank correlations. We validate this method on an animation movie database coming from an international festival. Then we propose a supervised classification method based on rank correlation. This contribution is evaluated on a multimedia challenge dataset. Then we focus on Spectral Clustering methods. We test a supervised Spectral Clustering technique and compare to state of the art methods. Finally we examine active semi-supervised Spectral Clustering methods. In this context, we propose and validate constraint propagation techniques and strategies to improve the convergence of these active methods.

Multimedia retrieval systems are supposed to provide the method and the interface for users to retrieve particular multimedia data from multimedia collections. Although, many different retrieval techniques evolved from times when the search in multimedia collections firstly appeared as a research task, not all of them can fulfill specific requirements that the multimedia exploration is determined for. The multimedia exploration is designated for revealing the content of a whole multimedia collection, quite often totally unknown to the users who retrieve data. Because of these facts a multimedia exploration system has to solve problems like, how to visualize (usually multidimensional) multimedia data, how to scale data retrieval from arbitrarily large collections and how to design such an interface that the users could intuitively use for the exploration. Taking these problems into consideration, we proposed and evaluated ideas for building the system that is well-suited for the multimedia exploration. We outlined the overall architecture of a multimedia exploration system, created the Multi-Layer Exploration Structure (MLES) as an underlying index structure that should solve problems of efficient and intuitive data retrieval and we also proposed definitions of exploration operations as an interactive and...

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

The field that deals with storing and effective searching of multimedia documents is called Information retrieval. This paper describes solution of effective searching in collections of shots. Multimedia documents are presented as vectors in high-dimensional space, because in such collection of documents it is easier to define semantics as well as the mechanisms of searching. The work aims at problems of similarity searching based on metric space, which uses distance functions, such as Euclidean, Chebyshev or Mahalanobis, for comparing global features and cosine or binary rating for comparing local features. Experiments on the TRECVid dataset compare implemented distance functions. Best distance function for global features appears to be Mahalanobis and for local features cosine rating.

The necessity of managing disparate data models is increasing within all IT areas. Emerging hybrid relational-XML systems are under development in this context to support both relational and XML data models. However, there are ever-growing needs for adequate data models for texts and multimedia, which are applications that require proper storage, and their capability to coexist and collaborate with other data models is as important as that of a relational-XML hybrid model. This work proposes a new data model named E-model that supports rich relations and reflects the dynamic nature of information. This E-model introduces abstract data typing objects and rules of relation that support: (1) the notion of time in object definition and relation, (2) multiple-type relations, (3) complex schema modeling methods using a relational directed acyclic graph, and (4) interoperation with popular data models. To implement the E-model prototype, extensive data operation APIs have been developed on top of relational databases. In processing dynamic queries, our prototype achieves an order of magnitude improvement in speed compared with popular data models. Based on extensive E-model APIs, a new language named EML is proposed. EML extends the SQL-89 standard with various E-model features: (1) unstructured queries, (2) unified object namespaces, (3) temporal queries, (4) ranking orders, (5) path queries, and (6) semantic expansions. The E-model system can interoperate with popular data models with its rich relations and flexible structure to support complex data models. It can act as a stand-alone database server or it can also provide materialized views for interoperation with other data models. It can also co-exist with established database systems as a centralized online archive or as a proxy database server. The current E-model prototype system was implemented on top of a relational database. This allows significant benefits from established database engines in application development. In addition to extensive features added to SQL, our EML prototype achieves an order of magnitude speed improvement in dynamic queries compared to popular database models. Availability Release the entire work immediately for access worldwide after my graduation.