Abstract :
Objects like road networks, CAD/CAM components, electrical or electronic circuits, molecules, can be represented as graphs, in many modern applications. The authors propose an efficient and effective graph manipulation technique that can be used in graph-based similarity search. Given a query graph Gq (V,E), they would like to determine fast which are the graphs in the database that are similar to Gq (V,E), with respect to a similarity measure. First, they study the similarity measure between two graphs. Then, they discuss graph representation techniques by means of multidimensional vectors. It is shown that no false dismissals are introduced by using the vector representation. Finally they illustrate some representative queries that can be handled by their approach, and present experimental results, based on the proposed graph similarity algorithm. The results show that considerable savings are obtained with respect to computational effort and I/O operations, in comparison to conventional searching techniques
Keywords :
computer graphics; image retrieval; pattern recognition; query formulation; query processing; computer graphics; graph histogram; graph manipulation; graph representation; graph similarity algorithm; information retrieval; multidimensional vector; pattern recognition; query handling; query processing; structure-based similarity search; technique; vector representation; Application software; Birth disorders; CADCAM; Computer aided manufacturing; Data engineering; Databases; Electrical capacitance tomography; Electronic circuits; Histograms; Informatics;
