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
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.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/407609
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact