Abstract
Entity Resolution (ER)—the process of identifying records that refer to the same real-world entity—is a critical task in data management. Traditional offline ER is often impractical for massive or externally hosted datasets. This paper presents a framework for query-time ER, enabling accurate, on-the-fly deduplication. By combining collective resolution with an adaptive expansion strategy, the proposed method achieves high accuracy in seconds, even on large-scale, noisy datasets.
Introduction
Entity Resolution is a classic "big data" challenge. Most existing systems are designed for offline processing, cleaning an entire database at once. However, as datasets grow to millions of records and are increasingly accessed via third-party interfaces (e.g., CiteSeer, PubMed), full-scale offline ER becomes computationally prohibitive. This paper addresses the challenge of resolving entities specifically for a given query, such as "Find all papers by author 'W. Wang'," providing quick and accurate results without requiring a fully cleaned database.
Methodology: The "Expand and Resolve" Framework
The primary challenge in query-time ER is that high-accuracy "collective" resolution depends on a network of relationships (e.g., co-authorship). This can lead to an "explosive" expansion of records to process. The authors propose a two-stage strategy:
1. Extraction Phase
Starting from the query, the system uses two operators:
- Attribute Expansion ($X_A$): Identifies records with similar attributes (e.g., similar names).
- Hyper-edge Expansion ($X_H$): Identifies related records through shared relationships, such as co-authorship on a paper.
2. Resolution Phase
The system performs Relational Clustering (RC-ER) on the extracted subset. This greedy algorithm merges clusters based on both attribute similarity and the similarity of their relational "neighborhoods."
To maintain performance, the authors introduce Adaptive Query Expansion. This technique uses "ambiguity estimation" to prioritize expanding the most informative records while ignoring those that add little value, preventing the extraction phase from pulling in excessive amounts of data.
Experimental Evaluation
The approach was evaluated on three primary datasets:
- arXiv: A high-energy physics citation dataset (~58k references, ~9k authors).
- Elsevier BioBase: A large biology publication database (~832k references). This dataset is particularly challenging due to high ambiguity (e.g., use of initials only).
- Synthetic Data: Used to test the algorithm's robustness against varying relationship density and attribute noise.
Key Results
- Accuracy: The RC-ER method significantly outperformed attribute-only baselines. On BioBase, it achieved an F1 score of 0.82, compared to 0.70 for the baseline.
- Performance: Queries on the arXiv dataset were resolved in an average of 1.36 seconds.
- Scalability: On BioBase, adaptive expansion reduced the relevant record set from ~44,000 to ~3,700, making query-time resolution feasible where it was previously impossible.
Discussion
A key insight from this work is that the gains in precision and recall from collective resolution follow a geometric progression, meaning most accuracy benefits are captured within a few expansion steps (depth 1 to 3). However, the authors also note that relationships can be counterproductive if they are too ambiguous.
Future work includes automating parameter tuning, implementing dynamic expansion depths based on real-time ambiguity levels, and utilizing caching to speed up overlapping queries.
Summary updated