Graph reachability is a fundamental problem in many applications, such as reasoning in lightweight formalisms, geographic navigation, XML/RDF/OWL query processing, etc. Many real world scenarios involve huge graphs and require fast algorithms to test for reachability between nodes. The problem becomes even more challenging when the graph is rapidly changing and received as a real-time stream of nodes and arcs. In this paper we will review current graph reachability algorithms and focus on how they can be adapted to the streaming setting. We will also outline a new algorithm for answering reachability queries on huge, rapidly changing graphs.
The graph reachability problem is defined as: given two vertices u and v on a
directed graph find out whether there is a path from u to v. The problem has been
explored in depth in several research fields [
Some typical applications involve geographic navigation, traffic control, click streams, etc. The problem is also a fundamental step in many reasoning tasks based on various logical formalisms such as OWL, WSML, DL. The reason for this is that for a directed graph its reachability relation is also its transitive closure, which in turn can be considered a classical example of monotonic reasoning and used as a building block to facilitate more complex reasoning.
As a more specific use case we can consider Urban Computing [
The outlined recent applications of the problem where large, rapidly changing graphs are involved rekindled the interest in the graph reachability problem. The solutions proposed for the problem clearly show the trade-off between time and space requirements: 1)Additional information about the graph (i.e the transitive closure) needs to be stored and maintained for fast query answering, 2)The query time becomes linearly proportional to the size of the graph if no additional information is kept. In this paper, we will review various graph reachability algorithms, comment on their applicability to the streaming setting, and outline a new algorithm designed for rapidly changing graphs.
The outline of the paper is as follows: in Section 2 we will review the current graph reachability algorithms and focus on how they can be adapted to the streaming setting. In Section 3 we will outline a new algorithm for streaming graph reachability queries. Finally we will present our conclusions and outline the future work in Section 4. 2
Given a graph G = (V, E) where V is the set of vertices, E is the set of edges and |V | = n, |E| = m, there are two naive approaches for answering reachability queries. One is to use the shortest path algorithm with O(m) query time. Another naive approach to this problem is to pre-compute reachability between every pair of vertices in a graph so that reachability queries over this graph can be answered in constant time and require O(n2) space. As can be seen from their time and space requirements, these approaches are impractical for large graphs, even if they are static. If we consider the streaming setting we also need to consider real-time updates to the graph and the ability to continuously evaluate a reachability query. The query time of the first approach and update time of the second approach clearly show the infeasibility of their use for streaming graphs.
Efficient solutions to this problem on large sparse graphs involve reachability
labeling methods. Several approaches have been proposed to encode graph
reachability information using labeling schemes [
The last method is called dual labeling by Wang et al. [
Shortest Path Transitive Closure
Interval 2-Hop HOPI Dual-I
Dual-II Fluid Path
O(m) O(1)
O(n) O(m1/2) O(m1/2)
O(1) O(logt)
O(t)
0 O(n3) O(n) O(n4)
O(n3) O(n + m + t3) O(n + m + t3) O(n + m + t)
0 O(n2)
O(n2) O(nm1/2) O(nm1/2) O(n + t2) O(n + t2)
O(n + t) contain the complete information needed to answer a reachability query over the original graph. The dual labeling method integrates interval-based labeling, which encodes reachability in the spanning tree and non-tree labeling to complete the reachability information of the graph. This method consists of two schemes Dual-I and Dual-II. The Dual-I scheme has constant query time, whereas it is O(logt) for Dual-II. Both schemes have O(n + t2) space complexity, however Dual-II uses less space in practice. These algorithms are more promising for the streaming graph reachability problem, especially Dual-I with its constant query time. However the dynamically changing nature of the graph will impose further requirements on the efficiency of storing this index structure composed of two components. For each update we need to regenerate the index which is very costly for huge streaming graphs. Figure 1 summarizes the complexity results for the methods mentioned in this section and in the next section. 3
In this section, we outline an algorithm for answering reachability queries on rapidly changing graphs which we call ‘fluid path’. Our algorithm uses intervalbased labeling and is comparable to dual labeling in terms of the trade off between time and space complexities which depend on the size of the set of non tree edges in the graph.
The input is a directed graph G = (V, E) where |V | = n, |E| = m. We assume
that G is acyclic and if not it can be transformed to an equivalent acyclic one
in terms of reachability information in O(n + m) time [
In the streaming setting, we assume that the graph information is received as this tree transformation since time-based labels can be added to the nodes as they are received, so a node is a pair (n1, t1) in this case where t1 is the timestamp assigned to the node.
The last step of the algorithm is to check whether a node v is reachable from u in the original graph using the labeling information. For this we need to check whether (v, 1) is reachable from (u, 1) in the tree transformation. Assume that the label of (v, 1) is l1 and the label of (u, 1) is l2 then there are two cases. First if the interval represented by l1 is in the interval represented by l2 then v is reachable from u and this step takes constant time. Second if the interval represented by l1 is not in the interval represented by l2 then we also need to check the other copies of v and determine if a copy of v is reachable from a duplicated node that is reachable from (u, 1). For instance if the label of (v, 2) is l3 = (l4, l1) to determine if (v, 2) is reachable from (u, 1) we check if at least one of the intervals represented by l4 or l1 is in the interval represented by l2 and return ’reachable’ if so, otherwise we check all the duplicated nodes reachable from (u, 1) and determine whether a copy of v is reachable from them. Since the size of the set of the duplicated nodes is O(t), the time complexity of this step is O(t). 4
Graph reachability is a well studied problem which has applications in many fields. The problem attracted more attention with the huge increase in data where graph structures play an important role in representing the connections and the dynamic nature of it. In this paper, we reviewed the various graph reachability algorithms and their applicability for rapidly changing graphs. We also outlined an algorithm designed exclusively for these types of graphs.
As future work we plan to extend our survey on the literature, provide a detailed algorithm and analyze how it performs in real applications that involve rapidly changing graphs. We also plan to propose methods for a reasoner component that uses different (and possibly hybrid) reachability algorithms depending on the structure of the input graph and time/space requirements.