Iterative Bipartite Graph Edit Distance Approximation
Vorschaubild nicht verfügbar
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2014
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Document Analysis Systems
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Reihennummer
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
724-731
Patentnummer
Verlag / Herausgebende Institution
Verlagsort / Veranstaltungsort
Tours
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
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.
Schlagwörter
Fachgebiet (DDC)
330 - Wirtschaft
Veranstaltung
IEEE Computer Society 2014
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
978-1-4799-3244-3
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Lizenz
Zitation
RIESEN, Kaspar, Rolf DORNBERGER und Horst BUNKE, 2014. Iterative Bipartite Graph Edit Distance Approximation. In: Document Analysis Systems. Tours. 2014. S. 724–731. ISBN 978-1-4799-3244-3. Verfügbar unter: http://hdl.handle.net/11654/8223