Reasoning about taxonomies

Abstract

Taxonomically organized data pervade science, business, and everyday life. Unfortunately, taxonomies are often under-specified, or even inconsistent, limiting their utility in contexts such as data integration, information navigation, and autonomous agent communication. This work formalizes taxonomies and articulations (relationships between taxa in taxonomies) as first-order formulas. This formalization concretizes notions such as consistency and inconsistency of taxonomies and articulations between them, enables the derivation of new articulations based on a given set of taxonomies and articulations, and provides a framework for testing assumptions about under-specified taxonomies.

Given the typical intractability of reasoning with taxonomies and articulations, this research also investigates many optimizations: from those that reduce the search space, to those that leverage parallel processing, to those investigating logics more tractable than first-order logic (e.g., monadic first-order logic, propositional logic, description logics, and subsets of the RCC-5 spatial algebra). Finally, in addition to reasoning with taxonomies and articulations, this research investigates how to merge taxonomies given articulations and how to merge data sets that have been annotated to aligned taxonomies. Critical to this research is the development of a framework for testing logics and supporting the development of taxonomies and articulations. This framework, CLEANTAX, has been implemented and has been used to study articulations between several large-scale biological taxonomies.