@book{42af758a942a42edab703efe0d42fca3,
title = "Improved labeling scheme for ancestor queries",
abstract = "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.",
keywords = "labeling scheme, rooted trees, ancestor queries, binary string labels, efficient information representation",
author = "Stephen Alstrup and Theis Rauhe",
year = "2001",
month = jul,
language = "English",
series = "IT University Technical Report Series",
number = "TR-2001-5",
publisher = "IT-Universitetet i K{\o}benhavn",
address = "Denmark",
edition = "TR-2001-5",
}