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.

Textual data, such as clinical notes, product or movie reviews in online stores, transcripts, chat records, and business documents, are widely collected nowadays and can be used to support a large spectrum of Big Data applications. At the same time, textual data, collected about individuals or from individuals, can be susceptible to inference attacks that may leak private and/or sensitive information about individuals.The increasing concerns of privacy risks in textual data preclude sharing or exchanging textual data across different parties/organizations for various applications such as record linkage, similar entity matching, natural language processing (NLP), or machine learning on large collections of textual data. This has led to the development of privacy preserving techniques for applying matching, machine learning or NLP techniques on textual data that contain personal and sensitive information about individuals. While cryptographic techniques are highly secure and accurate, they incur significant amount of computational cost for encoding and matching data – especially textual data – due to the complex nature of text.In this paper, we propose an efficient textual data encoding and matching algorithm using probabilistic techniques based on counting Bloom filters combined with Differential privacy. We apply our algorithm to a popular use case scenario that involves privacy preserving topic modeling – a widely used NLP technique – in order to identify common or collective topics in texts across multiple parties without learning the individual topics of each party, and show its effectiveness in supporting this application. Finally, through extensive experimental evaluation on three large text datasets against a state-of-the-art probabilistic encoding algorithm for privacy preserving LDA topic modelling, we show that our method provides a better privacy-utility trade-off at the cost of more computation complexity and memory space, while still being computationally efficient (log-linear complexity in the size of documents) for Big data compared to cryptographic techniques that have quadratic complexity.

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.

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.