Title: Decision trees for filtering large databases of graphs

Authors: Christophe Irniger, Horst Bunke

Addresses: Institute of Computer Science and Applied Mathematics, University of Bern, Neubruckstrasse 10, CH-3012 Bern, Switzerland. ' Institute of Computer Science and Applied Mathematics, University of Bern, Neubruckstrasse 10, CH-3012 Bern, Switzerland

Abstract: Graphs are a powerful representation formalism for structural data. They are, however, very expensive from the computational point of view. In pattern recognition and intelligent information processing it is often necessary to match an unknown sample against a database of candidate patterns. In this process the size of the database is introduced as an additional factor into the overall complexity of the matching process. To reduce the influence of that factor, an approach based on machine learning techniques is proposed in this paper. Firstly, graphs are represented using feature vectors. Then, based on these vectors, a decision tree is built to index the database. At runtime the decision tree allows one to eliminate a number of graphs from the database to reduce possible matching candidates.

Keywords: structural pattern recognition; graph matching; graph isomorphism; subgraph isomorphism; database filtering; decision trees; machine learning; graph databases; intelligent information processing; feature vectors; graphs.

DOI: 10.1504/IJISTA.2007.014258

International Journal of Intelligent Systems Technologies and Applications, 2007 Vol.3 No.3/4, pp.166 - 187

Published online: 28 Jun 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article