Iterative Bipartite Graph Edit Distance Approximation
Loading...
Authors
Author (Corporation)
Publication date
2014
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Editor (Corporation)
Supervisor
Parent work
Document Analysis Systems
Special issue
DOI of the original publication
Link
Series
Series number
Volume
Issue / Number
Pages / Duration
724-731
Patent number
Publisher / Publishing institution
Place of publication / Event location
Tours
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
One of the major tasks in many applications in the field of document analysis is the computation of dissimilarities between two or more objects from a given problem domain. Hence, employing graphs as representation formalism evokes the need for powerful, fast and flexible graph based dissimilarity models. Graph edit distance is powerful and applicable to any kind of graphs but suffers from its high computational complexity. Recently, however, a novel framework for graph edit distance approximation has been introduced. While the run time of this novel procedure is very convincing, the precision of the approximated graph distances is dissatisfying in some cases. The present paper introduces a generalized version of the existing approximation framework using an iterative bipartite procedure. With empirical investigations on three real world data sets we show that our extension substantially improves the accuracy of the approximations while the run time is increased only linearly with the number of additional iterations.
Keywords
Subject (DDC)
Event
IEEE Computer Society 2014
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
978-1-4799-3244-3
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
License
Citation
Riesen, K., Dornberger, R., & Bunke, H. (2014). Iterative Bipartite Graph Edit Distance Approximation. Document Analysis Systems, 724–731. http://hdl.handle.net/11654/8223