Integrating Information About Entities Progressively

Ben McCamish, Christopher Buss, Arash Termehchy, David MaierarXiv 2019 · arXiv

TL;DR

ProgMap is a progressive entity-matching framework that eliminates the need for costly, upfront manual data integration or schema mapping. By framing entity resolution as a dynamic reinforcement learning problem, data sources learn to collaborate and accurately match entities on-demand using minimal, iterative user feedback.

What Problem Does This Paper Address?

Integrating data across disparate sources is a classic database headache. Traditionally, experts must manually craft complex mapping rules or train supervised models beforehand to ensure that "Soda" in Database A maps correctly to "Pop" in Database B.

This upfront approach fails to scale with the explosion of online databases. Furthermore, database owners are often reluctant to share their entire schema or content due to privacy concerns, making global mappings impossible. Finally, upfront integration wastes massive amounts of effort mapping data that users might never actually query. The authors tackle this by proposing a system that integrates entities on-demand and progressively, learning only what is necessary based on active user queries.

Methods

ProgMap introduces a decentralized, progressive learning framework where a local database and external databases learn to communicate without an initial global schema.

  1. Vague Querying: When a user queries a local database, the system identifies the local entity of interest (the "intent"). Because it doesn't know the external schema, the local source formulates a intentionally vague keyword or full-text query (e.g., using MySQL's MATCH operator) to probe external databases.
  2. Stochastic Strategies: Both the local source (querying strategy) and external sources (answering strategy) maintain probabilistic models. The local strategy maps intents to specific keyword queries, while the external strategy maps incoming keyword queries to its internal entities.
  3. Dynamic Reinforcement Learning: Because both sides alter their strategies simultaneously, the environment is a "moving target." Standard multi-armed bandit algorithms (like UCB-1) assume a static environment and fail here. Instead, the authors adapt the Roth and Erev reinforcement learning algorithm, which is designed for dynamic, game-theoretic environments, updating selection probabilities based on user feedback (measured via Mean Reciprocal Rank, or MRR).
  4. Sample Efficiency Optimizations: To avoid exhausting the user with feedback requests, ProgMap employs two clever tricks:
  5. Autonomous Communication: The system caches user feedback and runs offline simulation rounds between the databases to bubble relevant results to the top.
  6. Query Expansion: Successfully matched external records are broken down into new keywords and fed back into the local querying strategy to enrich its vocabulary.

Datasets

The framework was evaluated using two real-world entity resolution benchmarks:

  • Product Datasets: Subsets of Amazon and Google product databases containing roughly 5,000 tuples each.
  • Movie Datasets: Two distinct movie databases containing approximately 100,000 tuples each.

Key Insights and Ideas

  • Embracing Vagueness: Instead of trying to generate perfect SQL queries across unknown schemas, ProgMap leverages the inherent flexibility of keyword search engines to bootstrap the integration process.
  • The Co-Adaptation Problem: Entity resolution with two learning agents means the success of a local query depends entirely on how the external database interprets it. This co-adaptation necessitates algorithms like Roth-Erev that can handle shifting reward distributions.
  • Leveraging Caching for Offline Learning: You don't need to bug the user for every single optimization step. By caching a single piece of user validation, the databases can "talk to each other" autonomously behind the scenes to refine their alignment.

Key Results

ProgMap (denoted as "RE With Auto and Expansion" in the evaluation) significantly outperformed baseline methods (standard BM25 ranking) and static RL approaches (UCB-1).

  • Product Datasets: ProgMap steadily climbed to a Mean Reciprocal Rank (MRR) of over 0.5 within 500 interactions, while UCB-1 variants quickly degraded to near 0 due to their inability to handle the dynamic environment.
Figure 1: MRR Over Product Datasets
  • Movie Datasets: Interestingly, a non-learning external source ("RE No Ext. Learning") initially performed better because it provided a stable, unchanging BM25 baseline for the local source to learn against. However, ProgMap's full learning suite ("RE With Auto and Expansion") quickly caught up and matched its performance within 400 interactions, eventually reaching an MRR of 0.75 after 2,000 interactions.
Figure 2: MRR Over Movie Datasets

Limitations and Future Work

  • Schema Simplification: The framework currently assumes data is structured in a single relational table per source. Extending this to complex, multi-table relational schemas or graph databases remains an open challenge.
  • Cold-Start Friction: As seen in the movie dataset evaluation, the initial interactions can yield low-quality results before the system learns, which might frustrate users early in the lifecycle.
  • Multi-Source Scaling: The paper primarily focuses on a pairwise interaction model (one local source, one external source); scaling this seamlessly to dozens of simultaneous external data sources simultaneously requires further exploration.

Summary updated

Abstract

Users often have to integrate information about entities from multiple data sources. This task is challenging as each data source may represent information about the same entity in a distinct form, e.g., each data source may use a different name for the same person. Currently, data from different representations are translated into a unified one via lengthy and costly expert attention and tuning. Such methods cannot scale to the rapidly increasing number and variety of available data sources. We demonstrate ProgMap, a entity-matching framework in which data sources learn to collaborate and integrate information about entities on-demand and with minimal expert intervention. The data sources leverage user feedback to improve the accuracy of their collaboration and results. ProgMap also has techniques to reduce the amount of required user feedback to achieve effective matchings.
BibTeX
@misc{mccamish2019integrating,
  author = {Ben McCamish and Christopher Buss and Arash Termehchy and David Maier},
  title = {{Integrating Information About Entities Progressively}},
  year = {2019},
  eprint = {1910.10263},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.10263},
}
Figure