Name
Abstract | ||
|---|---|---|
We present a labeling scheme for rooted trees that sup- ports ancestor queries. Given a tree, the scheme ~ssigns 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(~) 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/21ogn + O(loglogn) was presented. The problem is among other things motivated in connection with efficient representation of information for XML-based search en- gines for the internet. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.5555/545381.545504 | symposium on discrete algorithms |
Keywords | Field | DocType |
log log n,rooted tree,xml-based search engine,constant time,ancestor query,recent result,nodes u,log n,binary string,efficient representation,algorithms,knots,implementation,proteins,computational topology,winding number,search engine,differential geometry | Discrete mathematics,Binary logarithm,Combinatorics,Search engine,XML,Binary strings,Ancestor,Knot (unit),Mathematics,Computational topology,Bounded function | Conference |
ISBN | Citations | PageRank |
0-89871-513-X | 50 | 2.57 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephen Alstrup | 1 | 657 | 42.60 |
| Theis Rauhe | 2 | 661 | 35.11 |