Improved labeling scheme for ancestor queries

Stephen Alstrup, Theis Rauhe

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

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.
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2001-5
Antal sider12
ISBN (Elektronisk)87-7949-009-3
StatusUdgivet - jul. 2001
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2001-5
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Improved labeling scheme for ancestor queries'. Sammen danner de et unikt fingeraftryk.

Citationsformater