Correcting and speeding-up bounds for non-uniform graph edit distance
Blumenthal DB, Gamper J (2017)
Publication Type: Conference contribution
Publication year: 2017
Publisher: IEEE Computer Society
Pages Range: 131-134
Conference Proceedings Title: Proceedings - International Conference on Data Engineering
Event location: San Diego, CA
ISBN: 9781509065431
DOI: 10.1109/ICDE.2017.57
Abstract
The problem of deriving lower and upper bounds for the edit distance between labelled undirected graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform metric edit costs and incorporates information about both node and edge labels. In this paper, we show that this algorithm is incorrect in the sense that, in general, it does not compute a lower bound. We present BRANCH, a corrected version of the algorithm that runs in O(n5) time. We also develop a speed-up BRANCHFAST that runs in O(n4) time and computes a lower bound, which is only slightly less accurate than the one computed by BRANCH. An experimental evaluation shows that BRANCH and BRANCHFAST yield excellent runtime/accuracy-Tradeoffs, as they outperform all existing competitors in terms of runtime or in terms of accuracy.
Authors with CRIS profile
Involved external institutions
Italy (IT)How to cite
APA:
Blumenthal, D.B., & Gamper, J. (2017). Correcting and speeding-up bounds for non-uniform graph edit distance. In Proceedings - International Conference on Data Engineering (pp. 131-134). San Diego, CA, US: IEEE Computer Society.
MLA:
Blumenthal, David B., and Johann Gamper. "Correcting and speeding-up bounds for non-uniform graph edit distance." Proceedings of the 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA IEEE Computer Society, 2017. 131-134.
BibTeX: Download