[Gd-hackers] new type hierarchy encoding

[Kim Barrett]

Just received my PoPL 2008 proceedings yesterday; this might be of 
interest to some of you.

"Extensible Encoding of Type Hierarchies", Alavi, Gilbert, & 
Guerraoui, PoPL 2008.

Abstract:
The subtyping test consists of checking whether a type t is a 
descendant of a type r (Agrawal et al. 1989). We study how to perform 
such a test efficiently, assuming a dynamic hierarchy when new types 
are inserted at run-time. The goal is to achieve time and space 
efficiency, even as new types are inserted. We propose an extensible 
scheme, named ESE, that ensures (1) efficient insertion of new types, 
(2) efficient subtyping tests, and (3) small space usage. On the one 
hand ESE provides comparable test times to the most efficient 
existing static schemes (e.g.,Zibin et al. (2001)). On the other 
hand, ESE has comparable insertion times to the most efficient 
existing dynamic scheme (Baehni et al. 2007), while ESE outperforms 
it by a factor of 2-3 times in terms of space usage.