Record linkage holds a crucial position in data management and analysis by identifying and merging records from disparate data sets that pertain to the same real-world entity. As data volumes grow, the intricacies of record linkage amplify, presenting challenges, such as potential redundancies and computational complexities. This paper introduces DynaHash, a novel randomized record linkage mechanism that utilizes (a) the MinHash technique to generate compact representations of blocking keys and (b) Hamming Locality-Sensitive Hashing (LSH) to construct the blocking structure from these vectors. By employing these methods, DynaHash offers theoretical guarantees of accuracy and achieves sublinear runtime complexities, with appropriate parameter tuning. It comprises two key components: a persistent storage system for permanently storing the blocking structure to ensure complete results, and an in-memory component for generating very fast partial results by summarizing the persisted blocking structure. Additionally, DynaHash leverages Multi-Probe matching to scan multiple neighboring blocks, in terms of their Hamming distances, in order to find matches. Our theoretical work derives a decrease factor in the space requirements, which depends on the Hamming threshold, compared with the baseline LSH. Our experimental evaluation against three state-of-the-art methods on six real-world data sets demonstrates DynaHash’s exceptional recall rates and query times, which are at least 2 × faster than its competitors and do not depend on the size of the underlying data sets.

Organizations leverage massive volumes of information and new types of data to generate unprecedented insights and improve their outcomes. Correctly identifying duplicate records that represent the same entity, such as user, customer, patient and so on, a process commonly known as record linkage, can improve service levels, accelerate sales, or elevate healthcare decision support. Towards this direction, blocking methods are used with the aim to group matching records in the same block using a combination of their attributes as blocking keys. This paper introduces a suite of randomized algorithms specifically crafted for streaming record linkage settings. Using a bounded in-memory data structure, in terms of the number of blocks and positions within each block, our algorithms guarantee that the most frequently accessed and the most recently used blocks remain in main memory and, additionally, the records within a block are renewed on a rolling basis. The operation of our algorithms rely on simple random choices, instead of utilizing cumbersome sorting data structures, which ensure that the probability of inactive blocks and older records to remain in main memory decays in order to free space for more promising blocks and fresher records, respectively. We also introduce an algorithm that performs approximate blocking to tackle the problem of misspellings and typos present in the blocking keys. The experimental evaluation showcases that our proposed algorithms scale efficiently to data streams by providing certain accuracy guarantees.

A huge amount of data, in terms of streams, are collected nowadays via a variety of sources, such as sensors, mobile devices, or even raw log files. The unprecedented rate at which these data are generated and collected calls for novel record linkage methods to identify matching records pairs, which refer to the same real-world entity. Towards this direction, blocking methods are used in order to reduce the number of candidate record pairs while still maintaining high levels of accuracy. This paper introduces ExpBlock, a randomized record linkage structure, which guarantees that both the most frequently accessed and recently used blocks remain in main memory and, additionally, the records within a block are renewed on a rolling basis. Specifically, the probability of inactive blocks and older records to remain in main memory decays in order to make room for more promising blocks and fresher records, respectively. We implement these features using random choices instead of utilizing cumbersome sorting data structures in order to favour simplicity of implementation and efficiency. We showcase, through the experimental evaluation, that ExplBlock scales efficiently to data streams by providing accurate results in a timely fashion.

Progressive entity resolution techniques aim to allow linking vast amounts of records, coming from disparate data sources, in a way that provides early access to linkage results of high recall. However, existing methods suffer from serious limitations, as they either assume a nearly uniform distribution of record pairs in each block, or they use a sorted neighborhood approach which incurs a significant d elay i n t he r eporting of linkage results and can miss matching record pairs.In response, in this paper we introduce MULTIBLOCK, a progressive multi-iterative method that breaks down the matching step of entity resolution into a number of iterations, generating as many matching record pairs as possible upfront, to quickly resolve each block regardless of its size. MULTIBLOCK guarantees the formulation of each record pair with a fixed probability, and iteratively provides accurate estimates of the proportion of matching record pairs. It has linear complexity with the number of blocks and no dependence on the records of the data sets, which is important in large-scale settings. Additionally, MULTIBLOCK can adapt to any progressive algorithm that generates blocks of arbitrary sizes. Through experimental evaluation, using three real-world data sets consisting of millions of record pairs, we show that our approach outperforms four state-of-the-art methods in both accuracy and efficiency, b eing a t l east twice faster than its competitors.

Nowadays, a vast amount of information is collected in real-time on a daily basis via users' handheld devices, web-based applications, and customer service interactions (among many others). The sheer volume of this data and the unprecedented rate at which it becomes available for processing, potentially combined with other attributes that are commonly met in traditional data sets, calls for novel online record linkage1techniques that can handle streams of data to discover records that refer to the same real-world entity.This paper introduces UniBlock, an online record linkage approach, supported by a novel data structure, that can adapt to any blocking algorithm to separate the most frequently accessed blocks from the rest, and maintain these blocks in main memory. In UniBlock, this separation is performed in a randomized way, where the probability of eviction of a block is inversely proportional to its frequency of access, empowering our approach with simplicity and effectiveness. Additionally, UniBlock provides accurate estimations of the proportion of matching record pairs in the underlying data sets in sublinear running time. Through experimental evaluation, we show that our approach outperforms the state-of-the-art methods in both accuracy and efficiency, being able to scale well to data streams.

In privacy-preserving record linkage, a number of data custodians encode their records and submit them to a trusted third-party who is responsible for identifying those records that refer to the same real-world entity. In this paper, we propose FEDERAL, a novel record linkage framework that implements methods for anonymizing both string and numerical data values, which are typically present in data records. These methods rely on a strong theoretical foundation for rigorously specifying the dimensionality of the anonymization space, into which the original values are embedded, to provide accuracy and privacy guarantees under various models of privacy attacks. A key component of the applied embedding process is the threshold that is required by the distance computations, which we prove can be formally specified to guarantee accurate results. We evaluate our framework using three real-world data sets with varying characteristics. Our experimental findings show that FEDERAL offers a complete and effective solution for accurately identifying matching anonymized record pairs (with recall rates constantly above 93 percent) in large-scale privacy-preserving record linkage tasks.

In this work, we propose Bit Vectors (BV), an accurate, distance-preserving encoding scheme for representing numerical data values in privacy-preserving tasks. Although many methods have been proposed in the literature for encoding strings, the problem of encoding numerical values has not been effectively addressed yet. In Privacy-Preserving Record Linkage (PPRL), a number of data custodians encode their records and submit them to a trusted third-party that is responsible to identify those records that refer to the same real-world entity. BV is supported by a strong theoretical foundation for embedding numerical values into an anonymization space in a way that preserves the initial distances. Key components of this embedding process are (a) the employed hash functions which, by utilizing random intervals, they allow for approximate matching, and (b) the threshold that is required by the distance computations, which we prove that can be specified in a way that guarantees accurate results.

Record linkage, the process of identifying similar records that correspond to the same real-world entities across databases, is a well-established research problem in the database, data mining, and information retrieval communities. Computing distances between string values of records is the key component in order to determine the similarity of the represented entities. Due to the typically large volumes of records, a two-step process is followed. A blocking mechanism is first applied for grouping similar records together, and then a matching mechanism is performed for comparing the records which have been inserted into the same block. However, there does not exist any efficient blocking/matching mechanism which provides theoretical guarantees for identifying similar records which consist of strings. Towards this end, we put forth the novel notion of embedding string-based records into a Hamming space, where such a mechanism exists. The size of these embeddings is kept as small as needed in order to guarantee the correspondence of distances in that space to the types of errors that exist between strings, e.g., a missing or a modified character. We build embeddings whose size is 120 bits for representing accurately four fields of a publicly available data set. We also present a distance threshold-aware blocking technique for higher accuracy rates compared to blocking approaches which ignore the specified threshold. Our empirical study conducted on real-world data sets shows the efficacy achieved by our embedding method as compared to several existing solutions.

When dealing with sensitive and personal user data, the process of record linkage raises privacy issues. Thus, privacy preserving record linkage has emerged with the goal of identifying matching records across multiple data sources while preserving the privacy of the individuals they describe. The task is very resource demanding, considering the abundance of available data, which, in addition, are often dirty. Blocking techniques are deployed prior to matching to prune out unlikely to match candidate records so as to reduce processing time. However, when scaling to large datasets, such methods often result in quality loss. To this end, we propose Multi-Sampling Transitive Closure for Encrypted Fields (MS-TCEF), a novel privacy preserving blocking technique based on the use of reference sets. Our new method effectively prunes records based on redundant assignments to blocks, providing better fault-tolerance and maintaining result quality while scaling linearly with respect to the dataset size. We provide a theoretical analysis on the method's complexity and show how it outperforms state-of-the-art privacy preserving blocking techniques with respect to both recall and processing cost.

We present a Λ-fold Redundant Blocking Framework, that relies on the Locality-Sensitive Hashing technique for identifying candidate record pairs, which have undergone an anonymization transformation. In this context, we demonstrate the usage and evaluate the performance of a variety of families of hash functions used for blocking. We illustrate that the performance attained is highly correlated to the distance-preserving properties of the anonymization format used. The parameters, of the blocking scheme, are optimally selected so that we achieve the highest possible accuracy in the least possible running time. We also introduce an SMC-based protocol in order to compare the formulated record pairs homomorphically, without running the risk of breaching the privacy of the underlying records.

Integrating data from diverse sources with the aim to identify similar records that refer to the same real-world entities without compromising privacy of these entities is an emerging research problem in various domains. This problem is known as privacy-preserving record linkage (PPRL). Scalability of PPRL is a main challenge due to growing data size in real-world applications. Private blocking techniques have been used in PPRL to address this challenge by reducing the number of record pair comparisons that need to be conducted. Many of these private blocking techniques require a trusted third party to perform the blocking. One main threat with three-party solutions is the collusion between parties to identify the private data of another party.

Positioning capabilities offered in modern mobile devices enable usage of location-based services. Privacy and security is of great importance for related applications. We present a framework that allows conducting research on anonymity techniques in a real-life environment using smartphones. The proposed solution also includes logging mechanisms that facilitate positioning research dataset development in open format. To present the capabilities of the solution, we deliver the concept of K-anonymity to protect mobile users that issue queries to location-based services. Experimental evaluation of the solution includes development of real-life logging dataset using smartphones by volunteers. Different flavours of anonymity algorithms are easy to be included and tested. The solution has received encouraging feedback and successfully assists the researchers of location based services to experiment, validate and develop their techniques in real life environment.

The widespread adoption of location based services (LBSs) coupled with recent advances in location tracking technologies, pose serious concerns to user privacy. As a consequence, privacy preserving approaches have been proposed to protect the location information which is communicated during a request for an LBS. Most existing approaches are centralized as they rely on a trusted server to protect the real location of the user. Although the centralized approaches are commonplace, so far no attempt has been made to integrate them in a unified framework. Such an integration would provide the means for easily implementing and testing new techniques by offering ready-made vanilla system components and allow for both the experimental and analytical evaluation of the implemented techniques.In this paper we propose PLOT, an open-ended toolbox that allows the implementation and the evaluation of privacy-enhancing algorithms for LBSs. PLOT offers a variety of interesting features: (i) it supports both real and synthetic movement data, (ii) it relies on spatial DBMSs to efficiently handle movement data as well as the underlying model of user movement, (iii) it offers tools for mobile data preprocessing, movement reconstruction and segmentation, (iv) it allows the implementation of both network-based and free-terrain solutions to location privacy, (v) it provides the infrastructure for second-chance approaches when the main location privacy approach fails, (vi) it implements strategies for the identification of frequent patterns in user movement, and finally (vii) it offers an extended set of visualization tools that both provide insight on the workings of the implemented solutions and facilitate the qualitative and quantitative evaluation of their behavior.

In this paper, we propose a privacy model that offers trajectory privacy to the requesters of Location-Based Services (LBSs), by utilizing an underlying network of user movement. The privacy model has been implemented as a framework that (i) reconstructs the user movement from a series of independent location updates, (ii) identifies routes where user privacy is at risk, and (iii) anonymizes online user requests for LBSs to protect the requester for as long as the service withstands completion. In order to achieve (iii), we propose two anonymization techniques, the K–present (weak) and the K–frequent (strong) trajectory anonymity, and a second chance approach that takes over when anonymization fails to ensure that the privacy of the user is preserved. To the best of our knowledge, this is the first work to propose a trajectory privacy model that utilizes an underlying network of user movement to offer in an interactive way personalized privacy to online user requests on trajectory data.

In this paper, we propose a novel, exact border-based approach that provides an optimal solution for the hiding of sensitive frequent itemsets by (i) minimally extending the original database by a synthetically generated database part - the database extension, (ii) formulating the creation of the database extension as a constraint satisfaction problem, (iii) mapping the constraint satisfaction problem to an equivalent binary integer programming problem, (iv) exploiting underutilized synthetic transactions to proportionally increase the support of non-sensitive itemsets, (v) minimally relaxing the constraint satisfaction problem to provide an approximate solution close to the optimal one when an ideal solution does not exist, and (vi) by using a partitioning in the universe of the items to increase the efficiency of the proposed hiding algorithm. Extending the original database for sensitive itemset hiding is proved to provide optimal solutions to an extended set of hiding problems compared to previous approaches and to provide solutions of higher quality. Moreover, the application of binary integer programming enables the simultaneous hiding of the sensitive itemsets and thus allows for the identification of globally optimal solutions.

Often, in the real world, entities have two or more representations in databases. Duplicate records do not share a common key and/or they contain errors that make duplicate matching a difficult task. Errors are introduced as the result of transcription errors, incomplete information, lack of standard formats, or any combination of these factors. In this paper, we present a thorough analysis of the literature on duplicate record detection. We cover similarity metrics that are commonly used to detect similar field entries, and we present an extensive set of duplicate detection algorithms that can detect approximately duplicate records in a database. We also cover multiple techniques for improving the efficiency and scalability of approximate duplicate detection algorithms. We conclude with coverage of existing tools and with a brief discussion of the big open problems in the area

The rapid growth of transactional data brought, soon enough, into attention the need of its further exploitation. In this paper, we investigate the problem of securing sensitive knowledge from being exposed in patterns extracted during association rule mining. Instead of hiding the produced rules directly, we decide to hide the sensitive frequent itemsets that may lead to the production of these rules. As a first step, we introduce the notion of distance between two databases and a measure for quantifying it. By trying to minimize the distance between the original database and its sanitized version (that can safely be released), we propose a novel, exact algorithm for association rule hiding and evaluate it on real world datasets demonstrating its effectiveness towards solving the problem. Copyright 2006 ACM.

Large repositories of data contain sensitive information that must be protected against unauthorized access. The protection of the confidentiality of this information has been a long-term goal for the database security research community and for the government statistical agencies. Recent advances in data mining and machine learning algorithms have increased the disclosure risks that one may encounter when releasing data to outside parties. A key problem, and still not sufficiently investigated, is the need to balance the confidentiality of the disclosed data with the legitimate needs of the data users. Every disclosure limitation method affects, in some way, and modifies true data values and relationships. We investigate confidentiality issues of a broad category of rules, the association rules. In particular, we present three strategies and five algorithms for hiding a group of association rules, which is characterized as sensitive. One rule is characterized as sensitive if its disclosure risk is above a certain privacy threshold. Sometimes, sensitive rules should not be disclosed to the public since, among other things, they may be used for inferring sensitive data, or they may provide business competitors with an advantage. We also perform an evaluation study of the hiding algorithms in order to analyze their time complexity and the impact that they have in the original database.

Data cleaning is a vital process that ensures the quality of data stored in real-world databases. Data cleaning problems are frequently encountered in many research areas, such as knowledge discovery in databases, data warehousing, system integration and e-services. The process of identifying the record pairs that represent the same entity (duplicate records), commonly known as record linkage, is one of the essential elements of data cleaning. In this paper, we address the record linkage problem by adopting a machine learning approach. Three models are proposed and are analyzed empirically. Since no existing model, including those proposed in this paper, has been proved to be superior, we have developed an interactive record linkage toolbox named TAILOR (backwards acronym for "RecOrd LInkAge Toolbox"). Users of TAILOR can build their own record linkage models by tuning system parameters and by plugging in in-house-developed and public-domain tools. The proposed toolbox serves as a framework for the record linkage process, and is designed in an extensible way to interface with existing and future record linkage models. We have conducted an extensive experimental study to evaluate our proposed models using not only synthetic but also real data. The results show that the proposed machine-learning record linkage models outperform the existing ones both in accuracy and in performance.