Comparaison d'heuristiques pour le calcul de la distance d'édition entre graphes

Autor: Sébastien Bougleux, David Blumenthal, Luc Brun, Nicolas Boria, Johann Gamper
Přispěvatelé: Free University of Bozen-Bolzano, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), FEDER+Region Normandie., AGAC
Rok vydání: 2019
Předmět:
Graph databases
Theoretical computer science
Linear programming
Computer science
Similarity search
Nearest neighbor search
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
02 engineering and technology
ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.0: Graph algorithms
computer.software_genre
Distance measures
020204 information systems
0202 electrical engineering
electronic engineering
information engineering
Empirical evaluation
Graph edit distance
Local search (optimization)
Local search (constraint satisfaction)
Graph database
business.industry
[INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV]
Graph
Hardware and Architecture
ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization
020201 artificial intelligence & image processing
ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.2: Approximation
Heuristics
business
computer
Assignment problem
Information Systems
Zdroj: The VLDB Journal
The VLDB Journal, Springer, 2020, 29 (1), pp.419-458. ⟨10.1007/s00778-019-00544-1⟩
ISSN: 0949-877X
1066-8888
DOI: 10.1007/s00778-019-00544-1
Popis: International audience; Because of its flexibility, intuitiveness, and ex-pressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP-hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error-correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper , we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.
Databáze: OpenAIRE
Externí odkaz: