{'fraction_non_alphanumeric': 0.03812918556923742, 'fraction_numerical': 0.01485201987470296, 'mean_word_length': 4.236026015647092, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
TopCom: Index for Shortest Distance Query in Directed Graph

Finding shortest distance between two vertices in a graph is an important problem due to its numerous applications in diverse domains, including geo-spatial databases, social network analysis, and information retrieval. Classical algorithms (such as, Dijkstra) solve this problem in polynomial time, but these algorithms cannot provide real-time response for a large number of bursty queries on a large graph. So, indexing based solutions that pre-process the graph for efficiently answering (exactly or approximately) a large number of distance queries in real-time is becoming increasingly popular. Existing solutions have varying performance in terms of index size, index building time, query time, and accuracy. In this work, we propose T OP C OM , a novel indexing-based solution for exactly answering distance queries. Our experiments with two of the existing state-of-the-art methods (IS-Label and TreeMap) show the superiority of T OP C OM over these two methods considering scalability and query time. Besides, indexing of T OP C OM exploits the DAG (directed acyclic graph) structure in the graph, which makes it significantly faster than the existing methods if the SCCs (strongly connected component) of the input graph are relatively small.


INTRODUCTION
Finding shortest distance between two nodes in a graph (distance query) is one of the most useful operations in graph analysis. Besides the application that stands for its literal meaning, i.e. finding the shortest distance between two places in a road network, this operation is useful in many other applications in social and information networks. For instance, in social networks, the shortest path distance is used in the calculation of different centrality metrics, including closeness centrality and betweenness centrality [Okamoto et al. 2008;Erdem Sariyuce et al. 2013]. It is also used as a criterion for finding highly influential nodes [Kempe et al. 2003], and for detecting communities in a network [Backstrom et al. 2006]. Scientists have also used shortest path distance to generate features for predicting future links in a network [Hasan and Zaki 2011]. In information networks, shortest path distance is used for keyword search [Kargar and An 2011], and also for relevance ranking [Ukkonen et al. 2008].
Due to the importance of the shortest path distance problem, researchers have been studying this problem from the ancient time, and several classical algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) exist for this problem, which run in polynomial time over the number of vertices and the number of edges of the network. However, as real-life graphs grow in the order of thousands or millions of vertices, classical algorithms deem inefficient for providing real-time answers for a large number of distance queries on such graphs. For example, for a graph of a few thousand vertices, a contemporary desktop computer takes an order of seconds to answer a single query, so thousands of queries take tens of minutes, which is not acceptable for many real-time applications. So, there is a growing interest for the discovery of more efficient methods for solving this task.
Various approaches are considered for obtaining an efficient distance query method for large graphs. One of them is to exploit topological properties of real-life networks that adhere to some specific characteristics. For instance, many researchers exploit the spatial and planar properties of road networks [Tao et al. 2011;Abraham et al. 2011;Yan et al. 2013] to obtain efficient solutions for distance queries in road networks. However, for a general network from any other domain, such methods perform poorly [Abraham et al. 2012]. The second approach is to perform pre-processing on the host graph and build an index data structure which can be used at runtime to answer the distance query between an arbitrary pair of nodes more efficiently. Several indexing ideas are used, but two are the most common, landmark-based indexing [Tretyakov et al. 2011;Qiao et al. 2014;Potamias et al. 2009;Akiba et al. 2013] and 2-hop-cover indexing [Cohen et al. 2002]. Methods adopting the former idea identify a set of landmark nodes and pre-compute all-single source shortest paths from these landmark nodes. During query time, distances between a pair of arbitrary nodes are answered from their distances to their respective closest landmark nodes. Most of these methods deliver an approximation of shortest path distance except a method presented in [Akiba et al. 2013]. Methods adopting the two-hop cover indexing generally find the exact solution for a distance query [Jin et al. 2012b;Jiang et al. 2014;. These methods store a collection of hops (paths starting from that node), such that the shortest path between a pair of arbitrary vertices can be obtained from the intersection of the hops of those vertices.
A related work to the shortest path problem is the reachability problem. Given a directed graph G(V, E), and a pair of vertices u and v, the reachability problem answers whether a path exists from u to v. This problem can be solved in O(|V |+|E|) time using graph traversal, where V is the set of vertices and E is the set of edges. However, using a reachability index, a better runtime can be obtained in practice. All the existing solutions [Yildirim et al. 2012;Zhu et al. 2014] of the reachability problem solve it for a directed acyclic graph (DAG). This is due to the fact that any directed graph can be converted to a DAG such that a DAG node is a strongly connected component (SCC) of the original graph; since any nodes in an SCC is reachable to each other, the reachability solution in the DAG easily answers a reachability query in the original graph. The indexing idea that we propose in this work also exploits the SCC, but unlike existing works we solve the distance query problem instead of reachability.
In this work, we propose TOPCOM 1 , an indexing based method for obtaining exact solution of a distance query in an arbitrary directed graph. In principle, TOPCOM uses a 2-hop-cover solution, but its indexing is different from other existing indexing methods. Specifically, the basic indexing scheme of TOPCOM is designed for a DAG and it is inspired from the indexing solution of the reachability queries proposed in ]. Due to its design, TOPCOM exhibits a very attractive performance for a DAG or general graph in which SCCs are relatively small. However, we also extend the basic indexing scheme so that it also solves the distance query for an arbitrary directed graph. We show experiment results that validate TOPCOM's superior performance over IS-Label  and TreeMap [Xiang 2014] which are two of the fastest known indexing based shortest path methods in the recent years. Following other recent works, we also compare our method with bi-directional Dijkstra, which is a well-accepted baseline method for distance query solutions in a directed graph. Note that, this journal article is an extended version of a published conference article [Dave and Hasan 2015]; the conference article works for DAG only, but this work solves distance query indexing for arbitrary directed graphs.

RELATED WORKS
Shortest distance on a graph has many interesting recent and earlier works. In the section we discuss the most important works among these under two categories: (1) Online shortest distance calculation, (2) Offline (Index based) shortest distance calculation.

Online shortest distance calculation:
For unweighted graph, the simplest online method to find shortest distance is Breadth First Search (BFS) with time complexity O(|V | + |E|), where V is number of vertices and E is number of edges of the graph. For weighted graph, most well-known single source shortest distance algorithm is Dijkstra's algorithm, which computes shortest distance for weighted graph with positive weights. Using a binary heap based priority queue, the complexity of Dijkstra's algorithm is O(|E| lg |V |) and the same using a Fibonacci heap is O(|E| + |V | lg |V |). Another well known algorithm for single source shortest path is the Bellman-Ford algorithm [Bellman 1958;Cormen et al. 2001] with time complexity O(|V | · |E|), which is generally slow for large graphs with millions of nodes and edges.
There are methods proposed by different researchers to improve the above classical shortest distance methods [Bauer et al. 2010;Wagner and Willhalm 2007]. Although, they do not improve the worst case complexity of the shortest path algorithm, they do exhibit good average-case behavior. The most popular among these methods is Bidirectional Dijkstra [Sint and de Champeaux 1977], which is particularly applicable when the objective is to obtain the shortest distance between a pair of vertices. The computational complexity of bidirectional search can be denoted as O(b d/2 ), where b is the branching factor and d is the distance from start node to target node. Real life networks have small value of d (typically smaller than 10)-a fact that makes this algorithm an attractive choice for many applications. In this work, bidirectional Dijkstra is one of the methods with which we compare our proposed solution.

Offline (Index based) shortest distance calculation:
For large graphs, online methods are slower than an indexing based method, so most of the recent research efforts are concentrated towards indexing based methods. The literature for shortest distance indexing is quite vast, so, we review few of the works that have published in the recent years. For a detailed review, we refer the readers to read [Zwick 2001;Sommer 2014].
Many of the existing works for shortest distance computation is specifically designed for the road networks [Yan et al. 2013;Rice and Tsotras 2010;Tao et al. 2011;Zhu et al. 2013a;Abraham et al. 2011;Geisberger et al. 2008;Sanders and Schultes 2005;Jung and Pramanik 2002]. Such networks show hierarchical structures with the presence of junctions, hubs, and highways; the shortest distance computation methods for these networks exploit the hierarchical structure for compressing distance matrix or for building distance indices [Rice and Tsotras 2010;Geisberger et al. 2008]. For example, Sanders et al. [Sanders and Schultes 2005] use highway hierarchy and design an exact shortest distance computation method that runs faster than a method that does not use the hierarchy structure. Zhu et al. [Zhu et al. 2013a] design a hierarchy based indexing and prove that the results on real-life graphs is close to the theoretical complexity of the proposed method. Jung et al. [Jung and Pramanik 2002] design an efficient shortest path computation method for hierarchically structured topographical road maps. Abraham et al. [Abraham et al. 2011] have proposed an efficient hub-based labeling (HL) method to answer shortest path distance query on road networks. Tao et al. [Tao et al. 2011] explore the spatial property and find k-skip graph which can answer k-skip shortest path i.e. path created from the original shortest path by skipping at-most k consecutive nodes. Recently Yan et al. [Yan et al. 2013] propose a method to find the distance preserving sub-graphs to answer a shortest distance query more efficiently. However, most of the indexing schemes for the road networks are based on some specific property of the road networks and they are ineffective for general graphs that do not satisfy those properties of road networks [Abraham et al. 2012].
Finding exact shortest distance in a large graph is a costly task, hence few researchers have proposed methods for computing estimated shortest distance [Tretyakov et al. 2011;Gubichev et al. 2010;Qiao et al. 2014;Potamias et al. 2009]. The most common among the estimated shortest distance based methods is the landmark based method, which selects a set of landmark nodes based on some criteria and finds shortest paths that must go through those landmark nodes. The main task here is to decide the set of vertices that are optimal choice as landmarks. However, it has been shown that this optimization problem is N P-Hard [Potamias et al. 2009], so researchers adopt various heuristics based approaches for choosing those landmarks. Potamias et al. [Potamias et al. 2009] compare centrality and degree based approaches for selecting landmarks. Gubichev et al. [Gubichev et al. 2010] propose a sketch based indexing method for estimating answer of a shortest distance query. Treyakov et al. [Tretyakov et al. 2011] propose a landmark based fully dynamic approximation method using shortest path tree and also obtain an improved set of vertices as landmark; they show that their method has less approximation error than other landmark based approaches. Qiao et al. [Qiao et al. 2014] propose a query based local landmark method which selects landmark nodes that are local to the query in the sense that the obtained shortest path is the closest to the real shortest path as much as possible; this method also improves the estimation accuracy. Our proposed indexing method, TOPCOM, is not comparable to these methods, because unlike these methods, our method provides exact shortest path distance.
There are some other works for finding shortest distance in large graphs which are proposed very recently; examples include Zhu et al. 2013b;Jin et al. 2012b;Cheng and Yu 2009;Abraham et al. 2012;Xiang 2014;Akiba et al. 2013;Gao et al. 2011;Wei 2010;Cheng et al. 2012]. Many of these have unique ideas, so it is difficult to categorize them under a generic shortest path method. For example, Gao et al. [Gao et al. 2011] use a relational approach and propose an index called SegTable which stores local segments of a shortest distance. Zhu at al. [Zhu et al. 2013b] propose a method to answer single source shortest distance query for a huge graph on disk. Akiba et al. [Akiba et al. 2013] 2 propose a unique pruning method based on degree of a vertex, which can efficiently reduce the search space of BFS. Highway centric label (HCL) [Jin et al. 2012b] is one of the fastest recent methods that is proposed for a shortest distance query on both directed and undirected graphs. In a follow-up work, Xiang proposes TreeMap [Xiang 2014], a tree decomposition based approach for solving distance query exactly; the author compares TreeMap's solution with those of HCL to show that the former has better performance. Another recent method is called IS-Label which is proposed by Fu et al. . They have also shown that that IS-Label has superior performance than HCL. In this work, we compare TOPCOM with both IS-Label and TreeMap, which are among the best of the existing index based methods.
Our proposed method exploits conversion of a directed graph into a directed acyclic graph (DAG) by collapsing strongly connected components (SCCs) into a ver- tex. It is a widely used approach for solving reachability query task in a directed graph Jin et al. 2009;Yildirim et al. 2012;Jin et al. 2008;Jin et al. 2012a;Cheng and Yu 2009]. Any two nodes in an SCC are reachable from each other, hence for a directed graph the reachability query between two nodes can be answered through the reachability answer between their corresponding DAG nodes. However, note that, a reachability query is easier than a distance query, because the latter provides distance value as answer, which is relatively harder as the graph can be weighted. Specifically, for online (non-indexing) solution, reachability has a complexity of O(|V |+|E|), and shortest distance query for weighted graph has a higher complexity, O(|E| lg |V |). Authors in ] uses topological folding of DAG for answering reachability query. Our proposed method TOPCOM also uses topological folding property of DAG to compress the DAG level-wise, but unlike the above work, our work answers distance queries on weighted graph. Cheng et al. [Cheng and Yu 2009] is another existing work which also proposes a DAG based approach for answering distance queries by finding distance aware 2-HOP cover. Note that, one of the known limitations of indexing based methods is that they require more memory, but this is not a concern for TOPCOM with today's commodity machine having main memory in multiples of 2 GB.

METHOD
In this section, we discuss the shortest distance indexing of TOPCOM for a DAG. In subsequent section, we will show how this can be adapted for a general directed graph.

Topological compression
The main idea of TOPCOM is based on topological compression of DAG, which is performed during the index building step. During the compression, additional distance information is preserved in a data structure which TOPCOM uses for answering a dis-tance query efficiently. For the sake of simplicity, in subsequent discussion we assume that the given graph is unweighted for which the weight of each edge is 1 and the distance between two vertices is the minimum hop count between them. We will discuss the necessary adaptations that are needed for a weighted graph at the end of this section. Topological Level: Given a DAG G, we use V (G) and E(G) to represent set of vertices and edges of G, respectively. The topological level of any vertex v ∈ V (G), defined as topo(v), is 1 if v has no incoming edge, otherwise it is at least one higher than the topological level of any of v's parents. Mathematically, Example: Consider the DAG G in Figure 1(a). Topological level of vertices, a, b, and c is 1, as the vertices have no incoming edge. The topological level of vertex l is 4, as one of the predecessor node of l is i, which has a topological level value of 3. T opo(G) is equal to 7, because 7 is the largest topological level value for one of the vertices in G.
Topological compression of a DAG is performed iteratively, such that the compressed output of one iteration is the input of subsequent iteration. For an input DAG G, one iteration of topological compression removes all odd-topology vertices from G along with the edges that are incident to the removed vertices. All single-level edges are thus removed, as one of the adjacent vertices of these edges is an odd-topology vertex. A multi-level edge is also removed if at least one of the endpoints of the edge is an odd-topology vertex. As a result of this compression, the topological level of G reduces by half. For the purpose of shortest distance index building, starting from G = G 0 , we apply this compression process iteratively to generate a sequence of DAGs G 1 , G 2 , · · · , G t such that the topological level number of each successive DAG is half of that of the previous DAG, and the topological level number of the final DAG in this sequence is 1; i.e., topo(G i+1 ) = ⌊topo(G i )/2⌋, and topo(G t ) = 1, where t = ⌊log 2 topo(G)⌋.
Example: Consider the same DAG G = G 0 in Figure 1(a). Its topological compression in the first iteration, G 1 is shown in Figure 2(a), and in the second iteration, G 2 is shown in Figure 2(c). G 2 is the last compression state of G 0 , as topological level of G 2 is 1. Note that, in G 1 , all odd-topology vertices of G 0 , such as, a, b, c, h, i, j, etc. are removed. All single-level edges of G 0 , such as, (e, i), (k, n), (p, s), etc. are removed. Multi-level edges, such as, (b, l) and (m, s) are also removed. However, there are newly added vertices in G 1 , such as b ′ , h ′ , r1, and s1, along with newly added edges, such as, (b ′ , l) and (e, r1). More discussion about these additional vertices and edges are given in the following paragraphs.
Each iteration of topological compression of a DAG causes loss of information regarding the connectivity among the vertices; for correctly answering distance queries TOPCOM needs to preserve the connectivity information as the input DAG is being compressed. The preservation process gives rise to additional vertices and edges in G 1 , which we have seen in the above example. The connectivity preservation process is discussed in detail below.
The most common information loss is caused by the removal of single-level edges. However, such edges are also easily recoverable from the lastly compressed graph in which the edges were present before their removal. So, TOPCOM does not perform any action for explicit preservation of single-level edges. To preserve the information that is lost due to the removal of multi-level edges, TOPCOM inserts additional eventopology vertices, together with additional edges between the even-topology vertices to prepare the DAG for the compression. The insertion of additional vertices and edges for preserving the information of a removed DAG multi-level edge e = (u, v) is discussed below along with an example given in Figure 1. In this figure, the topological levels are mentioned in rectangular boxes. On the left side we show the original graph, and on the right side we show the modified graph which preserves information that is lost due to compression.
There are four possible cases for an edges (u, v) that is being removed due to topological compression. Case 1: (topo(u) is odd and topo(v) is even). Compression removes the vertex u, so we add a fictitious vertex u ′ such that topo(u ′ ) = topo(u) + 1. Then we remove the multi-level edge (u, v) and replace it with with two edges (u, u ′ ) and (u ′ , v). Since topological level number of both u ′ and v are even, the topological compression does not delete the edge (u ′ , v). For example, consider the multi-level edge (b, l) in figure 1(a), topo(b) = 1 (odd), and topo(l) = 4 (even). In the modified graph Figure 1 Case 2: (topo(u) is even and topo(v) is odd). This case is symmetric to Case 1 as compression removes v instead of u. We use a similar approach like Case 1 to handle this case. We create v 1 , a copy of the vertex v such that topo(v 1 ) = topo(v) − 1 and replace the multi-level edge (u, v) with two edges (u, v 1 ) and (v 1 , v). To distinguish the vertices added in these two cases, the newly added vertex is called fictitious for Case 1, and it is called copied for Case 2. The justification of such naming will be clarified in latter part of the text. Example of Case 2 in Figure 1(a) is edge (m, s), where topo(m) = 4 (even) and topo(s) = 7 (odd). In modified graph, we add copied node s 1 and replace the original edge with two edges shown in Figure 1 Case 3: (topo(u) is odd and topo(v) is odd). In this case we use the combination of above two methods and add two new vertices u ′ and v 1 . We set topological level numbering of new vertices as mentioned above. Also we replace multi level edge (u, v) with three different edges (u, u ′ ) , (u ′ , v 1 ), and (v 1 , v). Multi level edge (h, r) in Figure 1(a) is an example of this case. As shown in Figure 1(b), we add two new vertices h ′ and r 1 and three new edges, (h, h ′ ), (h ′ , r 1 ), and (r 1 , r) after deleting the original edge (h, r). Note that, if topo(u) = topo(v) − 2, topo(u ′ ) = topo(v 1 ). In this case, we treat it as Case 1 by adding only u ′ (but not v 1 ) and following the Case 1. It generates a single-level edge (u ′ , v), which we do not need to handle explicitly.
Case 4: (topo(u) is even and topo(v) is even). This is the easiest case as both u and v are not removed by the compression process and we do not make any change in the graph. Also note that the changes in the above three cases convert those cases into this Case 4. For example, applying Case 1 for edge (b, l) in Figure 1 creates new multi-edge (b ′ , l) which is an occurrence of Case 4. Similarly Case 2 creates the Case 4 multi-edge (m, s 1 ).
Dummy edges data structure: We described earlier, we do not need to handle singlelevel edges separately. However if two continuous single-level edges are removed, we still need to maintain the logical connection between the even-topology vertices. For example, in Figure 1(a) edges (e, i), (i, k), and (i, l) are single-level edges which will be deleted after the first compression iteration because topo(i) = 3. Now, information of logical (indirect) connection between e to k and l needs to be maintained, because all three vertices will exist after the compression. To handle this, we add new dummy edges (e, k) and (e, l); dummy edges are shown as dotted lines in Figure 1(b). Note that, for any dummy edge (u, v), topo(v) − topo(u) = 2 in the current DAG and the edges for which the node-topology difference is higher than 2 are handled by the above 4 multilevel edge cases. For same start and end nodes, if there are multiple dummy edges, TOPCOM considers edge with the smallest distance. To find the dummy edges, we scan through all odd-topology vertices and find their single-level incoming and outgoing edges. We store all these dummy edges along with the corresponding distance value in a list called DummyEdges as shown in Figure 1, which we use during the index generation step. For example dummy edge (d, h ′ ) has a distance 2 in the Figure 1, then At each compression iteration, we first obtain a modified graph, with fictitious vertices, copied vertices, and dummy edges and then apply compression to obtain the compressed graph of the subsequent iteration. The fictitious vertices, copied vertices, and dummy edges of the modified graph in earlier iteration become regular vertices and edges of the compressed graph in subsequent iteration. The above modification and compression proceeds iteratively until we reach t-compressed graph, G t , for which the topological level number is 1. We use G m to denote the modified uncompressed graph, G 1 m to denote the modified 1-compressed graph, G 2 m to denote the modified 2compressed graph and so on. For example, Figure 2(a) shows G 1 which is obtained by compressing the modified graph G m in Figure 1(b). Figure 2(b) shows G 1 m , the modified 1-compressed graph, and Figure 2(c) shows G 2 , the 2-compressed graph. We refer the set of all modified compressed graphs as G * m , i.e. { G t m , ..., G 2 m , G 1 m }.

Index generation
TOPCOM's index data structure is represented as a table of key-value pairs. For each key, (vertex) v of the input graph, the value contains two lists: (i) outgoing index value , which stores shortest distances from v to a set of vertices reachable from v; and (ii) incoming index value I in v , which stores shortest distances between v and a set of vertices that can reach v. Both the lists contain a collection of tuples, vertex id, distance , where vertex id is the id of a vertex other than v, and distance is the corresponding shortest path distance between v and that vertex.
TOPCOM also inserts (Line 16 in Algorithm 1) elements of I in u and I out w into I in v and I out v , respectively, using recursive calls. Algorithm 1 shows the pseudo-code of the index generation procedure for outgoing index values only. An identical piece of code can be used for generating incoming index values also, but for that we need to exchange the roles of fictitious and copied vertex, and change the I out * with I in * in Line 5-21 (more discussion on this is forthcoming). As shown in Line 2 of Algorithm 1, TOPCOM first collects all odd-topology vertices in variable O and builds out-indexes for each of these vertices using outgoing edges from these vertices (the edge (v, w) in Line 5 of Algorithm 1). Note that, vertices v and w in G curr m can be fictitious or copied vertex; TOPCOM uses the subroutine GETORIGINAL() Table I: Intermediate index generated from the DAG in Figure 2 which returns original vertex corresponding to any fictitious or copied vertex, if necessary (Line 4 and 6). Using the data structure DummyEdges (discussed in section 3.1), it first checks whether the edge (v, w) is a dummy edge (Line 10); if so, it obtains the actual distance from the data structure. In case the end-vertex w is a fictitious vertex, TOPCOM decrements the distance value by 1 (Line 14), because for each fictitious vertex, an extra edge with distance 1 is added from the original vertex to the fictitious vertex which has increased the distance value by one. For instance, in the graph in Figure 1, the actual distance from a to h is 2, but the fictitious vertex h ′ records the distance to be 3, which should be corrected. On the other hand, if w is a copied vertex, TOPCOM does not make this subtraction, because when a copied vertex is used as destination instead of the original vertex, the distance between the source vertex and the copied vertex correctly reflects the actual distance. For an example, in the same graph, the distance between e and r is 1; when we use the copied vertex r1 instead of r, distance between e and r1 is recorded as 1, which is the correct distance between e and r; so no distance correction is needed during the out index building when the destination vertex is a copied vertex. This is the reason why we make a distinction between the fictitious vertices and the copied vertices. Finallly note that, after generating indexes for each vertex there may be multiple entries for some vertices; from these multiple entries we need to get the smallest value (entry) and remove others. For building incoming index values, TOPCOM subtracts 1 for a copied vertex, but does not subtract 1 for a fictitious vertex, as the roles of start and end vertices flip for the incoming index values. Below, we give a complete index building example using the vertex a of the graph in Figure 1.

Example:
We want to find the outgoing index (value) for vertex a (key) of the graph G in Figure 1(a). topo(G) = 2, so we start building index using the graph G 1 m , which is shown in Figure 2(b). In the first iteration, TOPCOM builds I out d = { h, 1 }; the distance value of 1 comes as follows: TOPCOM uses distance of dummy edge (d, h ′ ) that is 2 (Figure 1-II) and then it replaces the fictitious vertex h ′ with h and obtains a distance of 1 by subtracting 1 from 2 (Line 14). It also inserts the following entries under the key e; i.e., I out e = { k, 2 , l, 2 }. The resulting indexes after this iteration is presented in Table I; incoming index values for keys b, d, e, f, g are empty (not presented in the table) and similarly outgoing index values for keys p, q, r, s are empty. For next iteration considering G m , TOPCOM inserts d, 1 in I out a ; using recursive calls of algorithm 2 (Line 11), this function also inserts h, 2 in I out a , recursion stops at h because I out h is empty (Line 6). Similarly, e, 1 and k, 3 , l, 3 are inserted in I out a recursively from I out e . At the end of the algorithm 1 we remove duplicate entries from indexes. For example, incoming index for key s has two entries for vertex m, m, 1 and m, 2 , one corresponding to edge (m, s1) in G 1 m and the other is a recursive result from q to s in G m . TOPCOM considers m, 1 and discards the other entry from I in s . For the graph in Figure 1(a), corresponding indexes are presented in Table II.  Table II: Index for the DAG in Figure 1 key

Index for weighted graph
For weighted graph, TOPCOM makes some minor changes in the above algorithm. First, distance values are stored both in the indexes and in the DummyEdge data structure. Many of these distances are implicitly 1 for unweighted graph, which is not true for weighted graph, so, for the latter TOPCOM stores the distance explicitly. Also, it ensures that the distance value between fictitious (or copied) vertices and an original vertex is one, so that the Algorithm 1 works as it is.

Query processing
For query processing, TOPCOM uses the distance indexes that is built during the indexing stage. For a given distance query from u to v, i.e. to compute δ(u, v), TOPCOM intersects outgoing index value of key u i.e. I out u and incoming index value of key v i.e. I in v and finds common vertex id in I out u and I in v , along with the distance values. To cover the cases, when v is in the outgoing index value of u, or u is in the incoming index value of v, the tuples u, 0 and v, 0 are also added in I out u and I in v respectively and then the intersection set of the indexes is found. If the intersection set size is 0, there is no path from u to v and hence the distance is infinity. Otherwise, the distance is simply the sum of the distances from u to vertex id and vertex id to v. If multiple paths exist, we take the one that has the smallest distance value.

Example:
We want to find δ(a, s) in Figure 1. From table II, I out a ∩ I in s = {k, l}. Now, we need to sum up the corresponding distance values, that gives { k, 6 , l, 6 }. Now we need to find smallest distance value; in this case both the values are same, hence we can provide any one as a result.

Theoretical proofs for correctness
In this section, we prove the correctness of TOPCOM, through the claim that TOP-COM's index is based on 2-hop covers of the shortest distance in a graph and method described in Section 3.4 gives correct shortest distance value. For shortest path, such a cover is a collection S of shortest paths such that for every two vertices u and v, there is a shortest path from u to v that is a concatenation of atmost two paths from S. [Cohen et al. 2002]. That is, shortest path from u to v is stored in S or there is an intermediate node x such that shortest paths from u to x and from x to v are stored in S. For TOPCOM's index also, the shortest distance from any node u to node v is the 2-hop cover such that the index itself has shortest distance value from u to v or there is an intermediate node x which would be present in both I out u and I in v .
Example: In DAG G in Figure 1(a) to find distance from a to s, we need to check the outgoing index value for vertex a and the incoming index value for vertex s in Table II. This gives us two possible shortest paths passing through intermediate node k or l, because distance in both cases is same. Thus, there can be multiple shortest paths however, atmost one intermediate node in the index. In the Theorem 3.3, we try to identify the topological layer of an intermediate node x. We identify a unique topological level for each pair of u and v, which tells there is atmost one intermediate node in a shortest path from u to v because in DAG there cannot be a directed edge within topological layer. We begin with the following lemmas, which will be useful for constructing the proof of the theorem.
LEMMA 3.1. In G m , if a node u is at topological level 2 i , it will be at topological level 1 in G i .
PROOF. TOPCOM compression method removes all odd-topology nodes and carries over nodes from the even topological levels to the next compression iteration. Thus any node from an even topological level 2x in some compressed graph will be at topological level x in the compressed graph of next iteration. Say, the node u is at topological level 2 i in G m , then it will be at topology level 2 i−1 in G 1 . Since 2 i−1 is also even, no fictitious or copied vertex will be added for u, and in G 1 m , it will remain at 2 i−1 level. In the next compression iteration, u will simply be moved to 2 i−2 level in G 2 and so on. Hence, it will be at level 2 i−i = 2 0 = 1 level in G i graph.
Example In the graph G m shown in Figure 1(b), the node d is at topological level 2 and the node k is at topological level 4. In G 1 shown in Figure 2(a) the node d is at topological level 1; similarly, in G 2 shown in Figure 2(c), the node k is at topological level 1.  In the modified graph G m , all the edges from/to an odd topology vertex connects with an even topology vertex, through the use of fictitious/copied nodes (if needed). Hence, if any node in DAG G m is at an odd topological level, it cannot be included as an index value. Additionally when we compress G i m to get G i+1 , we only include nodes from even topological levels, hence nodes from odd levels will never be included as a value for index building at compressed levels also.
Example: See the completely built index of the graph G in Figure 1(a) as shown in Table II. The nodes that appear as values are {d, e, b ′ (b), f, g, h ′ (h), k, l, m, r 1 (r), p, q, s 1 (s)}. All of these are from the even topology nodes in G m as shown in Figure 1(b). THEOREM 3.3. For finding shortest distance from u to v, assume that u has topological level number L u and v has topological level number L v in G m . We define Now, if there is a shortest path from u to v, for each shortest path, exclusively, one of the following is true.

Case 2: There is an intermediate node x, and
topo(x) = 2 n + C for some constant offset C.
PROOF. We prove this theorem using mathematical induction on n.
Base case: n = 1. If there is a direct edge from u to v then case 1 is true because if L u = 2 then I in v includes u or if L v = 2 then I out u includes v. If there is an intermediate node x then L u = 1 and L v = 3, hence topo(x) = 2 that shows case 2 is true. From Lemma 3.2 both I out u and I in v include the node x if there is a path from u to v. In this case constant offset C would be zero.

Induction hypothesis:
Here we assume that for n = d given theorem is true.

Induction step:
We want to prove, for n = d + 1 given theorem is true. If there is no intermediate node x then case 1 is true. Hence, we discuss the only scenario where there is an intermediate node x and we want to show that x is in both I out u and I in v . We sub-divide the proof for zero and non-zero values of constant offset C.

Constant offset C is zero:
If there are 2 d+1 levels, then compression step would be conducted at least one more time than 2 d levels. From Lemma 3.1 at the d'th step of compression, nodes at topological level 2 d in graph G m are at 1 st topological level in G d and nodes from topological level 2 d+1 would be at 2 nd topological level.
Hence, TOPCOM will build index for keys (nodes) from topological level 2 d in graph G m , and those index values include nodes from topological level 2 d+1 . As our method recursively includes already built index values, the nodes from topological level 2 d+1 would be recursively included to corresponding outgoing index values for keys at lower compression levels. Hence, if topo(x) = 2 d+1 then it is present in outgoing index value of u.
The similar argument works for incoming index of v.

Constant offset C is non-zero:
If we cannot find n that satisfies equation 1 then constant offset C is non-zero. In this case offset can be calculated as : Now, we define modified topological level number of u is L m u , where L m u = L u − C and similarly modified topological level number of v is L m v = L v − C. We use L m u and L m v in equation 1 to get n n = argmax i (L m u ≤ 2 i ≤ L m v ) Now, with topo(x) = 2 n + C, argument works similarly as zero offset.
Example of non-zero offset C: In Figure 1(b), we want to know the shortest distance from n to r where corresponding topological levels are L n = 5 and L r = 7 respectively. For this, we can not find any n that satisfies the equation 1. From equation 2, we can calculate n low = 2, using which modified topological levels L m n = 1(5 − 2 2 ) and L m r = 3 can be obtained. From L m n and L m r we get m = 1. Now, 2 1 + 2 2 = 6 is the topological level of intermediate node p, which is present in both I out n and I in r (Table II). If we look carefully L m n and L m r is a base case in the mathematical induction proof of Theorem 3.3, and L n (5), L r (7) with offset C behave exactly the same as the base case.

Note:
If there is no node from topological level 2 n in the shortest path from u to v, then there must be one multilevel edge which skips that level. For a node incident to that multilevel edge, at some step of the compression, we need to prepare fictitious/copied node. That new fictitious/copied node works as a node from topological For example, as depicted in Figure 1(b), shortest path from a to r doesn't pass through any node from topological level 4(2 2 ) in G m , but it has a multilevel edge (e, r 1 ). In G 2 m (Figure 2(b)), this edge causes a fictitious node e ′ at topological level 2 which is (logically) topological level 4 in G m . The resulting index in Table II shows that, the node e ′ (e) is included as a value in the incoming index of r (I in r ) and also included in I out a .

INDEXING FOR GENERAL DIRECTED GRAPH
Any directed graph G can be converted to a Directed Acyclic Graph (DAG) G d , by considering each strongly connected component (SCC) of G as a node of G d . Thus in DAG, the edges within a SCC are collapsed within the corresponding node. However, if an edge in G connects two vertices from two distinct SCCs, in G d those SCCs are connected by a DAG edge. To build the shortest path index for a general directed graph, TOPCOM first uses Tarjan's algorithm [Tarjan 1972] to convert G to a DAG G d by finding all SCCs of G. It also maintains a necessary data structure that keeps the mapping from a DAG node to a set of graph vertices, and vice-versa. We call this a parent-child mapping, i.e., a DAG node is the parent of graph vertices which are part of the corresponding SCC. A DAG edge connects two vertices, one from a distinct SCC. We call such vertices terminal vertices. A single DAG edge between a pair of SCCs may encapsulate multiple paths (one edge or multiple edges) of Graph G such that the end vertices of these paths are terminal vertices in those pair of SCCs. TOPCOM's DAG edge data structure contains a set of tuples, each representing one of these paths. A tuple has three elements: node-id of start terminal vertex, node-id of end terminal vertex, and the distance between these two vertices in G. For example consider Figure 4a(1), a DAG edge (a, b) stores {(3, 5, 1), (4, 7, 1), (3, 7, 2), (4, 5, 3)}, first two tuples represent a single-edge path, but the last two represent multi-edge paths. 3, 4 are terminal vertices of DAG node a, and 5,7 are terminal vertices of DAG node b. For each tuple, the third field stores the shortest distance between the pair of terminal vertices in the first two fields of that tuple. To compute distance between an arbitrary pair of vertices within an SCC, TOPCOM also pre-computes all-pair shortest paths among all graph nodes belonging to a single SCC and store them in shortest path index. In reallife directed networks, the size of SCCs are generally not very large, so storing all-pair distances within a SCC in the shortest path index is feasible.

Distance for dummy edges:
For an unweighted DAG two consecutive edges yield a distance value of 2, but for DAG which is a compressed representation of a general unweighted directed graph, two consecutive DAG edges may constitute an arbitrary distance value. This is due to the fact that the shortest path may visit a large number of vertices which are part of the start, middle, and end SCC. For an example, see Figure 4a(1); in this figure, the rectangles "even1", "odd" and "even2" are the topological level numbers; a, b and c are the DAG nodes (ellipses), and nodes with numeric ids are nodes of G. Two consecutive DAG edges are (a, b) and (b, c) connecting SCCs a, b and SCCs b, c, respectively. The shortest distance between a and c depends on the terminal nodes of a and c that are being used. If terminal node of a is 3 and terminal node of c is 13, the distance is 5, following the path 3 − −4 − −7 − −10 − −12 − −13. In this path, besides the distance 2 over the DAG edges, there are three within-SCC edges, one in each of SCCs. Thus, the total distance for a dummy edge is the sum of (i) distance from a terminal vertex of staring SCC to a terminal vertex in the middle SCC, (ii) distance between a pair of terminal vertices in the middle SCC, and (iii) distance from a terminal node in the middle SCC to a terminal node in the end SCC. To account for this, TOPCOM computes the dummy edge distance by considering all possible combination of terminal nodes in each SCCs.

Modification in index and query processing
TOPCOM Index for general graph stores the bidirectional mapping between the DAG nodes and the vertices of the input graph. For every DAG edge (and also for DAG dummy edges), it stores the set of tuple based representation that we have discussed in the above subsection. It also stores all pair distance between each of the vertices within an SCC. Above all, it prepares and stores the 2-hop cover DAG indexes for the DAG representation of the input graph using the methodologies that we discussed in Section 3. For query processing, given a query (u, v), TOPCOM first identifies the corresponding SSE nodes in the DAG using the bidirectional map. Say, these SSEs are s u and s v , respectively. If s u = s v , TOPCOM simply uses the within SSE all-pair index and return the distance between u and v. Otherwise, it first finds the set of out-terminal SSE nodes of s u (say, X), and in-terminal SSE nodes of s v (say, Y ). Then it uses the 2-hop cover indexing for finding the shortest path distance between each pair of nodes-one from X, and the other from Y . It also considers within SCC distances in three SCCs: Starting DAG node: Distance from starting node of the query to start terminal node of the DAG node. For example consider figure 4a(1), where query is δ (1, 14). Now all outgoing edges from DAG a are from nodes 3 and 4, hence we need to get distances from 1 to 3 and 4 i.e. δ(1, 3) = 1 and δ(1, 4) = 2. Middle DAG node: If there is a middle node (from the 2-hop cover index) then distance from incoming edge terminal node to outgoing edge terminal node within middle DAG node needs to be calculated. In our example suppose b is middle node, then we need distance from 5 to 9 and 10, i.e. δ(5, 9) = 4, δ(5, 10) = 3 and similar for node 7. Ending DAG node: Distance from end terminal node to ending node of the query within the DAG node.:w That means in our example distance from 12 and 13 to 14 i.e. δ(12, 14) = 2 and δ(13, 14) = 1.
Here again our task is to get minimum distance among all, and we use the similar strategy as section 4.1, which is to minimize the summation of above three distances along with edge distances.
As we can see, TOPCOM's principle indexing process works with DAG and it performs well on real world datasets (Table V). One reason is, real world complex graph  (Table III) are always smaller than AD, mostly an order of magnitude smaller and specifically for AS Caida average degree reduced to 1.86 from 87.36, which is a decrease of almost two orders of magnitude. However because of DAG, we also need to handle a challenging task, i.e. maintaining distance information within SCC for each DAG node. To keep this information, most common ways are to maintain distance matrix or to keep set of edges and calculate distance at run time. Both of these methods have their own pros and cons; keeping distance matrix is the fastest access method but the size of SCC leads to space limitation i.e. we need space for O(n 2 ) elements and for huge SCC this may be a notable problem. On the other hand keeping set of edges is a memory efficient way, however all distance finding algorithms are polynomial time in terms of |V | and |E|; and for huge SCC, finding distance between nodes at run time would be much slower. This represents a well known phenomenon in Computer Science called space-time trade-off. Here for our task, time gets priority over space, hence we selected first method, where we are maintaining distance matrix for each DAG node. For large SCC, this may take high memory, however we observed that our index is still not very large for contemporary machine.

Correctness revisited
In this Section 4, we explain how to adopt the proposed indexing method for a general directed graph. For that, first we convert a general directed graph into DAG and then build index on the DAG. We describe the methods to maintain the information at both steps. We should be able to calculate shortest distance from one node to any other node within the same DAG node. When we convert a general directed graph to DAG, we maintain this information by creating appropriate data structures during conversion (Section 4).
The index generation method for DAG is further divided into two steps: 1) Topological Compression and 2) Index Generation. We need to maintain information only during the first step, because the index generation step only builds index from the graphs generated in the topological compression (first) step. The topological compression step is described in Section 3.1, where DAG is compressed iteratively by removing all odd-topology vertices and incident vertices. This compression process maintains loss of information using dummy edges, to keep the correct information we explicitly handle distance information for dummy edges as explained in Section 4.1.
Lastly, as the structure of a converted DAG is different, we need to handle the queries a little differently. We have explained the modification of query processing in Section 4.2. Hence, all the required logical modifications are handled and TOPCOM maintains correctness for general directed graph.

EXPERIMENTAL EVALUATION
We compare performance of TOPCOM with two of the recent methods (IS-Label and TreeMap) for answering distance query. We also compare TOPCOM with baseline method Bidirectional Dijkstra's algorithm, which is one of the fastest online methods for single source shortest distance queries. For both IS-Label and TreeMap, codes are provided by their authors. For these experiments we use a machine with Intel 2.4 GHz processor, 8 GB RAM and Ubuntu 14.04 LTS OS. In [Xiang 2014] the author has claimed that TreeMap works for weighted directed graphs, however we are provided with the code of unweighted version for TreeMap, hence all comparisons with TreeMap are for unweighted graphs. Additionally as Y. Xiang mentioned in the paper, TreeMap needs huge memory if tree width is above threshold (1000). The only dataset we are able to run using above machine is WikiVote. Hence for comparison with TreeMap, we used machine with AMD 2.3 GHz processor, 132 GB RAM and Red Hat Enterprise Server Release 6.6 OS. We also perform comparison to IS-Lable using same machine for two datasets (Email Eu and Epinion). Using synthetic graphs of different sizes and degrees, we show that TreeMap is not scalable for higher degree graphs. To generate these synthetic graphs we use python package networkx (procedure name, FAST GNP RANDOM GRAPH()).

Datasets
Here for our experiments, we used seven real world datasets (Table III) from different domains to show wide applicability of TOPCOM . |V | and |E| are the number of vertices and the number of edges respectively. Similarly |V DAG | and |E DAG | are the number of vertices and the edges in the DAG of the corresponding graph. AD and AD DAG are average degree values for the graph and its DAG counterpart, respectively. MD and M D DAG are maximum degrees i.e. maximum in or out degree in the graph and its DAG, respectively. Largest SCC is a size of the biggest DAG node which encapsulate the maximum number of input graph nodes.
We collected all datasets from SNAP (Stanford Network Analysis Project) web page 5 except Epinion trust network dataset, which we collected from [Massa and Avesani 2006]. AS Caida is a business relationship network and Email Eu is a snapshot of an email network generated by European Research Institute. Epinion dataset is a trust network generated from social network users, it represents which user trusts whom. Gnutella is a peer-to-peer file sharing network where Gnutella09 is a snapshot of the network on 9th August 2002 and Gnutella31 is a snapshot of the same network on 31st August 2002. W ikiV ote is a network generated from Wikipedia admin voting history data.

Results and Discussion
AS per expectation for DAG TOPCOM outperforms IS-Label method for all datasets depicted in figure 5a. Results are average query time over 10 times execution in microsecond (µs), where each method calculated 10K random queries in every execution. For more detailed comparison, if we look at table IV, we can see that for datasets Epinion, Gnutella09 and Gnutella31 TOPCOM outperforms IS-Label and TreeMap by an order of magnitude. For other datasets also TOPCOM performs 2-3 times better than both of the competing methods. If we look at the Bi-Dijkstra results, TOPCOM performs multiple orders of magnitude better for all datasets. In figure 5b results for general graphs are plotted, which clearly demonstrate superiority of TOPCOM over IS-Label for general graph. Here also we used Average Query time over 10 times ex- ecution with each run calculating 10K random queries. Now if we look at table V for dataset AS Caida IS-Label performs better than TOPCOM however the difference is 0.00003989 ms which is really very small. On the other hand TOPCOM outperforms IS-Label for all other datasets. For Gnutella31 dataset TOPCOM performs an order of magnitude better than IS-Label and surprisingly IS-Label performs really poor on Epinion dataset such that TOPCOM outperforms IS-Label by two orders of magnitude. For Guntella09 TOPCOM performs almost 7 times better and for remaining datasets TOPCOM performs almost two times better than IS-Label. Here once again TOPCOM is multiple orders of magnitude faster than Bi-Dijkstra for all datasets. Table V shows result of TreeMap and TOPCOM comparisons on unweighed graph. It is clear that TOPCOM is competitively better in AS cadia, Gnutella09 and Gnutella31 datasets, but TreeMap performs an order of magnitude better for other three datasets. However, when we run the TreeMap for building index it took hours to build the index for some datasets, for example average index building time for Epinion dataset is more than 9 hours, while Gnutella31 takes more than 26 hours. We believe one of the reasons is a bigger graph with higher average degree. To find out the actual cause, we generated synthetic graphs of different sizes (10000-25000) and degrees (0.5-5) and tried to build indexes using TreeMap. In figure 6a the index building time is shown in seconds, after degree 1 all graphs started taking higher time and for bigger graphs the slope of the curve is very large. We compare construction time of TOPCOM for the same set of synthetic graphs shown in figure 6b, and as shown TOPCOM hardly takes few seconds for index construction. Highest time taken by TOPCOM is 44 sec for 25K nodes graph with average degree 5, which is almost thousand times faster compared to TreeMap. From this we can easily conclude that it is difficult for TreeMap to scale for higher degree graphs.

CONCLUSIONS
In this paper we proposed TOPCOM : a unique indexing method to answer distance query for directed real-world graphs. This method uses topological ordering property of DAG and describes a novel method for distance preserving compression of DAG. We compared TOPCOM with IS-Label and found the our method performs better than IS-Label for both weighted DAG and weighted general graph. We strongly believe our method should perform similar or better for unweighed graphs, because we store distance information in label irrespective of weighted/unweighted edges. We do not compare TOPCOM with other recent methods such as HCL [Jin et al. 2012b] and state-ofart 2-Hop [Cohen et al. 2002], because Fu et al. have compared IS-Label with HCL and proved superiority of IS-Label in ]. We also compare TOPCOM with the recent TreeMap method, which performs better for some datasets, however, we show that this method is not scalable for huge graphs with higher degree. We plan to study further to build index for dynamic large graphs that can answer exact distance query in an acceptable time.