Structural Classification - A Preliminary Report

TitleStructural Classification - A Preliminary Report
Publication TypeTechnical Report
Year of Publication1996
AuthorsKoehler, J., Stoffel K., & Hendler J. A.
Other Numbers1033
Keywordsclassification, concept languages, description logics, optimization techniques

A new type of classification algorithm is introduced that works on the folded representation of concepts. The algorithm comprises two phases: a preprocessing phase working on the normal-form representation of concepts to test for unsatisfiability and tautology, and a structural classifier that generates predecessors and successors of concepts by exploiting new optimization techniques not available to standard classifiers.Working on the folded terminology instead of its expanded and normalized representation allows to significantly reduce the number of subsumptions tests that are necessary to correctly classify a concept. We describe the algorithm, and prove it sound and complete for two different languages. It can be extended to more expressive languages when combined with a new method for reasoning about number restrictions over role hierarchies based on diophantine equations.The algorithm is very fast and very well parallelizable taking less than 4 hours for the classification of a terminology of 100,000 concepts on an SP2.

Bibliographic Notes

ICSI Technical Report TR-96-023

Abbreviated Authors

J. Koehler, K. Stoffel, and J. A. Hendler

ICSI Publication Type

Technical Report