Home // DBKDA 2016, The Eighth International Conference on Advances in Databases, Knowledge, and Data Applications // View article

A Distributed Algorithm For Graph Edit Distance

Authors:
Zeina Abu-Aisheh
Romain Raveaux
Jean-Yves Ramel
Patrick Martineau

Keywords: Pattern Recognition; Graph Matching; Graph Edit Distance; Branch-and-Bound; Distribution; Hadoop; MPI

Abstract:
Graph edit distance is an error-tolerant matching paradigm that can be used efficiently to address different tasks in pattern recognition, machine learning, and data mining. The literature is rich of many fast heuristics with unbounded errors but few works are devoted to exact graph edit distance computation. Exact graph edit distance methods suffer from high time and memory consumption. In the meantime, heavy computation tasks have moved from desktop applications to servers in order to spread the computation load on many machines. This paradigm leads to re-design methods in terms of scalability and performance. In this paper, a distributed and optimized branch-and-bound algorithm for exact graph edit distance computation is proposed. The search tree is cleverly pruned thanks to a lower and upper bounds’ strategy. In addition, tree branches are explored in a completely distributed manner to speed up the tree traversal. Meaningful performance evaluation metrics are presented. Experiments were conducted on two publicly available datasets. Results demonstrate that under time constraints the most precise solutions were obtained by our method against five methods from the literature.

Pages: 66 to 71

Copyright: Copyright (c) IARIA, 2016

Publication date: June 26, 2016

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-486-2

Location: Lisbon, Portugal

Dates: from June 26, 2016 to June 30, 2016