Improved labeling scheme for ancestor queries
Stephen Alstrup, Theis Rauhe · 2002
We present a labeling scheme for rooted trees that supports 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 of size n our scheme assigns labels of size bounded by log n + O( p log n) bits to each node. This improves a recent result of Abiteboul, Kaplan and Milo at SODA'01, where a labeling scheme with labels of size 3=2 log n+ O(log log n) was presented. The problem is among other things motivated in connection with ecient representation of information for XML-based search engines for the internet.