Improving Approximate Graph Edit Distance by Means of a Greedy Swap Strategy
Kein Vorschaubild vorhanden
Autor:innen
Bunke, Horst
Autor:in (Körperschaft)
Publikationsdatum
2014
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Image and Signal Processing. 6th International Conference, ICISP 2014, Cherbourg, France, June 20 -- July 2, 2014, Proceedings
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Reihennummer
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
314-321
Patentnummer
Verlag / Herausgebende Institution
Verlagsort / Veranstaltungsort
Stockholm
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
The authors of the present paper previously introduced a fast approximation framework for the graph edit distance problem. The basic idea of this approximation is to build a square cost matrix C = (c ij ), where each entry c ij reflects the cost of a node substitution, deletion or insertion plus the matching cost arising from the local edge structure. Based on C an optimal assignment of the nodes and their local structure is established in polynomial time. Yet, this procedure considers the graph structure only in a local way, and thus, an overestimation of the true graph edit distance has to be accepted. The present paper aims at reducing this overestimation by means of an additional greedy search strategy that builds upon the initial assignment. In an experimental evaluation on three real world data sets we empirically verify a substantial gain of distance accuracy while run time is nearly not affected.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
6th International Conference on Image and Signal Processing (ICISP 2014)
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
978-1-4799-5208-3
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Zukunftsfelder FHNW
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Lizenz
Zitation
RIESEN, Kaspar und Horst BUNKE, 2014. Improving Approximate Graph Edit Distance by Means of a Greedy Swap Strategy. In: Image and Signal Processing. 6th International Conference, ICISP 2014, Cherbourg, France, June 20 -- July 2, 2014, Proceedings. Stockholm. 2014. S. 314–321. ISBN 978-1-4799-5208-3. Verfügbar unter: http://hdl.handle.net/11654/8225