Structured Cases, Trees and Efficient Retrieval

A set of efficient algorithms for case retrieval from a case base of trees labeled on both nodes and edges is proposed. They extend the best known algorithm for solving the subtree-isomorphism problem. A branch and bound technique and a general definition of similarity between trees is considered. Both the case structure, i.e. the graph structure, and his semantic part, the labels is taken into account. The comparison with a conventional state-space search algorithm on randomly generated case bases, shows that significant speed up can be obtained