ON EFFICIENT ENTREEINGS

A data encoding is a formal model of how a logical data structure is m apped into or represented in a physical storage structure. Both struct ures are complete trees in this paper, and we encode the logical or gu est tree in the leaves of the physical or host tree giving a restricte d class of encodings called entreeings. The cost of an entreeing is th e total amount that the edges of the guest tree are stretched or dilat ed when they are replaced by shortest paths in the host tree. We are p articularly interested in the asymptotic average cost of families of s imilar entreeings. Our investigation is a continuation of the study in itiated by Rosenberg et al. In particular, the paper contains the foll owing results. 1. We refute a conjecture of Rosenberg et al. that a pa rticular family of entreeings of binary guests into binary hosts is op timal. 2. We provide an efficient family of entreeings for k-ary guest s into k-ary hosts, for k greater-than-or-equal-to 2. 3. We provide an efficient family of entreeings of k-ary guests into binary hosts, for k greater-than-or-equal-to 3. 4. We provide a new simple lower-bound technique that can be applied to the entreeings in part 2 to prove tha t they are very close to optimal. Moreover, it can be adapted for the entreeings of part 3, in which case we are able to show near optimalit y when k is sufficiently large.