On the Stable Marriage of MaximumWeight Royal Couples

Anan Marie, Avigdor Gal

In this paper we provide a comparison, both analytic and empirical, of two algorithms that were used in the literature for ensuring a 1:1 cardinality constraint in schema matching. We compare an application of a solution to the maximum weighted bipartite graph to schema matching to that of solving a stable marriage problem. Using real-world testbed we show that in practice, both algorithms yield similar results. We then analyze the roots of this similarity, by offering a variation of the stable marriage algorithm for schema matching (royal couples) and show the relationships between the royal couples stable marriage problem and the maximum weights bipartite graph problem. Finally, we propose a new heuristic for schema matching, based on the royal couples observation and show its performance with respect to the two algorithms.

Subjects: 1.4 Design; Please choose a second document classification

Submitted: May 11, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.