The foundations of taxonomic encoding

Taxonomies (partially ordered sets and lattices) are important in many areas of computing science, particularly object-oriented languages, machine learning, and knowledge representation. Taxonomic encoding strives to enhance the efficiency of taxonomic representation and use, which becomes increasingly important as the size of taxonomies grows. In this paper, we describe a formal structure, called a spanning set, in which taxonomic encoding techniques can be characterized. Any taxonomic encoding scheme implements a mapping from the original ordered set into a structure, such as the lattice of bit-vectors or logical terms, in which operations can be performed efficiently. We analyze the fundamental properties any such mapping must satisfy in order to preserve subsumption, joins, or meets. Spanning sets are an abstract framework within which we portray and compare existing encoding techniques, and provide a context in which new encoding problems can be analyzed, leading to existing, related algorithms or, using other results we develop in this paper, guiding the development of new algorithms. We also explore the limits of minimal-sized encodings, proving a lower bound for simple forms of encoding and showing that, in general, finding minimal-sized encodings is NP-hard. This paper can thus be viewed as both a synthesis of current research in taxonomic encoding and a repository of new results and directions for encoding as viewed from the perspective of spanning sets.