Progressive Entity Resolution for Large Scale Data Integration

This direction is merged into another direction: quadratic comparison complexity. Its last version stays readable and citable here.

Version 1 of 114 papers23 conceptsfrozen 2026-10-04

Traditional Entity Resolution (ER)—the process of identifying different records that refer to the same real-world entity—is fundamentally a bottlenecked process. In a classic workflow, you take two datasets, apply a blocking strategy to prune the search space, compare the remaining pairs, and finally produce a set of matches. This "batch" approach works for thousands of records, but as George Papadakis and colleagues note in The Four Generations of Entity Resolution, it fails when faced with the "4 Vs" of Big Data: Volume, Velocity, Variety, and Veracity.

When dealing with the Linked Open Data cloud or massive web-scale crawls, the computational complexity is often quadratic. Waiting for a full batch process to complete is often impossible due to strict time constraints or limited hardware budgets. Progressive Entity Resolution shifts the goal from "find all matches eventually" to "find as many matches as possible as quickly as possible."

The Pay-As-You-Go Intuition

The core philosophy of progressive ER is the "pay-as-you-go" model. In a standard system, the utility of the output is zero until the very end of the execution. In a progressive system, the utility (measured by the number of matches found) should increase steeply at the beginning of the process.

As described by Steven Euijong Whang and Héctor García-Molina in their work on Generic Entity Resolution, real-time applications require partial or approximate results within a fixed time budget. By prioritizing the most promising comparisons, these systems can deliver high-quality results early, allowing a user or a downstream application to proceed even if the full resolution is only 10% complete.

Prioritization through Scheduling

How does a system know which pairs are "promising" before it actually compares them? This is the central technical challenge of the field. Researchers like Kostas Stefanidis and Vasilis Efthymiou address this in the Minoan ER framework using a progressive scheduling mechanism.

The workflow typically involves three steps:

  1. Blocking: Grouping entities into blocks based on shared attributes (e.g., "all people named Smith").
  2. Weighting: Assigning a score to each pair of entities within those blocks. This score is a "hint" of how likely they are to match, often based on how many blocks they share or the distinctness of their shared tokens.
  3. Scheduling: Sorting the pairs by weight and processing the highest-weighted pairs first.

This iterative approach, as highlighted in JedAI3, allows the system to dynamically re-prioritize potential matches as new evidence is uncovered. If two records are confirmed as a match, the system can immediately look for other records related to those two, creating a "snowball effect" of discovery.

Schema-Agnosticism and Heterogeneity

On the modern web, data rarely follows a clean, unified schema. One dataset might describe a product with brand and model, while another uses manufacturer and id. Traditional ER relies on "schema alignment" to function, but Giovanni Simonini and Sonia Bergamaschi argue in Schema-Agnostic Progressive Entity Resolution that this alignment step is a bottleneck itself.

By being schema-agnostic, progressive ER methods can operate directly on raw attribute values. They leverage the inherent redundancy of data—the fact that the same entity will likely share several tokens across different fields—to build their priority queues. This makes the system robust to the high variety of the Linked Open Data cloud, where entities might share very few common attributes or rely on entirely different data structures.

Maximizing Recall under a Budget

The ultimate metric for these systems is not just precision and recall, but the recall-per-unit-of-computation. In End-to-End Entity Resolution for Big Data, Vassilis Christophides and Themis Palpanas emphasize that in large-scale environments, exhaustive comparison is often impossible.

Budget-aware ER turns the resolution process into an optimization problem: given $X$ amount of CPU time or $Y$ number of comparisons, which set of pairs will yield the maximum number of matches? By treating ER as a progressive, prioritized task rather than a static batch job, researchers have enabled data integration that can scale alongside the explosive growth of the web.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_progressive_entity_resolution_for_large__e4efb6a7,
  title = {Progressive Entity Resolution for Large Scale Data Integration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/progressive-entity-resolution-for-large-scale-data-integration/rdr_e4efb6a7d5554d0e9aed8242b3be1357},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_progressive_entity_resolution_for_large__e4efb6a7_v1,
  title = {Progressive Entity Resolution for Large Scale Data Integration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/progressive-entity-resolution-for-large-scale-data-integration/rdr_e4efb6a7d5554d0e9aed8242b3be1357/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}