LiEP CIS-2000-001: Incremental Encoding of Multiple Inheritance Hierarchies Supporting Lattice Operations.

Temporary registration page before publication by Linköping University Electronic Press, series Computer and Information Science

The following article is intended to be published shortly by Linköping University Electronic Press. The present page gives access to the article, but does not provide the guarantees of persistence.

Incremental Encoding of Multiple Inheritance Hierarchies Supporting Lattice Operations.

Title:	Incremental Encoding of Multiple Inheritance Hierarchies Supporting Lattice Operations.
Authors:	M.F. van Bommel and T.J. Beck
Series:	Linköping Electronic Articles in Computer and Information Science ISSN 1401-9841
Issue:	Vol. 5(2000): nr 001
URL:	http://www.ep.liu.se/ea/cis/2000/001/

Abstract:	Incremental updates to multiple inheritance hierachies are becoming more prevalent with the increasing number of persistent applications supporting complex objects. Efficient computation of lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and subsumption subsequently is becoming more and more important. General techniques for compact encoding of a hierarchy are presented that support the operations, and are flexible enough to allow incremental updates to the hierarchy. One such method is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant time complexity of the lattice operations. The method is based on an inverted version of the encoding of Aït-Kaci et al. to allow incremental update. Simple grouping is used to reduce the code space while keeping the lattice operations efficient. Comparisons are made to an incremental version of the range compression scheme of Agrawal et al., where each class is assigned an interval, and relationships are based on containment in the interval. The result is two incoding methods which have their relative merits.
Keywords:

Abstract:

Incremental updates to multiple inheritance hierachies are becoming more prevalent with the increasing number of persistent applications supporting complex objects. Efficient computation of lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and subsumption subsequently is becoming more and more important. General techniques for compact encoding of a hierarchy are presented that support the operations, and are flexible enough to allow incremental updates to the hierarchy. One such method is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant time complexity of the lattice operations. The method is based on an inverted version of the encoding of Aït-Kaci et al. to allow incremental update. Simple grouping is used to reduce the code space while keeping the lattice operations efficient. Comparisons are made to an incremental version of the range compression scheme of Agrawal et al., where each class is assigned an interval, and relationships are based on containment in the interval. The result is two incoding methods which have their relative merits.

Keywords:

First posting 2000-03-08	In ETAI area "Concept Based Knowledge Representation"
Intended publication 2000-12-05	Postscript part I -- Checksum Postscript part II -- Checksum II
Info from authors
Third-party information

[About LiEP] [About Checksum validation] [About compression formats]

Editor-in-chief: editor@ep.liu.se
Webmaster: webmaster@ep.liu.se