We address the problem of labeling the nodes of a tree such that one can determine the identi¯er of the least common ancestor of any two nodes by looking only at their labels. This problem has applica- tion in routing and in distributed computing in peer-to-peer networks. A labeling scheme using £(log2 n)-bit labels has been presented by Peleg. By engineering this scheme and a new one due to the authors, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time.
Algorithmic aspects of bijective tree encoding: a survey / Petreschi, Rossella. - STAMPA. - (2010). (Intervento presentato al convegno Annual meeting of asian Association for Algorithms and Computation tenutosi a Pohang/Corea nel 17/19 Aprile).
Algorithmic aspects of bijective tree encoding: a survey
PETRESCHI, Rossella
2010
Abstract
We address the problem of labeling the nodes of a tree such that one can determine the identi¯er of the least common ancestor of any two nodes by looking only at their labels. This problem has applica- tion in routing and in distributed computing in peer-to-peer networks. A labeling scheme using £(log2 n)-bit labels has been presented by Peleg. By engineering this scheme and a new one due to the authors, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
