Informative Labeling Schemes for the Least Common Ancestor Problem.
Saverio Caminiti, Irene Finocchi, Rossella Petreschi · Italian Conference on Theoretical Computer Science · 2009
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 Θ(log 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. Effective representations of large, geographically dispersed communication networks should allow the users to efficiently retrieve information about the network in a distributed and localized way. Labeling schemes provide an answer to this problem by assigning labels to the network nodes in such a way that queries can be computed alone from the labels of the involved nodes, without any extra information source. The primary goal of a labeling scheme is to minimize the maximum label length, while keeping queries fast. Adjacency labeling schemes were first introduced by Breuer and Folkman in [5, 6], and further studied in [11]. The interest in informative labeling schemes, however, was revived only more recently, after Peleg showed the feasibility of the design of efficient labeling schemes capturing distance information [15]. Since then, upper and lower bounds for labeling schemes have been proved on a variety of graph families (including weighted trees, bounded arboricity graphs, intersection-based and cdecomposable graphs) and for a large variety of queries, including distance [2, 8, 10], tree ancestry [1, 3], flow and connectivity [13]. In spite of a large body of theoretical works, to the best of our knowledge only few experimental investigations of the efficiency of informative labeling schemes have been addressed in the literature [8, 12]. In our work [7] we focus on labeling schemes for answering least common ancestor queries in trees. Labeling schemes for least common ancestors are mainly useful in routing messages on tree networks: the ability to compute the identifier of the least common ancestor of any two nodes u and v turns out to be useful when a message has to be sent from u to v in the network, because the message has to go through lca(u, v). Other applications are related to query processing in XML search engines and distributed computing in peer-to-peer networks (see, e.g., [3, 4, 12]). In [16], Peleg has proved that for the class of n-node trees there exists a labeling scheme for least common ancestors using Θ(log n)-bit labels, which is also shown to be asymptotically optimal. We finally remark that, when node levels are known, it is trivial to compute the distance between any two nodes given their lca. Therefore, all the data structures considered in this work can be easily exploited to answer distance queries.