The rate of data growth outpaces the decline of hardware costs, and there has been an ever-increasing demand in reducing the storage and network overhead for online database management systems (DBMSs). The most widely used approach for data reduction in DBMSs is blocklevel compression. Although this method is simple and effective, it fails to address redundancy across blocks and therefore leaves significant room for improvement for many applications. This dissertation proposes a systematic approach, termed similaritybased deduplication, which reduces the amount of data stored on disk and transmitted over the network beyond the benefits provided by traditional compression schemes. To demonstrate the approach, we designed and implemented dbDedup, a lightweight record-level similaritybased deduplication engine for online DBMSs. The design of dbDedup exploits key observations we find in database workloads, including small item sizes, temporal locality, and the incremental nature of record updates. The proposed approach differs from traditional chunk-based deduplication approaches in that, instead of finding identical chunks anywhere else in the data corpus, similarity-based deduplication identifies a single similar data-item and performs differential compression to remove the redundant parts for greater savings. To achieve high efficiency, dbDedup introduces novel encoding, caching and similarity selection techniques that significantly mitigate the deduplication overhead with minimal loss of compression ratio. For evaluation, we integrated dbDedup into the storage and replication components of a distributed NoSQL DBMS and analyzed its properties using four real datasets. Our results show that dbDedup achieves up to 37⇥ reduction in the storage size and replication traffic of the database on its own and up to 61⇥ reduction when paired with the DBMS’s block-level compression. dbDedup provides both benefits with negligible effect on DBMS throughput or client latency (average and tail).

A deduplicação consiste na tarefa de identificar quais objetos (registros, documentos, textos, etc.) são potencialmente os mesmos em uma base de dados (ou em um conjunto de bases de dados). A identificação de dados duplicados depende da intervenção do usuário, principalmente para a criação de um conjunto contendo pares duplicados e não duplicados. Tais informações são usadas para ajudar na identificação de outros possíveis pares duplicados presentes na base de dados. Em geral, quando a deduplicação é estendida para grandes conjuntos de dados, a eficiência e a qualidade das duplicatas dependem diretamente do “ajuste” de um usuário especialista. Nesse cenário, a configuração das principais etapas da deduplicação (etapas de blocagem e classificação) demandam que o usuário seja responsável pela tarefa pouco intuitiva de definir valores de limiares e, em alguns casos, fornecer pares manualmente rotulados. Desse modo, o processo de calibração exige que o usuário detenha um conhecimento prévio sobre as características específicas da base de dados e os detalhes do funcionamento do método de deduplicação. O objetivo principal desta tese é tratar do problema da configuração da deduplicação de grandes bases de dados, de modo a reduzir o esforço do usuário. O usuário deve ser somente requisitado para rotular um conjunto reduzido de pares automaticamente selecionados. Para isso, é proposta uma metodologia, chamada FS-Dedup, que incorpora algoritmos do estado da arte da deduplicação para permitir o processamento de grandes volumes de dados e adiciona um conjunto de estratégias com intuito de possibilitar a definição dos parâmetros do deduplicador, removendo os detalhes de configuração da responsabilidade do usuário. A metodologia pode ser vista como uma camada capaz de identificar as informações requisitadas pelo deduplicador (principalmente valores de limiares) a partir de um conjunto de pares rotulados pelo usuário. A tese propõe também uma abordagem que trata do problema da seleção dos pares informativos para a criação de um conjunto de treinamento reduzido. O desafio maior é selecionar um conjunto reduzido de pares suficientemente informativo para possibilitar a configuração da deduplicação com uma alta eficácia. Para isso, são incorporadas estratégias para reduzir o volume de pares candidatos a um algoritmo de aprendizagem ativa. Tal abordagem é integrada à metodologia FS-Dedup para possibilitar a remoção da intervenção especialista nas principais etapas da deduplicação. Por fim, um conjunto exaustivo de experimentos é executado com objetivo de validar as ideias propostas. Especificamente, são demonstrados os promissores resultados alcançados nos experimentos em bases de dados reais e sintéticas, com intuito de reduzir o número de pares manualmente rotulados, sem causar perdas na qualidade da deduplicação. / Deduplication is the task of identifying which objects (e.g., records, texts, documents, etc.) are potentially the same in a given dataset (or datasets). It usually requires user intervention in several stages of the process, mainly to ensure that pairs representing matchings and non-matchings can be determined. This information can be used to help detect other potential duplicate records. When deduplication is applied to very large datasets, the matching quality depends on expert users. The expert users are requested to define threshold values and produce a training set. This intervention requires user knowledge of the noise level of the data and a particular approach to deduplication so that it can be applied to configure the most important stages of the process (e.g. blocking and classification). The main aim of this thesis is to provide solutions to help in tuning the deduplication process in large datasets with a reduced effort from the user, who is only required to label an automatically selected subset of pairs. To achieve this, we propose a methodology, called FS-Dedup, which incorporates state-of-the-art algorithms in its deduplication core to address high performance issues. Following this, a set of strategies is proposed to assist in setting its parameters, and removing most of the detailed configuration concerns from the user. The methodology proposed can be regarded as a layer that is able to identify the specific information requested in the deduplication approach (mainly, threshold values) through pairs that are manually labeled by the user. Moreover, this thesis proposed an approach which would enable to select an informative set of pairs to produce a reduced training set. The main challenge here is how to select a “representative” set of pairs to configure the deduplication with high matching quality. In this context, the proposed approach incorporates an active learning method with strategies that allow the deduplication to be carried out on large datasets. This approach is integrated with the FS-Dedup methodology to avoid the need for a definition of threshold values in the most important deduplication stages. Finally, exhaustive experiments using both synthetic and real datasets have been conducted to validate the ideas outlined in this thesis. In particular, we demonstrate the ability of our approach to reduce the user effort without degrading the matching quality.

A deduplicação consiste na tarefa de identificar quais objetos (registros, documentos, textos, etc.) são potencialmente os mesmos em uma base de dados (ou em um conjunto de bases de dados). A identificação de dados duplicados depende da intervenção do usuário, principalmente para a criação de um conjunto contendo pares duplicados e não duplicados. Tais informações são usadas para ajudar na identificação de outros possíveis pares duplicados presentes na base de dados. Em geral, quando a deduplicação é estendida para grandes conjuntos de dados, a eficiência e a qualidade das duplicatas dependem diretamente do “ajuste” de um usuário especialista. Nesse cenário, a configuração das principais etapas da deduplicação (etapas de blocagem e classificação) demandam que o usuário seja responsável pela tarefa pouco intuitiva de definir valores de limiares e, em alguns casos, fornecer pares manualmente rotulados. Desse modo, o processo de calibração exige que o usuário detenha um conhecimento prévio sobre as características específicas da base de dados e os detalhes do funcionamento do método de deduplicação. O objetivo principal desta tese é tratar do problema da configuração da deduplicação de grandes bases de dados, de modo a reduzir o esforço do usuário. O usuário deve ser somente requisitado para rotular um conjunto reduzido de pares automaticamente selecionados. Para isso, é proposta uma metodologia, chamada FS-Dedup, que incorpora algoritmos do estado da arte da deduplicação para permitir o processamento de grandes volumes de dados e adiciona um conjunto de estratégias com intuito de possibilitar a definição dos parâmetros do deduplicador, removendo os detalhes de configuração da responsabilidade do usuário. A metodologia pode ser vista como uma camada capaz de identificar as informações requisitadas pelo deduplicador (principalmente valores de limiares) a partir de um conjunto de pares rotulados pelo usuário. A tese propõe também uma abordagem que trata do problema da seleção dos pares informativos para a criação de um conjunto de treinamento reduzido. O desafio maior é selecionar um conjunto reduzido de pares suficientemente informativo para possibilitar a configuração da deduplicação com uma alta eficácia. Para isso, são incorporadas estratégias para reduzir o volume de pares candidatos a um algoritmo de aprendizagem ativa. Tal abordagem é integrada à metodologia FS-Dedup para possibilitar a remoção da intervenção especialista nas principais etapas da deduplicação. Por fim, um conjunto exaustivo de experimentos é executado com objetivo de validar as ideias propostas. Especificamente, são demonstrados os promissores resultados alcançados nos experimentos em bases de dados reais e sintéticas, com intuito de reduzir o número de pares manualmente rotulados, sem causar perdas na qualidade da deduplicação. / Deduplication is the task of identifying which objects (e.g., records, texts, documents, etc.) are potentially the same in a given dataset (or datasets). It usually requires user intervention in several stages of the process, mainly to ensure that pairs representing matchings and non-matchings can be determined. This information can be used to help detect other potential duplicate records. When deduplication is applied to very large datasets, the matching quality depends on expert users. The expert users are requested to define threshold values and produce a training set. This intervention requires user knowledge of the noise level of the data and a particular approach to deduplication so that it can be applied to configure the most important stages of the process (e.g. blocking and classification). The main aim of this thesis is to provide solutions to help in tuning the deduplication process in large datasets with a reduced effort from the user, who is only required to label an automatically selected subset of pairs. To achieve this, we propose a methodology, called FS-Dedup, which incorporates state-of-the-art algorithms in its deduplication core to address high performance issues. Following this, a set of strategies is proposed to assist in setting its parameters, and removing most of the detailed configuration concerns from the user. The methodology proposed can be regarded as a layer that is able to identify the specific information requested in the deduplication approach (mainly, threshold values) through pairs that are manually labeled by the user. Moreover, this thesis proposed an approach which would enable to select an informative set of pairs to produce a reduced training set. The main challenge here is how to select a “representative” set of pairs to configure the deduplication with high matching quality. In this context, the proposed approach incorporates an active learning method with strategies that allow the deduplication to be carried out on large datasets. This approach is integrated with the FS-Dedup methodology to avoid the need for a definition of threshold values in the most important deduplication stages. Finally, exhaustive experiments using both synthetic and real datasets have been conducted to validate the ideas outlined in this thesis. In particular, we demonstrate the ability of our approach to reduce the user effort without degrading the matching quality.

A deduplicação consiste na tarefa de identificar quais objetos (registros, documentos, textos, etc.) são potencialmente os mesmos em uma base de dados (ou em um conjunto de bases de dados). A identificação de dados duplicados depende da intervenção do usuário, principalmente para a criação de um conjunto contendo pares duplicados e não duplicados. Tais informações são usadas para ajudar na identificação de outros possíveis pares duplicados presentes na base de dados. Em geral, quando a deduplicação é estendida para grandes conjuntos de dados, a eficiência e a qualidade das duplicatas dependem diretamente do “ajuste” de um usuário especialista. Nesse cenário, a configuração das principais etapas da deduplicação (etapas de blocagem e classificação) demandam que o usuário seja responsável pela tarefa pouco intuitiva de definir valores de limiares e, em alguns casos, fornecer pares manualmente rotulados. Desse modo, o processo de calibração exige que o usuário detenha um conhecimento prévio sobre as características específicas da base de dados e os detalhes do funcionamento do método de deduplicação. O objetivo principal desta tese é tratar do problema da configuração da deduplicação de grandes bases de dados, de modo a reduzir o esforço do usuário. O usuário deve ser somente requisitado para rotular um conjunto reduzido de pares automaticamente selecionados. Para isso, é proposta uma metodologia, chamada FS-Dedup, que incorpora algoritmos do estado da arte da deduplicação para permitir o processamento de grandes volumes de dados e adiciona um conjunto de estratégias com intuito de possibilitar a definição dos parâmetros do deduplicador, removendo os detalhes de configuração da responsabilidade do usuário. A metodologia pode ser vista como uma camada capaz de identificar as informações requisitadas pelo deduplicador (principalmente valores de limiares) a partir de um conjunto de pares rotulados pelo usuário. A tese propõe também uma abordagem que trata do problema da seleção dos pares informativos para a criação de um conjunto de treinamento reduzido. O desafio maior é selecionar um conjunto reduzido de pares suficientemente informativo para possibilitar a configuração da deduplicação com uma alta eficácia. Para isso, são incorporadas estratégias para reduzir o volume de pares candidatos a um algoritmo de aprendizagem ativa. Tal abordagem é integrada à metodologia FS-Dedup para possibilitar a remoção da intervenção especialista nas principais etapas da deduplicação. Por fim, um conjunto exaustivo de experimentos é executado com objetivo de validar as ideias propostas. Especificamente, são demonstrados os promissores resultados alcançados nos experimentos em bases de dados reais e sintéticas, com intuito de reduzir o número de pares manualmente rotulados, sem causar perdas na qualidade da deduplicação. / Deduplication is the task of identifying which objects (e.g., records, texts, documents, etc.) are potentially the same in a given dataset (or datasets). It usually requires user intervention in several stages of the process, mainly to ensure that pairs representing matchings and non-matchings can be determined. This information can be used to help detect other potential duplicate records. When deduplication is applied to very large datasets, the matching quality depends on expert users. The expert users are requested to define threshold values and produce a training set. This intervention requires user knowledge of the noise level of the data and a particular approach to deduplication so that it can be applied to configure the most important stages of the process (e.g. blocking and classification). The main aim of this thesis is to provide solutions to help in tuning the deduplication process in large datasets with a reduced effort from the user, who is only required to label an automatically selected subset of pairs. To achieve this, we propose a methodology, called FS-Dedup, which incorporates state-of-the-art algorithms in its deduplication core to address high performance issues. Following this, a set of strategies is proposed to assist in setting its parameters, and removing most of the detailed configuration concerns from the user. The methodology proposed can be regarded as a layer that is able to identify the specific information requested in the deduplication approach (mainly, threshold values) through pairs that are manually labeled by the user. Moreover, this thesis proposed an approach which would enable to select an informative set of pairs to produce a reduced training set. The main challenge here is how to select a “representative” set of pairs to configure the deduplication with high matching quality. In this context, the proposed approach incorporates an active learning method with strategies that allow the deduplication to be carried out on large datasets. This approach is integrated with the FS-Dedup methodology to avoid the need for a definition of threshold values in the most important deduplication stages. Finally, exhaustive experiments using both synthetic and real datasets have been conducted to validate the ideas outlined in this thesis. In particular, we demonstrate the ability of our approach to reduce the user effort without degrading the matching quality.

No description available.

Data quality is one of the key problems in data management. An unprecedented amount of data has been accumulated and has become a valuable asset of an organization. The value of the data relies greatly on its quality. However, data is often dirty in real life. It may be inconsistent, duplicated, stale, inaccurate or incomplete, which can reduce its usability and increase the cost of businesses. Consequently the need for improving data quality arises, which comprises of five central issues of improving data quality, namely, data consistency, data deduplication, data currency, data accuracy and information completeness. This thesis presents the results of our work on the first four issues with regards to data consistency, deduplication, currency and accuracy. The first part of the thesis investigates incremental verifications of data consistencies in distributed data. Given a distributed database D, a set S of conditional functional dependencies (CFDs), the set V of violations of the CFDs in D, and updates ΔD to D, it is to find, with minimum data shipment, changes ΔV to V in response to ΔD. Although the problems are intractable, we show that they are bounded: there exist algorithms to detect errors such that their computational cost and data shipment are both linear in the size of ΔD and ΔV, independent of the size of the database D. Such incremental algorithms are provided for both vertically and horizontally partitioned data, and we show that the algorithms are optimal. The second part of the thesis studies the interaction between record matching and data repairing. Record matching, the main technique underlying data deduplication, aims to identify tuples that refer to the same real-world object, and repairing is to make a database consistent by fixing errors in the data using constraints. These are treated as separate processes in most data cleaning systems, based on heuristic solutions. However, our studies show that repairing can effectively help us identify matches, and vice versa. To capture the interaction, a uniform framework that seamlessly unifies repairing and matching operations is proposed to clean a database based on integrity constraints, matching rules and master data. The third part of the thesis presents our study of finding certain fixes that are absolutely correct for data repairing. Data repairing methods based on integrity constraints are normally heuristic, and they may not find certain fixes. Worse still, they may even introduce new errors when attempting to repair the data, which may not work well when repairing critical data such as medical records, in which a seemingly minor error often has disastrous consequences. We propose a framework and an algorithm to find certain fixes, based on master data, a class of editing rules and user interactions. A prototype system is also developed. The fourth part of the thesis introduces inferring data currency and consistency for conflict resolution, where data currency aims to identify the current values of entities, and conflict resolution is to combine tuples that pertain to the same real-world entity into a single tuple and resolve conflicts, which is also an important issue for data deduplication. We show that data currency and consistency help each other in resolving conflicts. We study a number of associated fundamental problems, and develop an approach for conflict resolution by inferring data currency and consistency. The last part of the thesis reports our study of data accuracy on the longstanding relative accuracy problem which is to determine, given tuples t1 and t2 that refer to the same entity e, whether t1[A] is more accurate than t2[A], i.e., t1[A] is closer to the true value of the A attribute of e than t2[A]. We introduce a class of accuracy rules and an inference system with a chase procedure to deduce relative accuracy, and the related fundamental problems are studied. We also propose a framework and algorithms for inferring accurate values with users’ interaction.

Virtualization is a widely used technology for running multiple operating systems on a single set of hardware. Virtual machines running the same operating system have been shown to have a large amount of identical data, in such cases deduplication have been shown to be very effective in eliminating duplicated data. This study aimed to investigate if the storage savings are as large as shown in previous research, as well as to investigate if there are any negative performance impacts when using deduplication. The selected performance variables are resource utilisation and disk performance. The selected deduplication implementations are SDFS and ZFS deduplication. Each file system is tested with its respective non-deduplicated file systems, ext4 and ZFS. The results show that the storage savings are between 72,5 % and 73,65 % while the resource utilisation is generally higher when using deduplication. The results also show that deduplication using SDFS has an overall large negative disk performance impact, while ZFS deduplication has a general disk performance increase.

In the present work we study the record deduplication problem as an issue of data quality. We define duplicates as records having different syntax and the same semantics and which are representing the same real-world entity. The main goal of this work is to provide the overview of existing deduplication methods according to their requirements, results and usability. We focus on the comparison of two groups of record deduplication methods - with and without the domain knowledge. Therefore, the second part of this work is dedicated to the implementation of our method which does not utilize any domain knowledge and compare its results with the results of commercial tool deeply utilizing the domain knowledge.

Les fournisseurs de services de cloud computing, les réseaux sociaux et les entreprises de gestion des données ont assisté à une augmentation considérable du volume de données qu'ils reçoivent chaque jour. Toutes ces données créent des nouvelles opportunités pour étendre la connaissance humaine dans des domaines comme la santé, l'urbanisme et le comportement humain et permettent d'améliorer les services offerts comme la recherche, la recommandation, et bien d'autres. Ce n'est pas par accident que plusieurs universitaires mais aussi les médias publics se référent à notre époque comme l'époque “Big Data”. Mais ces énormes opportunités ne peuvent être exploitées que grâce à de meilleurs systèmes de gestion de données. D'une part, ces derniers doivent accueillir en toute sécurité ce volume énorme de données et, d'autre part, être capable de les restituer rapidement afin que les applications puissent bénéficier de leur traite- ment. Ce document se concentre sur ces deux défis relatifs aux “Big Data”. Dans notre étude, nous nous concentrons sur le stockage de sauvegarde (i) comme un moyen de protéger les données contre un certain nombre de facteurs qui peuvent les rendre indisponibles et (ii) sur le placement des données sur des systèmes de stockage répartis géographiquement, afin que les temps de latence perçue par l'utilisateur soient minimisés tout en utilisant les ressources de stockage et du réseau efficacement. Tout au long de notre étude, les données sont placées au centre de nos choix de conception dont nous essayons de tirer parti des propriétés de contenu à la fois pour le placement et le stockage efficace. / Cloud service providers, social networks and data-management companies are witnessing a tremendous increase in the amount of data they receive every day. All this data creates new opportunities to expand human knowledge in fields like healthcare and human behavior and improve offered services like search, recommendation, and many others. It is not by accident that many academics but also public media refer to our era as the “Big Data” era. But these huge opportunities come with the requirement for better data management systems that, on one hand, can safely accommodate this huge and constantly increasing volume of data and, on the other, serve them in a timely and useful manner so that applications can benefit from processing them. This document focuses on the above two challenges that come with “Big Data”. In more detail, we study (i) backup storage systems as a means to safeguard data against a number of factors that may render them unavailable and (ii) data placement strategies on geographically distributed storage systems, with the goal to reduce the user perceived latencies and the network and storage resources are efficiently utilized. Throughout our study, data are placed in the centre of our design choices as we try to leverage content properties for both placement and efficient storage.

Smartphones and tablets have been growing in popularity. These ultra mobile devices bring in new challenges for efficient network operations because of their mobility, resource constraints and richness of features. There is thus an increasing need to adapt network protocols to these devices and the traffic demands on wireless service providers. This dissertation focuses on identifying design limitations in existing network protocols when operating in ultra mobile environments and developing algorithmic solutions for the same. Our work comprises of three components. The first component identifies the shortcomings of TCP flow control algorithm when operating on resource constrained smartphones and tablets. We then propose an Adaptive Flow Control (AFC) algorithm for TCP that relies not just on the available buffer space but also on the application read-rate at the receiver. The second component of this work looks at network deduplication for mobile devices. With traditional network deduplication (dedup), the dedup source uses only the portion of the cache at the dedup destination that it is aware of. We argue in this work that in a mobile environment, the dedup destination (say the mobile) could have accumulated a much larger cache than what the current dedup source is aware of. In this context, we propose Asymmetric caching, a solution which allows the dedup destination to selectively feedback appropriate portions of its cache to the dedup source with the intent of improving the redundancy elimination efficiency. The third and final component focuses on leveraging network heterogeneity for prefetching on mobile devices. Our analysis of browser history of 24 iPhone users show that URLs do not repeat exactly. Users do show a lot of repetition in the domains they visit but not the particular URL. Additionally, mobile users access web content over diverse network technologies: WiFi and cellular (3G/4G). While data is unlimited over WiFi, users typically have monthly limits on data over the cellular network. In this context, we propose Precog, an action-based prefetching solution to reduce cellular data footprint on smartphones and tablets.