The Experts below are selected from a list of 11118 Experts worldwide ranked by ideXlab platform

Lise Getoor - One of the best experts on this subject based on the ideXlab platform.

  • collective Entity Resolution in familial networks
    International Conference on Data Mining, 2017
    Co-Authors: Pigi Kouki, Jay Pujara, Christopher Steven Marcum, Laura M Koehly, Lise Getoor
    Abstract:

    Entity Resolution in settings with rich relational structure often introduces complex dependencies between co-references. Exploiting these dependencies is challenging - it requires seamlessly combining statistical, relational, and logical dependencies. One task of particular interest is Entity Resolution in familial networks. In this setting, multiple partial representations of a family tree are provided, from the perspective of different family members, and the challenge is to reconstruct a family tree from these multiple, noisy, partial views. This reconstruction is crucial for applications such as understanding genetic inheritance, tracking disease contagion, and performing census surveys. Here, we design a model that incorporates statistical signals, such as name similarity, relational information, such as sibling overlap, and logical constraints, such as transitivity and bijective matching, in a collective model. We show how to integrate these features using probabilistic soft logic, a scalable probabilistic programming framework. In experiments on real-world data, our model significantly outperforms state-of-the-art classifiers that use relational features but are incapable of collective reasoning.

  • Generic Statistical Relational Entity Resolution in Knowledge Graphs.
    arXiv: Artificial Intelligence, 2016
    Co-Authors: Jay Pujara, Lise Getoor
    Abstract:

    Entity Resolution, the problem of identifying the underlying Entity of references found in data, has been researched for many decades in many communities. A common theme in this research has been the importance of incorporating relational features into the Resolution process. Relational Entity Resolution is particularly important in knowledge graphs (KGs), which have a regular structure capturing entities and their interrelationships. We identify three major problems in KG Entity Resolution: (1) intra-KG reference ambiguity; (2) inter-KG reference ambiguity; and (3) ambiguity when extending KGs with new facts. We implement a framework that generalizes across these three settings and exploits this regular structure of KGs. Our framework has many advantages over custom solutions widely deployed in industry, including collective inference, scalability, and interpretability. We apply our framework to two real-world KG Entity Resolution problems, ambiguity in NELL and merging data from Freebase and MusicBrainz, demonstrating the importance of relational features.

  • Entity Resolution for big data
    Knowledge Discovery and Data Mining, 2013
    Co-Authors: Lise Getoor, Ashwin Machanavajjhala
    Abstract:

    Entity Resolution (ER), the problem of extracting, matching and resolving Entity mentions in structured and unstructured data, is a long-standing challenge in database management, information retrieval, machine learning, natural language processing and statistics. Accurate and fast Entity Resolution has huge practical implications in a wide variety of commercial, scientific and security domains. Despite the long history of work on Entity Resolution, there is still a surprising diversity of approaches, and lack of guiding theory. Meanwhile, in the age of big data, the need for high quality Entity Resolution is growing, as we are inundated with more and more data, all of which needs to be integrated, aligned and matched, before further utility can be extracted. In this tutorial, we bring together perspectives on Entity Resolution from a variety of fields, including databases, information retrieval, natural language processing and machine learning, to provide, in one setting, a survey of a large body of work. We discuss both the practical aspects and theoretical underpinnings of ER. We describe existing solutions, current challenges and open research problems. In addition to giving attendees a thorough understanding of existing ER models, algorithms and evaluation methods, the tutorial will cover important research topics such as scalable ER, active and lightly supervised ER, and query-driven ER.

  • KDD - Entity Resolution for big data
    Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, 2013
    Co-Authors: Lise Getoor, Ashwin Machanavajjhala
    Abstract:

    Entity Resolution (ER), the problem of extracting, matching and resolving Entity mentions in structured and unstructured data, is a long-standing challenge in database management, information retrieval, machine learning, natural language processing and statistics. Accurate and fast Entity Resolution has huge practical implications in a wide variety of commercial, scientific and security domains. Despite the long history of work on Entity Resolution, there is still a surprising diversity of approaches, and lack of guiding theory. Meanwhile, in the age of big data, the need for high quality Entity Resolution is growing, as we are inundated with more and more data, all of which needs to be integrated, aligned and matched, before further utility can be extracted. In this tutorial, we bring together perspectives on Entity Resolution from a variety of fields, including databases, information retrieval, natural language processing and machine learning, to provide, in one setting, a survey of a large body of work. We discuss both the practical aspects and theoretical underpinnings of ER. We describe existing solutions, current challenges and open research problems. In addition to giving attendees a thorough understanding of existing ER models, algorithms and evaluation methods, the tutorial will cover important research topics such as scalable ER, active and lightly supervised ER, and query-driven ER.

  • Interactive Entity Resolution in Relational Data: A Visual Analytic Tool and Its Evaluation
    IEEE transactions on visualization and computer graphics, 2008
    Co-Authors: Hyunmo Kang, Lise Getoor, Mustafa Bilgic, Ben Shneiderman, Louis Licamele
    Abstract:

    Databases often contain uncertain and imprecise references to real-world entities. Entity Resolution, the process of reconciling multiple references to underlying real-world entities, is an important data cleaning process required before accurate visualization or analysis of the data is possible. In many cases, in addition to noisy data describing entities, there is data describing the relationships among the entities. This relational data is important during the Entity Resolution process; it is useful both for the algorithms which determine likely database references to be resolved and for visual analytic tools which support the Entity Resolution process. In this paper, we introduce a novel user interface, D-Dupe, for interactive Entity Resolution in relational data. D-Dupe effectively combines relational Entity Resolution algorithms with a novel network visualization that enables users to make use of an Entity's relational context for making Resolution decisions. Since Resolution decisions often are interdependent, D-Dupe facilitates understanding this complex process through animations which highlight combined inferences and a history mechanism which allows users to inspect chains of Resolution decisions. An empirical study with 12 users confirmed the benefits of the relational context visualization on the performance of Entity Resolution tasks in relational data in terms of time as well as users' confidence and satisfaction.

Vasilis Verroios - One of the best experts on this subject based on the ideXlab platform.

  • top k Entity Resolution with adaptive locality sensitive hashing
    International Conference on Data Engineering, 2019
    Co-Authors: Vasilis Verroios, Hector Garciamolina
    Abstract:

    Given a set of records, Entity Resolution algorithms find all the records referring to each Entity. In top-k Entity Resolution, the goal is to find all the records referring to the k largest (in terms of number of records) entities. Top-k Entity Resolution is driven by many modern applications that operate over just the few most popular entities in a dataset. In this paper we introduce the problem of top-k Entity Resolution and we summarize a novel approach for this problem; full details are presented in a technical report. Our approach is based on locality-sensitive hashing, and can very rapidly and accurately process massive datasets. Our key insight is to adaptively decide how much processing each record requires to ascertain if it refers to a top-k Entity or not: the less likely a record is to refer to a top-k Entity, the less it is processed. The heavily reduced amount of processing for the vast majority of records that do not refer to top-k entities, leads to significant speedups. Our experiments with images, web articles, and scientific publications show a 2x to 25x speedup compared to traditional approaches for high-dimensional data.

  • ICDE - Top-K Entity Resolution with Adaptive Locality-Sensitive Hashing
    2019 IEEE 35th International Conference on Data Engineering (ICDE), 2019
    Co-Authors: Vasilis Verroios, Hector Garcia-molina
    Abstract:

    Given a set of records, Entity Resolution algorithms find all the records referring to each Entity. In top-k Entity Resolution, the goal is to find all the records referring to the k largest (in terms of number of records) entities. Top-k Entity Resolution is driven by many modern applications that operate over just the few most popular entities in a dataset. In this paper we introduce the problem of top-k Entity Resolution and we summarize a novel approach for this problem; full details are presented in a technical report. Our approach is based on locality-sensitive hashing, and can very rapidly and accurately process massive datasets. Our key insight is to adaptively decide how much processing each record requires to ascertain if it refers to a top-k Entity or not: the less likely a record is to refer to a top-k Entity, the less it is processed. The heavily reduced amount of processing for the vast majority of records that do not refer to top-k entities, leads to significant speedups. Our experiments with images, web articles, and scientific publications show a 2x to 25x speedup compared to traditional approaches for high-dimensional data.

  • waldo an adaptive human interface for crowd Entity Resolution
    International Conference on Management of Data, 2017
    Co-Authors: Vasilis Verroios, Hector Garciamolina, Yannis Papakonstantinou
    Abstract:

    In Entity Resolution, the objective is to find which records of a dataset refer to the same real-world Entity. Crowd Entity Resolution uses humans, in addition to machine algorithms, to improve the quality of the outcome. We study a hybrid approach that combines two common interfaces for human tasks in Crowd Entity Resolution, taking into account key observations about the advantages and disadvantages of the two interfaces. We give a formal definition to the problem of human task selection and we derive algorithms with strong optimality guarantees. Our experiments with four real-world datasets show that our hybrid approach gives an improvement of 50% to 300% in the crowd cost to resolve a dataset, compared to using a single interface.

  • SIGMOD Conference - Waldo: An Adaptive Human Interface for Crowd Entity Resolution
    Proceedings of the 2017 ACM International Conference on Management of Data, 2017
    Co-Authors: Vasilis Verroios, Hector Garcia-molina, Yannis Papakonstantinou
    Abstract:

    In Entity Resolution, the objective is to find which records of a dataset refer to the same real-world Entity. Crowd Entity Resolution uses humans, in addition to machine algorithms, to improve the quality of the outcome. We study a hybrid approach that combines two common interfaces for human tasks in Crowd Entity Resolution, taking into account key observations about the advantages and disadvantages of the two interfaces. We give a formal definition to the problem of human task selection and we derive algorithms with strong optimality guarantees. Our experiments with four real-world datasets show that our hybrid approach gives an improvement of 50% to 300% in the crowd cost to resolve a dataset, compared to using a single interface.

Indrajit Bhattacharya - One of the best experts on this subject based on the ideXlab platform.

  • Query-time Entity Resolution
    Journal of Artificial Intelligence Research, 2007
    Co-Authors: Indrajit Bhattacharya, Lise Getoor
    Abstract:

    Entity Resolution is the problem of reconciling database references corresponding to the same real-world entities. Given the abundance of publicly available databases that have unresolved entities, we motivate the problem of query-time Entity Resolution: quick and accurate Resolution for answering queries over such 'unclean' databases at query-time. Since collective Entity Resolution approaches -- where related references are resolved jointly -- have been shown to be more accurate than independent attribute-based Resolution for off-line Entity Resolution, we focus on developing new algorithms for collective Resolution for answering Entity Resolution queries at query-time. For this purpose, we first formally show that, for collective Resolution, precision and recall for individual entities follow a geometric progression as neighbors at increasing distances are considered. Unfolding this progression leads naturally to a two stage 'expand and resolve' query processing strategy. In this strategy, we first extract the related records for a query using two novel expansion operators, and then resolve the extracted records collectively. We then show how the same strategy can be adapted for query-time Entity Resolution by identifying and resolving only those database references that are the most helpful for processing the query. We validate our approach on two large real-world publication databases where we show the usefulness of collective Resolution and at the same time demonstrate the need for adaptive strategies for query processing. We then show how the same queries can be answered in real-time using our adaptive approach while preserving the gains of collective Resolution. In addition to experiments on real datasets, we use synthetically generated data to empirically demonstrate the validity of the performance trends predicted by our analysis of collective Entity Resolution over a wide range of structural characteristics in the data.

  • Collective Entity Resolution in relational data
    ACM Transactions on Knowledge Discovery from Data, 2007
    Co-Authors: Indrajit Bhattacharya, Lise Getoor
    Abstract:

    Many databases contain uncertain and imprecise references to real-world entities. The absence of identifiers for the underlying entities often results in a database which contains multiple references to the same Entity. This can lead not only to data redundancy, but also inaccuracies in query processing and knowledge extraction. These problems can be alleviated through the use of Entity Resolution. Entity Resolution involves discovering the underlying entities and mapping each database reference to these entities. Traditionally, entities are resolved using pairwise similarity over the attributes of references. However, there is often additional relational information in the data. Specifically, references to different entities may cooccur. In these cases, collective Entity Resolution, in which entities for cooccurring references are determined jointly rather than independently, can improve Entity Resolution accuracy. We propose a novel relational clustering algorithm that uses both attribute and relational information for determining the underlying domain entities, and we give an efficient implementation. We investigate the impact that different relational similarity measures have on Entity Resolution quality. We evaluate our collective Entity Resolution algorithm on multiple real-world databases. We show that it improves Entity Resolution performance over both attribute-based baselines and over algorithms that consider relational information but do not resolve entities collectively. In addition, we perform detailed experiments on synthetically generated data to identify data characteristics that favor collective relational Resolution over purely attribute-based algorithms.

  • a latent dirichlet model for unsupervised Entity Resolution
    SIAM International Conference on Data Mining, 2005
    Co-Authors: Indrajit Bhattacharya, Lise Getoor
    Abstract:

    Entity Resolution has received considerable attention in recent years. Given many references to underlying entities, the goal is to predict which references correspond to the same Entity. We show how to extend the Latent Dirichlet Allocation model for this task and propose a probabilistic model for collective Entity Resolution for relational domains where references are connected to each other. Our approach differs from other recently proposed Entity Resolution approaches in that it is a) generative, b) does not make pair-wise decisions and c) captures relations between entities through a hidden group variable. We propose a novel sampling algorithm for collective Entity Resolution which is unsupervised and also takes Entity relations into account. Additionally, we do not assume the domain of entities to be known and show how to infer the number of entities from the data. We demonstrate the utility and practicality of our relational Entity Resolution approach for author Resolution in two real-world bibliographic datasets. In addition, we present preliminary results on characterizing conditions under which relational information is useful.

  • SDM - A Latent Dirichlet Model for Unsupervised Entity Resolution
    2005
    Co-Authors: Indrajit Bhattacharya, Lise Getoor
    Abstract:

    Entity Resolution has received considerable attention in recent years. Given many references to underlying entities, the goal is to predict which references correspond to the same Entity. We show how to extend the Latent Dirichlet Allocation model for this task and propose a probabilistic model for collective Entity Resolution for relational domains where references are connected to each other. Our approach differs from other recently proposed Entity Resolution approaches in that it is a) generative, b) does not make pair-wise decisions and c) captures relations between entities through a hidden group variable. We propose a novel sampling algorithm for collective Entity Resolution which is unsupervised and also takes Entity relations into account. Additionally, we do not assume the domain of entities to be known and show how to infer the number of entities from the data. We demonstrate the utility and practicality of our relational Entity Resolution approach for author Resolution in two real-world bibliographic datasets. In addition, we present preliminary results on characterizing conditions under which relational information is useful.

Hector Garcia-molina - One of the best experts on this subject based on the ideXlab platform.

  • ICDE - Top-K Entity Resolution with Adaptive Locality-Sensitive Hashing
    2019 IEEE 35th International Conference on Data Engineering (ICDE), 2019
    Co-Authors: Vasilis Verroios, Hector Garcia-molina
    Abstract:

    Given a set of records, Entity Resolution algorithms find all the records referring to each Entity. In top-k Entity Resolution, the goal is to find all the records referring to the k largest (in terms of number of records) entities. Top-k Entity Resolution is driven by many modern applications that operate over just the few most popular entities in a dataset. In this paper we introduce the problem of top-k Entity Resolution and we summarize a novel approach for this problem; full details are presented in a technical report. Our approach is based on locality-sensitive hashing, and can very rapidly and accurately process massive datasets. Our key insight is to adaptively decide how much processing each record requires to ascertain if it refers to a top-k Entity or not: the less likely a record is to refer to a top-k Entity, the less it is processed. The heavily reduced amount of processing for the vast majority of records that do not refer to top-k entities, leads to significant speedups. Our experiments with images, web articles, and scientific publications show a 2x to 25x speedup compared to traditional approaches for high-dimensional data.

  • SIGMOD Conference - Waldo: An Adaptive Human Interface for Crowd Entity Resolution
    Proceedings of the 2017 ACM International Conference on Management of Data, 2017
    Co-Authors: Vasilis Verroios, Hector Garcia-molina, Yannis Papakonstantinou
    Abstract:

    In Entity Resolution, the objective is to find which records of a dataset refer to the same real-world Entity. Crowd Entity Resolution uses humans, in addition to machine algorithms, to improve the quality of the outcome. We study a hybrid approach that combines two common interfaces for human tasks in Crowd Entity Resolution, taking into account key observations about the advantages and disadvantages of the two interfaces. We give a formal definition to the problem of human task selection and we derive algorithms with strong optimality guarantees. Our experiments with four real-world datasets show that our hybrid approach gives an improvement of 50% to 300% in the crowd cost to resolve a dataset, compared to using a single interface.

  • Developments in Generic Entity Resolution.
    IEEE Data(base) Engineering Bulletin, 2011
    Co-Authors: Steven Euijong Whang, Hector Garcia-molina
    Abstract:

    Entity Resolution (ER) is the problem of identifying which records in a database refer to the same Entity. Although ER is a well-known problem, the rapid increase of data has made ER a challenging problem in many application areas ranging from resolving shopping items to counter-terrorism. The SERF project at Stanford focuses on providing scalable and accurate ER techniques that can be used across applications. We introduce generic ER and explain the recent advances made in our project.

  • ER - Entity Resolution: Overview and Challenges
    Lecture Notes in Computer Science, 2004
    Co-Authors: Hector Garcia-molina
    Abstract:

    Entity Resolution is a problem that arises in many information integration scenarios: We have two or more sources containing records on the same set of real-world entities (e.g., customers). However, there are no unique identifiers that tell us what records from one source correspond to those in the other sources. Furthermore, the records representing the same Entity may have differing information, e.g., one record may have the address misspelled, another record may be missing some fields. An Entity Resolution algorithm attempts to identify the matching records from multiple sources (i.e., those corresponding to the same real-world Entity), and merges the matching records as best it can. Entity Resolution algorithms typically rely on user-defined functions that (a) compare fields or records to determine if they match (are likely to represent the same real world Entity), and (b) merge matching records into one, and in the process perhaps combine fields (e.g., creating a new name based on two slightly different versions of the name).

Hector Garciamolina - One of the best experts on this subject based on the ideXlab platform.

  • top k Entity Resolution with adaptive locality sensitive hashing
    International Conference on Data Engineering, 2019
    Co-Authors: Vasilis Verroios, Hector Garciamolina
    Abstract:

    Given a set of records, Entity Resolution algorithms find all the records referring to each Entity. In top-k Entity Resolution, the goal is to find all the records referring to the k largest (in terms of number of records) entities. Top-k Entity Resolution is driven by many modern applications that operate over just the few most popular entities in a dataset. In this paper we introduce the problem of top-k Entity Resolution and we summarize a novel approach for this problem; full details are presented in a technical report. Our approach is based on locality-sensitive hashing, and can very rapidly and accurately process massive datasets. Our key insight is to adaptively decide how much processing each record requires to ascertain if it refers to a top-k Entity or not: the less likely a record is to refer to a top-k Entity, the less it is processed. The heavily reduced amount of processing for the vast majority of records that do not refer to top-k entities, leads to significant speedups. Our experiments with images, web articles, and scientific publications show a 2x to 25x speedup compared to traditional approaches for high-dimensional data.

  • waldo an adaptive human interface for crowd Entity Resolution
    International Conference on Management of Data, 2017
    Co-Authors: Vasilis Verroios, Hector Garciamolina, Yannis Papakonstantinou
    Abstract:

    In Entity Resolution, the objective is to find which records of a dataset refer to the same real-world Entity. Crowd Entity Resolution uses humans, in addition to machine algorithms, to improve the quality of the outcome. We study a hybrid approach that combines two common interfaces for human tasks in Crowd Entity Resolution, taking into account key observations about the advantages and disadvantages of the two interfaces. We give a formal definition to the problem of human task selection and we derive algorithms with strong optimality guarantees. Our experiments with four real-world datasets show that our hybrid approach gives an improvement of 50% to 300% in the crowd cost to resolve a dataset, compared to using a single interface.

  • joint Entity Resolution
    International Conference on Data Engineering, 2012
    Co-Authors: Steven Euijong Whang, Hector Garciamolina
    Abstract:

    Entity Resolution (ER) is the problem of identifying which records in a database represent the same Entity. Often, records of different types are involved (e.g., authors, publications, institutions, venues), and resolving records of one type can impact the Resolution of other types of records. In this paper we propose a flexible, modular Resolution framework where existing ER algorithms developed for a given record type can be plugged in and used in concert with other ER algorithms. Our approach also makes it possible to run ER on subsets of similar records at a time, important when the full data is too large to resolve together. We study the scheduling and coordination of the individual ER algorithms in order to resolve the full data set. We then evaluate our joint ER techniques on synthetic and real data and show the scalability of our approach.