Search papers, labs, and topics across Lattice.
This paper addresses the challenge of entity resolution using an oracle that processes limited batches of records, focusing on how to optimally query the oracle to cluster records referring to the same entity. The authors introduce a pay-as-you-go strategy that balances cost control with maximizing recall, proving the NP-hardness of the optimal batch selection problem and providing a solution under specific conditions. Evaluations across six datasets demonstrate that their method outperforms existing state-of-the-art approaches in entity resolution tasks.
Optimal batch selection for entity resolution is NP-hard, yet this study reveals a practical solution that significantly enhances recall while controlling costs.
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.
