An ancestry labeling scheme assigns labels (bit strings) to the nodes of rooted trees such that ancestry queries between any two nodes in a tree can be answered merely by looking at their corresponding labels. The quality of an ancestry labeling scheme is measured by its label size, that is the maximal number of bits in a label of a tree node. In addition to its theoretical appeal, the design of efficient ancestry labeling schemes is motivated by applications in web search engines. For this purpose, even small improvements in the label size are important. In fact, the literature about this topic is interested in the exact label size rather than just its order of magnitude. As a result, following the proposal of a simple interval-based ancestry scheme with label size @math bits (, STOC '88), a considerable amount of work was devoted to improve the bound on the size of a label. The current state of the art upper bound is @math bits (, SODA '02) which is still far from the known @math bits lower bound (, SODA '03). In this paper we close the gap between the known lower and upper bounds, by constructing an ancestry labeling scheme with label size @math bits. In addition to the optimal label size, our scheme assigns the labels in linear time and can support any ancestry query in constant time.
As explained in @cite_0 , the names of nodes in traditional graph representations reveal no information about the graph structure and hence memory is wasted. Moreover, typical representations are usually global in nature, i.e., in order to derive useful information, one must access a global data structure representing the entire network, even if the sought information is local, pertaining to only a few nodes. In contrast, the notion of informative labeling schemes , introduced in @cite_0 , involves an informative method for assigning labels to nodes. Specifically, the assignment is made in a way that allows one to infer information regarding any two nodes directly from their labels, without using any additional information sources. Hence in essence, this method bases the entire representation on the set of labels alone. This method was illustrated in @cite_0 , by giving two elegant and simple labeling schemes for @math -node trees: one supporting adjacency queries and the other supporting ancestry queries. Both schemes incur @math label size.
@cite_0
2006334273 1560716145 1990376056 2952655484
How to represent a graph in memory is a fundamental data structuring question. In the usual representations of an n -node graph, the names of the nodes (i.e. integers from 1 to n ) betray nothing about the graph itself. Indeed, the names (or labels) on the n nodes are just log n bit place holders to allow data on the edges to code for the structure of the graph. In our scenario, there is no such waste. By assigning O (log n ) bit labels to the nodes, we completely code for the structure of the graph, so that given the labels of two nodes we can test if they are adjacent in time linear in the size of the labels. Furthermore, given an arbitrary original labeling of the nodes, we can find structure coding labels (as above) that are no more than a small constant factor larger than the original labels. These notions are intimately related to vertex induced universal graphs of polynomial size. For example, we can label planar graphs with structure coding labels of size n . This implies the existence of a graph with n 4 nodes that contains all n -node planar graphs as vertex induced subgraphs (It was not previously known that this class had polynomial sized universal graphs). The theorems on finite graphs extend to a theorem about the constrained labeling of infinite graphs. We present a labeling scheme for rooted trees which allows to compute, from the label of v alone, unique identifiers for the ancestors of v that are at distance at most d from v. For any constant d our labeling scheme produce labels of length log n+O(√log n), and for d ∈ O(√log n) the labels are still of length O(log n). In particular, given the labels of two nodes u and v we can determine from the labels alone whether u is the parent of v or vice versa, whether u and v are siblings, and whether u and v are at distance at most d from each other. The need for such labeling scheme arises in several application areas, including in particular communication networks and search engines for large collections ofWeb XML files. In the latter application XML files are viewed as trees, and typical queries ask for XML files containing a particular set of nodes with specific ancestor, parent, or sibling relationships among them. We consider the following problem. Give a rooted tree T, label the nodes of T in the most compact way such that given the labels of two nodes one can determine in constant time, by looking only at the labels, if one node is an ancestor of the other. The best known labeling scheme is rather straightforward and uses labels of size at most 2 log n, where n is the number of vertices In the tree. Our main result in this paper is a labeling scheme with maximum label size close to 3 2 log n. Our motivation for studying this problem is enhancing the performance of Web search engines. In the context of this application each indexed document is a tree and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label size are important. There are no lower bounds known for this problem except for an obvious lower bound of log n that follows from the fact that different vertices must have different labels. The question whether one can find even shorter labels remains an intriguing open question. We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label lenght and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different trade-offs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades. More specifically, we present a distance labeling scheme with label size (log 3) 2 + o(n) (logarithms are in base 2) and O(1) decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size (log 3)n and O(n log n) decoding time, and (SODA'01), which uses labels of size 11n + o(n) and O(loglog n) decoding time. In addition, our algorithm is simpler than the previous ones. In the case of integral edge weights of size at most W, we present almost matching upper and lower bounds for label sizes. For r-additive approximation schemes, where distances can be off by an additive constant r, we give both upper and lower bounds. In particular, we present an upper bound for 1-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency scheme: n 2. We also give results for bipartite graphs and for exact and 1-additive distance oracles.