首页|Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching
Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Matchings between objects from two datasets, domains, or ontologies have to be computed in various application scenarios. One often used meta-approach -which we call bipartite data matching-is to leverage domain knowledge for defining costs between the objects that should be matched, and to then use the classical Hungarian algorithm to compute a minimum cost bipartite matching. In this paper, we introduce and study the problem of enumerating K dissimilar minimum cost bipartite matchings. We formalize this problem, prove that it is NP-hard, and present heuristics based on greedy dynamic programming. The presented enumeration techniques are not only interesting in themselves, but also mitigate an often overlooked shortcoming of bipartite data matching, namely, that it is sensitive w. r. t. the storage order of the input data. Extensive experiments show that our enumeration heuristics clearly outperform existing algorithms in terms of dissimilarity of the obtained matchings, that they are effective at rendering bipartite data matching approaches more robust w. r. t. random storage order, and that they significantly improve the upper bounds of state-of-the art algorithms for graph edit distance computation that are based on bipartite data matching.(c) 2022 Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Enumeration with dissimilarityData matchingBipartite matchingDynamic programmingGraph edit distanceGRAPH EDIT DISTANCECOMPUTATIONASSIGNMENTALGORITHMS
Dignos, Anton、Gamper, Johann、Blumenthal, David B.、Bougleux, Sebastien
NSTL
Elsevier
