Melnik, Sergey and Garcia-Molina, Hector and Rahm, Erhard (2002) Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching. In: 18th International Conference on Data Engineering (ICDE 2002), February 26 - March 1, 2002, San Jose, CA.
This is the latest version of this item.
Matching elements of two data schemas or two data instances plays a key role in data warehousing, e-business, or even biochemical applications. In this paper we present a matching algorithm based on a fixpoint computation that is usable across different scenarios. The algorithm takes two graphs (schemas, catalogs, or other data structures) as input, and produces as output a mapping between corresponding nodes of the graphs. Depending on the matching goal, a subset of the mapping is chosen using filters. After our algorithm runs, we expect a human to check and if necessary adjust the results. As a matter of fact, we evaluate the `accuracy' of the algorithm by counting the number of needed adjustments. We conducted a user study, in which our accuracy metric was used to estimate the labor savings that the users could obtain by utilizing our algorithm to obtain an initial matching. Finally, we illustrate how our matching algorithm is deployed as one of several high-level operators in an implemented testbed for managing information models and mappings.
|Item Type:||Conference or Workshop Item (Paper)|
|Uncontrolled Keywords:||Matching, Model Management, Heterogeneous Databases, Semistructured Data|
|Subjects:||Computer Science > Data Integration and Mediation|
Computer Science > Semistructured Data
|Related URLs:||Project Homepage, Project Homepage||http://www-diglib.stanford.edu/diglib/pub/, http://infolab.stanford.edu/OntoAgents/|
|Deposited By:||Import Account|
|Deposited On:||11 Nov 2001 16:00|
|Last Modified:||25 Dec 2008 09:53|
Available Versions of this Item
- Similarity Flooding: A Versatile Graph Matching Algorithm (Extended Technical Report). (deposited 25 Jun 2001 17:00)
- Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching. (deposited 11 Nov 2001 16:00) [Currently Displayed]
Repository Staff Only: item control page