Improved labeling scheme for ancestor queries

We present a labeling scheme for rooted trees that support ancestor queries. Given a tree, the scheme assigns to each node a label which is a binary string. Given the labels of any two nodes u and v, it can in constant time be determined whether u is ancestor to v alone from these labels. For trees size of n our scheme assigns labels of size bounded by log n + O (√log n) bits to each node. This improves a recent result of a biteboul, Kaplan and Milo at SODA'01, where a labeling scheme with labels of size 3/2 log n + O(loglog n) was presented. The problem is among other things motivated in  connection with efficient representation of information for XML-based research engines for the internet.