SmartInt: using mined attribute dependencies to integrate fragmented web databases

Ravi Gummadi, Anupam Khulbe, Aravind Kalavagattu, Sanil Salvi, Subbarao Kambhampati

Introduction

In the modern "Web of Data," thousands of independent databases—ranging from automotive listings to consumer product reviews—are accessible online. However, this wealth of information is often fragmented. A user seeking a specific vehicle might find pricing on one site, technical specifications on another, and professional reviews on a third. Integrating these disparate sources is difficult because they rarely share common "Primary Keys" (such as a VIN). Standard database join techniques often fail in this environment, as joining on non-unique attributes like "Model" creates "spurious entities," where every instance of a car model is incorrectly matched with every related review.

To address this, researchers at Arizona State University developed SMARTINT, a system designed to automatically reconstruct fragmented entities by mining probabilistic correlations between data attributes.

The SMARTINT Architecture

SMARTINT operates in two distinct phases: an offline learning phase and an online query processing phase. The system moves away from traditional rigid joins, instead using "soft keys" derived from data patterns.

SMARTINT System Architecture

1. Offline: AFD Mining

The system utilizes an algorithm called AFDMiner to discover Approximate Functional Dependencies (AFDs). Unlike strict functional dependencies (e.g., a Zip Code always determines a City), an AFD is probabilistic (e.g., a Car Model usually determines a Cylinder Count). By measuring the information entropy of attributes, the system identifies "specific" rules that are most useful for identifying and linking entities across tables while ignoring overly broad correlations.

2. Online: Query Answering

When a user submits a query involving attributes spread across multiple tables, SMARTINT performs three main steps:

  • Source Selection: It identifies a "base table" containing the majority of the query's attributes.
  • Constraint Translation: If a query constraint (e.g., "4 cylinders") refers to an attribute not present in the base table, SMARTINT uses its mined AFDs to translate that constraint into values the base table understands (e.g., specific car models known to have 4 cylinders).
  • Tuple Expansion: The system constructs a "Tree of Tables" to horizontally grow a single record, fetching missing values from related sources to provide a complete entity view.
Tree of Tables for Query Processing

Evaluation and Results

The system was evaluated using a dataset of 350,000 records from Google Base in the automotive domain. To simulate the real web, a master table was fragmented into five overlapping child tables.

Key findings include:

  • Balanced Performance: SMARTINT achieved a significantly higher F-measure (the balance of precision and recall) compared to "Single Table" or "Direct Join" methods.
  • Precision Maintenance: While Direct Joins often saw precision drop below 20% due to spurious matches, SMARTINT maintained high precision by using AFDs to filter out statistically unlikely combinations.
  • Efficiency: The AFDMiner processed the experimental dataset in approximately 4 seconds, demonstrating its viability for large-scale web data.

Conclusion and Future Work

SMARTINT demonstrates that mining attribute dependencies is a powerful alternative to explicit keys for web data integration. Future work aims to address current limitations, such as the reliance on pre-mapped schemas and the dependency on a single "base table" for entity reconstruction. The researchers are also exploring "variable-width" answers, where the system dynamically determines how much information to fetch based on the confidence levels of the underlying AFDs.

Summary updated

BibTeX
@article{gummadi2012smartint,
  author = {Ravi Gummadi and Anupam Khulbe and Aravind Kalavagattu and Sanil Salvi and Subbarao Kambhampati},
  title = {{SmartInt: using mined attribute dependencies to integrate fragmented web databases}},
  journal = {J. Intell. Inf. Syst.},
  year = {2012},
  doi = {10.1007/s10844-011-0169-0},
}
Figure