We address the problem of labeling the nodes of a tree such that one can determine the identifier of the least common ancestor of any two nodes by looking only at their labels. This problem has application in routing and in distributed computing in peer-to-peer networks. A labeling scheme using Θ(log2 n)-bit labels has been previously presented by Peleg. By engineering this scheme, 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. © 2008 Springer-Verlag Berlin Heidelberg.
Engineering Tree Labeling Schemes: a Case Study on Least Common Ancestor / Caminiti, Saverio; Finocchi, Irene; Petreschi, Rossella. - STAMPA. - LNCS 5193:(2008), pp. 234-245. (Intervento presentato al convegno 16th Annual European Symposium on Algorithms, ESA 2008 tenutosi a Karlsruhe; Germany nel 15/17 settembre 2008) [10.1007/978-3-540-87744-8_20].
Engineering Tree Labeling Schemes: a Case Study on Least Common Ancestor
CAMINITI, SAVERIO;FINOCCHI, Irene;PETRESCHI, Rossella
2008
Abstract
We address the problem of labeling the nodes of a tree such that one can determine the identifier of the least common ancestor of any two nodes by looking only at their labels. This problem has application in routing and in distributed computing in peer-to-peer networks. A labeling scheme using Θ(log2 n)-bit labels has been previously presented by Peleg. By engineering this scheme, 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. © 2008 Springer-Verlag Berlin Heidelberg.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
