Theoretical limits of microclustering for record linkage.
Ontology highlight
ABSTRACT:
SUBMITTER: Johndrow JE
PROVIDER: S-EPMC5963577 | biostudies-literature | 2018 Jun
REPOSITORIES: biostudies-literature
Publications
Theoretical limits of microclustering for record linkage.
Johndrow J E JE Lum K K Dunson D B DB
Biometrika 20180319 2
There has been substantial recent interest in record linkage, where one attempts to group the records pertaining to the same entities from one or more large databases that lack unique identifiers. This can be viewed as a type of microclustering, with few observations per cluster and a very large number of clusters. We show that the problem is fundamentally hard from a theoretical perspective and, even in idealized cases, accurate entity resolution is effectively impossible unless the number of e ...[more]
Similar Datasets
Project description:Studies involving the use of probabilistic record linkage are becoming increasingly common. However, the methods underpinning probabilistic record linkage are not widely taught or understood, and therefore these studies can appear to be a 'black box' research tool. In this article, we aim to describe the process of probabilistic record linkage through a simple exemplar. We first introduce the concept of deterministic linkage and contrast this with probabilistic linkage. We illustrate each step of the process using a simple exemplar and describe the data structure required to perform a probabilistic linkage. We describe the process of calculating and interpreting matched weights and how to convert matched weights into posterior probabilities of a match using Bayes theorem. We conclude this article with a brief discussion of some of the computational demands of record linkage, how you might assess the quality of your linkage algorithm, and how epidemiologists can maximize the value of their record-linked research using robust record linkage methods.
| S-EPMC5005943 | biostudies-literature
Project description:For the past 80 years, social scientists have been linking historical censuses across time to study economic and geographic mobility. In recent decades, the quantity of historical census record linkage has exploded, owing largely to the advent of new machine-readable data created by genealogical organizations. Investigators are examining economic and geographic mobility across multiple generations, but also engaging many new topics. Several analysts are exploring the effects of early-life socioeconomic conditions, environmental exposures, or natural disasters on family, health and economic outcomes in later life. Other studies exploit natural experiments to gauge the impact of policy interventions such as social welfare programs and educational reforms. The new data sources have led to a proliferation of record linkage methodology, and some widespread approaches inadvertently introduce errors that can lead to false inferences. A new generation of large-scale shared data infrastructure now in preparation will ameliorate weaknesses of current linkage methods.
| S-EPMC6200350 | biostudies-literature
Project description:To achieve mass, power and cost reduction, there is a trend to reduce the volume of many instruments aboard spacecraft, especially for small spacecraft (cubesats or nanosats) with very limited mass, volume and power budgets. With the current trend of miniaturizing spacecraft instruments one could naturally ask if is there a physical limit to this process for star sensors. This paper shows that there is a fundamental limit on star sensor accuracy, which depends on stellar distribution, star sensor dimensions and exposure time. An estimate of this limit is given for our location in the galaxy.
| S-EPMC6960684 | biostudies-literature
Project description:ObjectiveRecord linkage to integrate uncoordinated databases is critical in biomedical research using Big Data. Balancing privacy protection against the need for high quality record linkage requires a human-machine hybrid system to safely manage uncertainty in the ever changing streams of chaotic Big Data.MethodsIn the computer science literature, private record linkage is the most published area. It investigates how to apply a known linkage function safely when linking two tables. However, in practice, the linkage function is rarely known. Thus, there are many data linkage centers whose main role is to be the trusted third party to determine the linkage function manually and link data for research via a master population list for a designated region. Recently, a more flexible computerized third-party linkage platform, Secure Decoupled Linkage (SDLink), has been proposed based on: (1) decoupling data via encryption, (2) obfuscation via chaffing (adding fake data) and universe manipulation; and (3) minimum information disclosure via recoding.ResultsWe synthesize this literature to formalize a new framework for privacy preserving interactive record linkage (PPIRL) with tractable privacy and utility properties and then analyze the literature using this framework.ConclusionsHuman-based third-party linkage centers for privacy preserving record linkage are the accepted norm internationally. We find that a computer-based third-party platform that can precisely control the information disclosed at the micro level and allow frequent human interaction during the linkage process, is an effective human-machine hybrid system that significantly improves on the linkage center model both in terms of privacy and utility.
| S-EPMC3932473 | biostudies-literature
Project description:BackgroundThe linkage of records which refer to the same entity in separate data collections is a common requirement in public health and biomedical research. Traditionally, record linkage techniques have required that all the identifying data in which links are sought be revealed to at least one party, often a third party. This necessarily invades personal privacy and requires complete trust in the intentions of that party and their ability to maintain security and confidentiality. Dusserre, Quantin, Bouzelat and colleagues have demonstrated that it is possible to use secure one-way hash transformations to carry out follow-up epidemiological studies without any party having to reveal identifying information about any of the subjects - a technique which we refer to as "blindfolded record linkage". A limitation of their method is that only exact comparisons of values are possible, although phonetic encoding of names and other strings can be used to allow for some types of typographical variation and data errors.MethodsA method is described which permits the calculation of a general similarity measure, the n-gram score, without having to reveal the data being compared, albeit at some cost in computation and data communication. This method can be combined with public key cryptography and automatic estimation of linkage model parameters to create an overall system for blindfolded record linkage.ResultsThe system described offers good protection against misdeeds or security failures by any one party, but remains vulnerable to collusion between or simultaneous compromise of two or more parties involved in the linkage operation. In order to reduce the likelihood of this, the use of last-minute allocation of tasks to substitutable servers is proposed. Proof-of-concept computer programmes written in the Python programming language are provided to illustrate the similarity comparison protocol.ConclusionAlthough the protocols described in this paper are not unconditionally secure, they do suggest the feasibility, with the aid of modern cryptographic techniques and high speed communication networks, of a general purpose probabilistic record linkage system which permits record linkage studies to be carried out with negligible risk of invasion of personal privacy.
| S-EPMC471556 | biostudies-literature
Project description:Diamond is the hardest natural material, but its practical strength is low and its elastic deformability extremely limited. While recent experiments have demonstrated that diamond nanoneedles can sustain exceptionally large elastic tensile strains with high tensile strengths, the size- and orientation-dependence of these properties remains unknown. Here we report maximum achievable tensile strain and strength of diamond nanoneedles with various diameters, oriented in <100>, <110> and <111> -directions, using in situ transmission electron microscopy. We show that reversible elastic deformation depends both on nanoneedle diameter and orientation. <100> -oriented nanoneedles with a diameter of 60 nm exhibit highest elastic tensile strain (13.4%) and tensile strength (125 GPa). These values are comparable with the theoretical elasticity and Griffith strength limits of diamond, respectively. Our experimental data, together with first principles simulations, indicate that maximum achievable elastic strain and strength are primarily determined by surface conditions of the nanoneedles.
| S-EPMC6892892 | biostudies-literature
Project description:IntroductionThe robustness of record linkage evaluation measures is of high importance since linkage techniques are assessed based on these. However, minimal research has been conducted to evaluate the suitability of existing evaluation measures in the context of linking groups of records. Linkage quality is generally evaluated based on traditional measures such as precision and recall. As we show, these traditional evaluation measures are not suitable for evaluating groups of linked records because they evaluate the quality of individual record pairs rather than the quality of records grouped into clusters.ObjectivesWe set out to highlight the shortcomings of traditional evaluation measures and then propose a novel method to evaluate clustering quality in the context of group-based record linkage.MethodsThe proposed linkage evaluation method assesses how well individual records have been allocated into predicted groups/clusters with respect to ground-truth data. We first identify the best representative predicted cluster for each ground-truth cluster and, based on the resulting mapping, each record in a ground-truth cluster is assigned to one of seven categories. These categories reflect how well the linkage technique assigned records into groups.ResultsWe empirically evaluated our proposed method using real-world data and showed that it better reflects the quality of clusters generated by three group-based record linkage techniques. We also showed that traditional measures such as precision and recall can produce ambiguous results whereas our method does not.ConclusionsThe proposed evaluation method provides unambiguous results regarding the assessed group-based record linkage approaches. The method comprises of seven categories which reflect how each record was predicted, providing more detailed information about the quality of the linkage result. This will help to make better-informed decisions about which linkage technique is best suited for a given linkage application.
| S-EPMC8142966 | biostudies-literature
Project description:Population genetic theory shows that the efficacy of natural selection is limited by linkage-selection at one site interferes with selection at linked sites. Such interference slows adaptation in asexual genomes and may explain the evolutionary advantage of sex. Here, we test for two signatures of constraint caused by linkage in a sexual genome, by using sequence data from 255 Drosophila melanogaster and Drosophila simulans loci. We find that (i) the rate of protein adaptation is reduced in regions of low recombination, and (ii) evolution at strongly selected amino acid sites interferes with optimal codon usage at weakly selected, tightly linked synonymous sites. Together these findings suggest that linkage limits the rate and degree of adaptation even in recombining genomes.
| S-EPMC129723 | biostudies-literature
Project description:Linkage analysis in autotetraploid species has been an historical challenge in quantitative genetics theory and is a stumbling block that urgently needs to be removed in the rapidly emerging genome research on this species, such as cultivated potato. This article presents theory of a full model of tetrasomic linkage and develops a statistical framework for the linkage analysis. The model considers both double reduction and recombination, the most essential features of tetrasomic inheritance with linked loci, whereas the statistical method takes appropriate account of the major complexities in analyzing both dominant and codominant molecular marker data during map reconstruction in tetraploid species. These complexities include the problems arising from multiple dosage of allelic inheritance, the null allele, allelic segregation distortion, mixed bivalent and quadrivalent pairing in meiosis, and incomplete information of marker phenotype data. The theoretical analysis established the relationship between the coefficients of double reduction at linked loci, which is essential in the present tetrasomic linkage analysis and in assessing the impact of double reduction on the evolution of tetraploid populations. The statistical method, based on the combination of theoretical analysis and a computer-based algorithm, provided analytical tools for predicting the maximum-likelihood estimates of the model parameters. A simulation study showed the feasibility of a practical implementation of the method, detailed the procedure of the analysis, validated the power and reliability in the parameter estimation, and compared the present method with those proposed in the current literature.
| S-EPMC406462 | biostudies-literature
Project description:BackgroundWithin the field of record linkage, numerous data cleaning and standardisation techniques are employed to ensure the highest quality of links. While these facilities are common in record linkage software packages and are regularly deployed across record linkage units, little work has been published demonstrating the impact of data cleaning on linkage quality.MethodsA range of cleaning techniques was applied to both a synthetically generated dataset and a large administrative dataset previously linked to a high standard. The effect of these changes on linkage quality was investigated using pairwise F-measure to determine quality.ResultsData cleaning made little difference to the overall linkage quality, with heavy cleaning leading to a decrease in quality. Further examination showed that decreases in linkage quality were due to cleaning techniques typically reducing the variability - although correct records were now more likely to match, incorrect records were also more likely to match, and these incorrect matches outweighed the correct matches, reducing quality overall.ConclusionsData cleaning techniques have minimal effect on linkage quality. Care should be taken during the data cleaning process.
| S-EPMC3688507 | biostudies-literature