Premium
Matching shape graphs
Author(s) -
Demirci M. Fatih,
van Leuken Reinier,
Veltkamp Remco
Publication year - 2007
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200700444
Subject(s) - search engine indexing , computer science , graph database , graph , xml , theoretical computer science , matching (statistics) , combinatorics , information retrieval , mathematics , world wide web , statistics
Graphs are important structures to model complex relationships such as chemical compounds, proteins, geometric or hierarchical parts, and XML documents. Given a query graph, indexing has become a necessity to retrieve similar graphs quickly from large databases. We propose a novel technique for indexing databases, whose entries can be represented as graph structures. Our method starts by representing the topological structure of a graph as well as that of its subgraphs as vectors in which the components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)