You are in:Home/Publications/An improved global lower bound for graph edit similarity search

Dr. Mona Mohamed Arafa Abd Elmonem :: Publications:

Title:
An improved global lower bound for graph edit similarity search
Authors: Karam Gouda,MonaArafa
Year: 2015
Keywords: Graph edit distance, Global lower bound, Similarity search, Graph database.
Journal: Pattern RecognitionLetters
Volume: 58
Issue: Not Available
Pages: Not Available
Publisher: ELSEVIER
Local/International: International
Paper Link: Not Available
Full paper Not Available
Supplementary materials Not Available
Abstract:

Graph similarity search is to retrieve data graphs that are similar to a given query graph.It has become an essential operation in many application areas .In this paper, we investigate the problem of graph similarity search with edit distance constraints.Existing solutions adopt the filter-and-verify strategy to speed up the search,where lower and upper bounds of graph edit distance are employed as pruning and validation rules in this process.The main problem with existing lower bounds is that they show different performance on different datagraphs. An interesting group of lower bounds is the global counting ones.These bounds come almost for free and can be injected with any filtering methodology to work as preliminary filters .In this paper, we present an improvement upon these bounds without adding any computation overhead. We show that the new bound is tighter than the previous global ones except for few cases where they identically evaluate.Via experiments,we show how the new bound, when incorporated into previous lower bounding methods, increases the performance significantly.

Google ScholarAcdemia.eduResearch GateLinkedinFacebookTwitterGoogle PlusYoutubeWordpressInstagramMendeleyZoteroEvernoteORCIDScopus