Improved labeling scheme for ancestor queries
- Stephen Alstrup,
- Theis Rauhe
Publikation:
Bog / Antologi / Rapport
Rapport
Forskning
Open Access
Resume
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 <i>u</i> and <i>v, </i>it can in constant time be determined whether <i>u</i> is ancestor to <i>v</i> alone from these labels. For trees size of <i>n</i> 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.
Publikation information
Produktionstype
Publikation:
Bog / Antologi / Rapport
Rapport
Forskning
Originalsprog
EngelskPublikationsmilepæle
- Udgivet - 07/2001
Publikationsstatus
Udgivet - 07/2001
Udgivelsessted
CopenhagenUdgave
TR-2001-5Forlag
IT-Universitetet i København, DanmarkBogserie
- Bogserienavn: IT University Technical Report Series
Serienummer: TR-2001-5
ISSN: 1600-6100
ISBN (Elektronisk)
87-7949-009-3Adgang til dokumenter
Forlagets udgivne version, 270.61 KB
