Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching

Blumenthal DB, Bougleux S, Dignoes A, Gamper J (2022)

Publication Language: English

Publication Type: Journal article

Publication year: 2022

Journal

Information Sciences Elsevier

Book Volume: 596

Pages Range: 202-221

DOI: 10.1016/j.ins.2022.03.017

Abstract

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.

Authors with CRIS profile

David Blumenthal Professur für Biomedical Network Science

Involved external institutions

Free University of Bozen - Bolzano IT Italy (IT) Normandy University / Normandie Université FR France (FR)

How to cite

APA:

Blumenthal, D.B., Bougleux, S., Dignoes, A., & Gamper, J. (2022). Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching. Information Sciences, 596, 202-221. https://doi.org/10.1016/j.ins.2022.03.017

MLA:

Blumenthal, David B., et al. "Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching." Information Sciences 596 (2022): 202-221.

BibTeX: Download