Graph Edit Distance Compacted Search Tree

Chegrane, Ibrahim; Hocine, Imane; Yahiaoui, Saïd; Bendjoudi, Ahcene; Nouali_Taboudjemat, Nadia

Graph Edit Distance Compacted Search Tree

Files

Graph Edit Distance Compacted Search Tree - SISAP-2022.pdf(935.37 KB)

Date

2022

Authors

Nouali_Taboudjemat, Nadia

Publisher

Springer, Cham

Abstract

We propose two methods to compact the used search tree during the graph edit distance (GED) computation. The first maps the node information and encodes the different edit operations by numbers and the needed remaining vertices and edges by BitSets. The second represents the tree succinctly by bit-vectors. The proposed methods require 24 to 250 times less memory than traditional versions without negatively influencing the running time.

Keywords

Graph Edit Distance (GED), Compacted GED search space

URI

https://dl.cerist.dz/handle/CERIST/952

Collections

International Conference Papers

Full item page