Entity Resolution via Batched Oracle Queries
This work addresses the practical need for cost-effective entity resolution in large datasets where oracle queries are limited, offering a principled approach with theoretical guarantees.
The authors formalize the problem of entity resolution with a batched oracle that clusters records in limited batches, prove optimal batch selection is NP-hard, and provide an optimal solution under a natural condition on entity sizes, achieving superior recall over baselines on six datasets.
We consider an oracle that processes a limited batch of records at a time and clusters those that refer to the same real-world entity. We study how to interrogate such an oracle to resolve entities in a dataset whose size is far larger than a single batch, and where no batch is guaranteed to contain all records of any given entity. We aim at a pay-as-you-go approach, to have full control over the costs (the number of oracle consults), while achieving the highest possible recall at every step. We formally cast this problem as batched entity resolution, prove that selecting optimal batches is NP-hard, and provide an optimal solution under a natural condition on entity sizes. Finally, we evaluate our approach on six datasets and show its superiority over state-of-the-art baselines.