Correcting and Speeding-Up Bounds for Non-Uniform Graph Edit Distance
MetadataShow full item record
SubjectEdge labels; Lower and upper bounds; Undirected graph; Edit distance; Experimental evaluation
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.
Showing items related by title, author, creator and subject.
Blumenthal DB; Gamper J (Springer, 2017)The graph edit distance is a well-established and widely used distance measure for labelled, undirected graphs. However, since its exact computation is NP -hard, research has mainly focused on devising approximative ...
Augsten, J; Böhlen, MH; Gamper, J (Association for Computing Machinery (ACM), 2010)When integrating data from autonomous sources, exact matches of data items that represent the same real-world object often fail due to a lack of common keys. Yet in many cases structural information is available and can ...
Chondrogiannis T; Gamper J (IEEE, 2016)To process shortest path and distance queries on road networks, various preprocessing techniques have been proposed. State-of-the-art methods for distance queries offer superior query time but do not provide any efficient ...