Skip to main content

Research Repository

Advanced Search

An edit distance between graph correspondences.

Moreno-García, Carlos Francisco; Serratosa, Francesc; Jiang, Xiaoyi

Authors

Francesc Serratosa

Xiaoyi Jiang



Contributors

Pasquale Foggia
Editor

Cheng-Lin Liu
Editor

Mario Vento
Editor

Abstract

The Hamming Distance has been largely used to calculate the dissimilarity of a pair of correspondences (also known as labellings or matchings) between two structures (i.e. sets of points, strings or graphs). Although it has the advantage of being simple in computation, it does not consider the structures that the correspondences relate. In this paper, we propose a new distance between a pair of graph correspondences based on the concept of the edit distance, called Correspondence Edit Distance. This distance takes into consideration not only the mapped elements of the correspondences, but also the attributes on the nodes and edges of the graphs being mapped. In addition to its definition, we also present an efficient procedure for computing the correspondence edit distance in a special case. In the experimental validation, the results delivered using the Correspondence Edit Distance are contrasted against the ones of the Hamming Distance in a case of finding the weighted means between a pair of graph correspondences.

Citation

MORENO-GARCIA, C.F., SERRATOSA, F. and JIANG, X. 2017. An edit distance between graph correspondences. In Foggia, P., Liu, C.-L. and Vento, M (eds.) 2017. Graph-based representations in pattern recognition: proceedings of the 11th Image analysis in patter recognition technical committee 15th (IAPR-TC-15) international workshop (GbRPR 2017), 16-18 May 2017, Anacapri, Italy. Cham: Springer [online], pages 232-241. Available from: https://doi.org/10.1007/978-3-319-58961-9_21

Presentation Conference Type Conference Paper (published)
Conference Name 11th Image analysis in pattern recognition technical committee 15th (IAPR-TC-15) international workshop (GbRPR 2017)
Start Date May 16, 2017
End Date May 18, 2017
Acceptance Date Feb 20, 2017
Online Publication Date May 10, 2017
Publication Date May 10, 2017
Deposit Date Mar 11, 2019
Publicly Available Date Apr 4, 2019
Electronic ISSN 1611-3349
Publisher Springer
Peer Reviewed Peer Reviewed
Pages 232-241
Series Title Lecture notes in computer science
Series Number 10310
Series ISSN 0302-9743
Book Title Graph-based representations in pattern recognition: proceedings of the 11th Image analysis in patter recognition technical committee 15th (IAPR-TC-15) international workshop (GbRPR 2017), 16-18 May 2017, Anacapri, Italy.
Chapter Number Chapter 21
ISBN 9783319589602
DOI https://doi.org/10.1007/978-3-319-58961-9_21
Keywords Graph correspondence; Hamming distance; Edit distance; Weighted mean
Public URL https://rgu-repository.worktribe.com/output/228204
Contract Date Apr 4, 2019

Files




You might also like



Downloadable Citations