Tolerant similarity search in graph database
Meera M. Dhabu, Parag S Deshpande, Himanshu Jakhmola · 2017 Computing Conference · 2017
In today's world, we come across number of problems which requires modeling the elements of these problems in the form of graph and then get the result by manipulating graphs. One of the operations on such graphs is finding graphs from the graph database that are similar to a particular query graph. There are number of problem statements where very large numbers of graphs need to be manipulated. In addition to this, these graphs are big in size, therefore efficient searching of similar graphs for a given query graph becomes a difficult task. In the literature, lots of work has been reported on graph edit distance (GED) as it is not restrictive to particular type of graph. Graph edit distance is error tolerant i.e. by adding tolerance limit in GED, similar graphs can be found even in the presence of noise. Most of the work is done for graph with no edge labels. There are graphs which exhibit some relationship between the vertices i.e. a labeled edge. In this paper, we propose an algorithm for computing edit distance's lower bounds for simple graph with labeled edges represented as star substructure. The proposed algorithm uses edge label & vertex label indexing and modifies inverted index based on substructures like star with labeled edges and edge substructure as substructure. A two-level inverted index is constructed and pre-processed to maintain a global similarity order for subunits and graphs in case of star.