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(n
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sup>
) time. We also develop a speed-up BRANCHFAST that runs in O(n
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup>
) 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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/ICDE.2017.57 | 2017 IEEE 33rd International Conference on Data Engineering (ICDE) |
Keywords | Field | DocType |
nonuniform graph edit distance,lower bound,upper bound,labelled undirected graphs,nonuniform metric edit costs,node label,edge label,O(n5) time algorithm,BRANCHFAST algorithm,O(n4) time algorithm | Edit distance,Discrete mathematics,Data mining,Graph,Upper and lower bounds,Computer science,Bipartite graph,Algorithm,Graph edit distance | Conference |
ISSN | ISBN | Citations |
1084-4627 | 978-1-5090-6544-8 | 2 |
PageRank | References | Authors |
0.38 | 7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Blumenthal | 1 | 24 | 6.26 |
Johann Gamper | 2 | 465 | 54.06 |