Abstract
We present an implementation and evaluation based on simulation of dynamic labeling schemes for tree networks. Two algorithms are studied: a general scheme that converts static labeling schemes to dynamic, and a specialized dynamic distance labeling scheme. Our study shows that theoretical bounds only partially portray the performance of such dynamic labeling schemes in practice. First, we observe order-of-magnitude differences between the gains in label size when compared to the number of messages passed. Second, we demonstrate a significant bottleneck in the tree network, suggesting that the current practice of counting total messages passed in the whole network is insufficient to properly characterize performance of these distributed algorithms. Finally, our experiments provide intuition on the worst case scenarios for the stated algorithms, in particular path tree networks and fully dynamic schemes permitting both node additions and deletions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Afek, Y., Awerbuch, B., Plotkin, S., Saks, M.: Local management of a global resource in a communication network. JACM 43(1), 1–19 (1996)
Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. SIAM J. Discret. Math. 19(2), 448–462 (2005)
Alstrup, S., Halvorsen, E.B., Larsen, K.G.: Near-optimal labeling schemes for nearest common ancestors. arXiv preprint arXiv:1312.4413 (2013)
Alstrup, S., Rauhe, T.: Small induced-universal graphs and compact implicit graph representations. In: FOCS 2002, pp. 53–62 (2002)
Breuer, M.A., Folkman, J.: An unexpected result in coding the vertices of a graph. J. Mathematical Analysis and Applications 20, 583–600 (1967)
Caminiti, S., Finocchi, I., Petreschi, R.: Engineering tree labeling schemes: A case study on least common ancestors. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 234–245. Springer, Heidelberg (2008)
Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comp. 32(5), 1338–1355 (2003)
Cohen, E., Kaplan, H., Milo, T.: Labeling dynamic xml trees. SIAM Journal on Computing 39(5), 2048–2074 (2010)
Fischer, J.: Short labels for lowest common ancestors in trees. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 752–763. Springer, Heidelberg (2009)
Fraigniaud, P., Korman, A.: An optimal ancestry scheme and small universal posets. In: STOC 2010, pp. 611–620 (2010)
Jain, R.: The art of computer systems performance analysis, vol. 182. John Wiley & Sons, Chichester (1991)
Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 334–343 (1992)
Kaplan, H., Milo, T., Shabo, R.: A comparison of labeling schemes for ancestor queries. In: SODA 2002, pp. 954–963 (2002)
Korman, A.: General compact labeling schemes for dynamic trees. Distributed Computing 20(3), 179–193 (2007)
Korman, A.: Improved compact routing schemes for dynamic trees. In: PODC 2008, pp. 185–194. ACM (2008)
Korman, A.: Compact routing schemes for dynamic trees in the fixed port model. In: Distributed Computing and Networking, pp. 218–229 (2009)
Korman, A., Peleg, D.: Labeling schemes for weighted dynamic trees. Information and Computation 205(12), 1721–1740 (2007)
Korman, A., Peleg, D., Rodeh, Y.: Labeling schemes for dynamic tree networks. Theory of Computing Systems 37(1), 49–75 (2004)
Peleg, D.: Proximity-preserving labeling schemes. Journal of Graph Theory 33(3), 167–176 (2000)
Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA 2001, pp. 1–10 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Rotbart, N., Vaz Salles, M., Zotos, I. (2014). An Evaluation of Dynamic Labeling Schemes for Tree Networks. In: Gudmundsson, J., Katajainen, J. (eds) Experimental Algorithms. SEA 2014. Lecture Notes in Computer Science, vol 8504. Springer, Cham. https://doi.org/10.1007/978-3-319-07959-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-07959-2_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07958-5
Online ISBN: 978-3-319-07959-2
eBook Packages: Computer ScienceComputer Science (R0)