Suchergebnisse

ABSTRACT
ObjectiveRecent years have seen the development of novel techniques for linking complex types of data that contain records about different types of entities, for example bibliographic databases with records about authors, publications, and venues. Advanced approaches have been devised to link individuals and groups of records. These approaches exploit both the similarities between record attributes as well as the relationships between entities. Rather than linking records about different types of entities, in this work we study the novel problem of linking records where the same entity can have different roles and where these roles can change over time.
ApproachWe specifically develop novel techniques for linking historical birth, death, marriage, and census certificates with the aim to reconstruct the population covered by these certificates over a period of time. Our techniques make use of constraints that consider roles, relationships, as well as time. Our first technique links certificates based on the specific roles of their individuals, and greedily selects pairs of certificates with the highest overall similarity while also considering 1-to-1 and 1-to-many linkage constraints. Our second hybrid technique combines graph, group, and temporal linkage, and also considers relationship information between individuals and groups. We compare these techniques with state-of-the-art group, collective, and graph-based linkage approaches.
ResultsWe evaluate our proposed techniques on real Scottish data from 1861 to 1901 that cover the population of the Isle of Skye. In total, these data sets contain 119,042 certificates for 234,365 individuals. As ground truth we have a set of life-segments of records manually linked by domain experts. Our results indicate that even advanced techniques have difficulty in achieving high linkage quality compared to careful manual linkage. Two reasons for this are the very small name pool in our data and the changing nature of people's personal details over time. Both our proposed techniques, however, significantly outperform traditional pair-wise attribute similarity and group linkage approaches, with the greedy role-based technique achieving better results than the hybrid technique.
ConclusionOur experiments on real data show that even with advanced linkage techniques that employ group, graph, relationship, and temporal approaches it is challenging to achieve high quality links from complex data such as birth, death, marriage and census certificates that span several decades. As future work we will improve all steps of our techniques with the goal of developing highly accurate, scalable, and automatic techniques for linking large-scale complex population databases.

Databases covering all individuals of a population are increasingly used for research and decision-making. The massive size of such databases is often mistaken as a guarantee for valid inferences. However, population data have characteristics that make them challenging to use. Various assumptions on population coverage and data quality are commonly made, including how such data were captured and what types of processing have been applied to them. Furthermore, the full potential of population data can often only be unlocked when such data are linked to other databases. Record linkage often implies subtle technical problems, which are easily missed. We discuss a diverse range of myths and misconceptions relevant for anybody capturing, processing, linking, or analysing population data. Remarkably, many of these myths and misconceptions are due to the social nature of data collections and are therefore missed by purely technical accounts of data processing. Many are also not well documented in scientific publications. We conclude with a set of recommendations for using population data.

ObjectivesPopulation databases containing birth, death, and marriage certificates or census records, are increasingly used for studies in a variety of research domains. Their large scale and complexity make linking such databases highly challenging. We present a scalable blocking and linking technique that exploits temporal and spatial constraints in personal data.
ApproachBased on a state-of-the-art blocking method using locality sensitive hashing (LSH), we incorporate (a) attribute similarities, (b) temporal constraints (for example, a mother cannot give birth to two babies less than nine months apart, besides a multiple birth), and (c) spatial constraints (two births by the same mother are more likely to happen in the same location than far apart). In an iterative fashion, we identify highly confident matches first, and use these matches to further refine our constraints. We adopt a block size and frequency-based filtering approach to further enhance the efficiency of the record linkage comparison step.
ResultsWe conducted experiments on a Scottish data set containing 17,613 birth certificates from 1861 to 1901, where the application of standard LSH blocking generated approximately 15 million candidate record pairs, with a recall of 0.999 and a precision of 0.003. With the application of our block size and frequency-based filtering approach we obtained a ten-fold and hundred-fold reduction of this candidate record pair set with a small reduction of recall to 0.984 and 0.962, respectively. The comparison of record pairs in the hundred-fold reduction using our iterative linking technique achieved up-to 0.961 precision and 0.811 recall. This means that our method can achieve a reduction in computational efforts, and improvement in precision of over 99% at the cost of a decline in recall below 19%.
ConclusionWe presented a method to reduce the computational complexity of linking large and complex population databases while ensuring high linkage quality. Our method can be generalised to population databases where temporal and spatial constraints can be defined. We plan to apply our method on a Scottish database with 24 million records.

ObjectivesDatabases covering full populations are increasingly used for research studies. Their massive size is often mistaken as a guarantee for valid inferences on the population of interest. However, population data have characteristics that make them challenging to use. We discuss misconceptions about how population data were captured, processed, and linked.
ApproachWe define population data as data about people at the level of a population. The focus on populations is important, as it refers to the scale and complexity of such data, which make manual processing and data quality assessment challenging. Personal data include quasi-identifiers such as names and addresses, as well as microdata such as people's medical details.
Little consideration has been given to how assumptions about population data can influence the outcomes of a research study. Only few publications describe experiences or challenges when dealing with population data. Many of the misconceptions we discuss are therefore drawn from our experiences over decades working with real-world population databases in collaborations with both private and public sector organisations.
ResultsWe identified 32 misconceptions about population data, 21 due to how data are captured (among them "a database contains all individuals in a population", "records in a population database always refer to real people", "data definitions are unambiguous", and "missing data have no meaning"); four due to data processing (including "data processing is always correct" and "metadata are correct, complete, and up-to-date"); and seven due to data linkage (such as "a linked data set corresponds to an actual population", "a linked data set is unbiased", and "linkage error rates are independent of database size").
ConclusionDue to misconceptions like those we have identified, careful consideration is needed when personal data at the level of populations are used for research studies. There are no (simple) technical solutions to detect and correct many of these misconceptions; heightened awareness is required by anybody working with population data. We will provide recommendations to help recognise and overcome such misconceptions.

IntroductionApplications in domains ranging from healthcare to national security increasingly require records about individuals in sensitive databases to be linked in privacy-preserving ways. Missing values make the linkage process challenging because they can affect the encoding of attribute values. No study has systematically investigated how missing values affect the outcomes of different encoding techniques used in privacy-preserving linkage applications.
Objectives and ApproachBinary encodings, such as Bloom filters, are popular for linking sensitive databases. They are now employed in real-world linkage applications. However, existing encoding techniques assume the quasi-identifying attributes used for encoding to be complete. Missing values can lead to incomplete encodings which can result in decreased or increased similarities and therefore to false non-matches or false matches. In this study we empirically evaluate three binary encoding techniques using real voter databases, where pairs of records that correspond to the same voter (with name or address changes) resulted in files of 100,000 and 500,000 records containing from 0% to 50% missing values.
ResultsWe encoded between two and four of the attributes first and last name, street, and city into three record-level binary encodings: Cryptographic long-term key (CLK) [Schnell et al. 2009], record-level Bloom filter (RBF) [Durham et al. 2014], and tabulation Min-hashing (TBH) [Smith 2017]. Experiments showed a 10% to 25% drop on average in both precision and recall for all encoding techniques when missing values are increasing. CLK resulted in the highest decrease in precision, while TBH resulted in the highest decrease in recall compared to the other encoding techniques.
ConclusionBinary encodings such as Bloom filters are now used in practical applications for linking sensitive databases. Our evaluation shows that such encoding techniques can result in lower linkage quality if there are missing values in quasi-identifying attributes. This highlights the need for novel encoding techniques that can overcome the challenge of missing values.

IntroductionDue to privacy concerns personal identifiers used for linking data often have to be encoded (masked) before being linked across organisations. Bloom filter (BF) encoding is a popular privacy technique that is now employed in real-world linkage applications. Recent research has however shown that BFs are vulnerable to cryptanalysis attacks.
Objectives and ApproachAttacks on BFs either exploit that encoding frequent plain-text values (such as common names) results in corresponding frequent BFs, or they apply pattern mining to identify co-occurring BF bit positions that correspond to frequent encoded q-grams (sub-strings). In this study we empirically evaluated the privacy of individuals encoded in BFs against two recent cryptanalysis attack methods by Christen et al. (2017/2018). We used two snapshots of the North Carolina Voter Registration database for our evaluation, where pairs of records corresponding to the same voter (with name or address variations) resulted in files with 222,251 BFs and 224,061 plain-text records, respectively.
ResultsWe encoded between two and four of the fields first and last name, street, and city into one BF per record. For combinations of three and four fields all plain-text values and BFs were unique, challenging any frequency-based attack. For hardening BFs, different suggested methods (balancing, random hashing, XOR, BLIP, and salting) were applied.
Without any hardening applied up to 20.7% and 5% of plain-text values were correctly re-identified as 1-to-1 matches by both the pattern-mining and frequency-based attack methods, respectively. No more than 5\% correct 1-to-1 re-identification matches were achieved with the frequency-based attack on BFs encoding two fields when either balancing, random hashing, or XOR folding was applied; while the pattern-mining based attack was not successful in any correct re-identifications for any hardening technique.
Conclusion/ImplicationsGiven that BF encoding is now being employed in real-world linkage applications, it is important to study the limits of this privacy technique. Our experimental evaluation shows that although basic BFs without hardening technique are susceptible to cryptanalysis attacks, some hardening techniques are able to protect BFs against these attacks.

ObjectivesDemographers are interested in the degree to which marriage is driven by prenuptial pregnancy within particular communities. To help answer this question, we present a novel method which links marriage certificates to birth certificates, where the birth-mother is the marriage-bride, considering only births which occur in the first seven months after a marriage.
ApproachTo identify prenuptial births we employed an unsupervised graph-based record linkage method to link birth and marriage certificates. We first extracted related groups of individuals: babies and their parents from birth certificates, and brides, grooms, and their parents from marriage certificates. To link births with marriages, we employed techniques to address challenges such as changing attribute values over time (such as names and addresses), the ambiguity of attribute values giving priority to rare names over common names, and different relationships encountered at different points in time (by applying temporal constraints). Based on the obtained links we then extracted prenuptial births.
ResultsUsing two Scottish data sets containing a total of 38,451 births and 8,667 marriage certificates from the period 1861 to 1901 and employing different linkage thresholds we identified between 853 and 945 first birth-marriage links in the smaller (rural) data set, and between 2,165 and 2,232 links in the larger (urban) data set. In the rural data set, between 16.9% and 17.7% of these links were with birth less than 8 months after marriage (i.e. prenuptial births), where the corresponding ground truth contained 17.6% prenuptial births. For the urban data set, we identified between 51.3% and 51.4% prenuptial births. Our results show clear differences between rural and urban prenuptial pregnancies in 19th Century Scotland.
ConclusionWe have presented an unsupervised graph-based record linkage method that compares attribute values of individuals and their relationships to link records based on the ambiguity of attribute values, attribute value changes, and temporal constraints. This linking process helps us to identify prenuptial births to help us understand the degree to which marriages may have been driven by pregnancy.

IntroductionThe linking of sensitive databases containing personal identifying information across organisations is an increasingly important task in application domains ranging from health and social science research to national censuses. Various techniques have been developed to facilitate the linking of sensitive databases while at the same time preserving the privacy of individuals represented in these databases.
Objectives and approachWe present several case studies where the privacy-preserving linking of sensitive databases is crucial, and then discuss the advantages and limitations of existing algorithms and techniques to link sensitive databases. We discuss privacy techniques such as Bloom filter encoding, hashing, and secure multi-party computation, from the point of view of a linkage practitioner. We highlight those aspects that are important when selecting or implementing a privacy-preserving linkage technique within practical applications.
ResultsConceptually, linkage techniques can be evaluated across three main dimensions linkage quality, scalability to linking large or multiple databases, and the privacy protection provided by a technique. From a practical perspective, however, several other dimensions are crucial, including the availability of software or ease of implementation, technical knowledge available in an organisation, and the suitability of techniques for a given linkage scenario. Our analysis of a diverse range of linkage techniques has shown that currently no technique provides an adequate solution along all conceptual as well as all practical dimensions.
ConclusionsMore research is required to develop novel techniques that facilitate the privacy-preserving linkage of large sensitive databases across organisations; including new encoding methods and cryptanalysis attacks (where until now most attacks have neglected the attack vectors that likely occur in practice), and novel evaluation measures to assess the privacy provided by linkage techniques. We encourage practitioners to be aware of the identified limitations – as well as the opportunities – of existing privacy-preserving linkage techniques and carefully assess the technical and organisational requirements of such techniques within their institution.

Data linkage, the process of identifying records that refer to the same entities across databases, is a crucial component of Population Data Science. Data linkage has a history going back over fifty years with many different methods and techniques being developed in various disciplines including computer science, statistics, and health informatics. Data linkage researchers and practitioners are commonly only familiar with methods and techniques that have been developed or are used in their own discipline, and they often only follow research that is being published at venues in their own discipline. There is currently no single online resource that allows data linkage researchers and practitioners across different disciplines to exchange ideas, post questions, or advertise new publications, software, open positions, or upcoming conferences and workshops. This leads to a communication gap in the multi-disciplinary field of data linkage. We aim to address this gap with the DLforum, a public online discussion forum for data linkage. DLforum contains several discussion areas, including publication announcements, resources (software and data sets), information about upcoming conferences and workshops, job opportunities, and general questions related to data linkage. The forum includes a moderation process where all registered users can post content and reply to posts by other users. We anticipate that the number of users registered and the amount of content posted in the forum will show that such an online forum is of value to data linkage researchers and practitioners from different disciplines to effectively communicate and exchange their knowledge, and thus form an online community of practice. In this paper we describe the methods of developing the DLforum, its structure and content, and our plan on how to evaluate the forum. The DLforum is freely available at: https://dmm.anu.edu.au/DLforum/

Techniques for integrating data from diverse sources have attracted significant interest in recent years. Much of today's data collected by businesses and governments are about people, and integrating such data across organizations can raise privacy concerns. Various techniques that preserve privacy during data integration have been developed, but several challenges persist that need to be solved before such techniques become useful in practical applications. We elaborate on these challenges and discuss research directions.

Diverse online social networks are becoming increasingly interconnected by sharing information. Accordingly, emergent macro-level phenomena have been observed, such as the synchronous spread of information across different types of social media. Attempting to analyze the emergent global behavior is impossible from the examination of a single social platform, and dynamic influences between different social networks are not negligible. Furthermore, the underlying structural property of networks is important, as it drives the diffusion process in a stochastic way. In this paper, we propose a macro-level diffusion model with a probabilistic approach by combining both the heterogeneity and structural connectivity of social networks. As real-world phenomena, we explore instances of news diffusion across different social media platforms from a dataset that contains over 386 million web documents covering a one-month period in early 2011. We find that influence between different media types is varied by the context of information. News media are the most influential in the arts and economy categories, while social networking sites (SNS) and blog media are in the politics and culture categories, respectively. Furthermore, controversial topics, such as political protests and multiculturalism failure, tend to spread concurrently across social media, while entertainment topics, such as film releases and celebrities, are more likely driven by interactions within single social platforms. We expect that the proposed model applies to a wider class of diffusion phenomena in diverse fields and that it provides a way of interpreting the dynamics of diffusion in terms of the strength and directionality of influences among populations.

It is estimated that between 80% and 90% of governmental data collections contain address information, Geocoding - the process of assigning geographic coordinates to addresses - is becoming increasingly important in application areas that involve the analysis and mining of such data. In many cases, address records are captured and/or stored in a free-form or inconsistent manner. This fact complicates the task of accurately matching such addresses to spatially-annotated reference data. In this paper we describe a geocoding system that is based on a comprehensive high-quality geocoded national address database. It uses a learning address parser based on hidden Markov models to segment free-form addresses into components, and a rule-based matching engine to determine the best matches to the reference database.

It is estimated that between 80% and 90% of governmental data collections contain address information, Geocoding - the process of assigning geographic coordinates to addresses - is becoming increasingly important in application areas that involve the analysis and mining of such data. In many cases, address records are captured and/or stored in a free-form or inconsistent manner. This fact complicates the task of accurately matching such addresses to spatially-annotated reference data. In this paper we describe a geocoding system that is based on a comprehensive high-quality geocoded national address database. It uses a learning address parser based on hidden Markov models to segment free-form addresses into components, and a rule-based matching engine to determine the best matches to the reference database.

Techniques for integrating data from diverse sources have attracted significant interest in recent years. Much of today's data collected by businesses and governments are about people, and integrating such data across organizations can raise privacy concerns. Various techniques that preserve privacy during data integration have been developed, but several challenges persist that need to be solved before such techniques become useful in practical applications. We elaborate on these challenges and discuss research directions.