Entity Resolution via Batched Oracle Queries

Entity Resolution (ER) is the process of identifying records that refer to the same real-world entity. Traditionally, ER relies on pairwise comparisons, which scale quadratically with dataset size, making them computationally expensive for large collections. This paper addresses the challenge of 'progressive batched entity resolution,' where an oracle processes a limited batch of records at a time to identify matches. The goal is to maximize the number of discovered matches at each step while maintaining strict control over the number of oracle queries (the budget).

The authors formalize the problem by modeling the oracle as a function that takes a batch of records and returns a partition of those records into clusters. They demonstrate that finding an optimal sequence of batches is NP-hard by reducing it to the bin-packing problem. To manage this complexity, they propose an algorithm called pERbacco. This approach prioritizes batches that are estimated to yield the highest gain in discovered matches, effectively navigating the trade-off between budget consumption and resolution quality. The algorithm is designed to be model-agnostic, meaning it can be applied to various oracle types, including Large Language Models (LLMs) or crowdsourcing platforms.

The study establishes that an optimal sequence of batches does not always exist, highlighting the inherent difficulty of the task. Despite this, the authors provide a practical, approximate solution that guides batch selection to maximize the benefit at each invocation. Experimental evaluations across six datasets demonstrate that their approach consistently outperforms state-of-the-art baselines in terms of recall and efficiency under comparable budget constraints. The authors also provide theoretical upper and lower bounds on the number of queries required, which they show are tight approximations for real-world data.