Gå til søgefeltetSpring over til navigationSpring til hovedindhold

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 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.

Publikation information

Produktionstype

Publikation:
Bog / Antologi / Rapport
Rapport
Forskning

Originalsprog

Engelsk

Publikationsmilepæle

  • Udgivet - 07/2001

Publikationsstatus

Udgivet - 07/2001

Udgivelsessted

Copenhagen

Udgave

TR-2001-5

Forlag

IT-Universitetet i København, Danmark

Bogserie

  • Bogserienavn: IT University Technical Report Series
    Serienummer: TR-2001-5
    ISSN: 1600-6100

ISBN (Elektronisk)

87-7949-009-3

Adgang til dokumenter

Forlagets udgivne version, 270.61 KB