Incremental Reachability Index

In the scope of this paper, we assume that the nodes of $G$ are inserted one by one, in a topological order, that is, all nodes are sinks when they are inserted. Thus, each node is identified with its insertion rank (i.e. $V=\{1,\mathrm{\dots }|V|\}$). The topological order further implies that for any arc $u\to v$ and that $u\le v$ for any pair of ancestor/descendant $u{\to }^{\ast }v$.

The optimal chain decomposition of a graph can be computed in polynomial time [8]. However, in the incremental setting we consider here, a chain decomposition must be extended with each new node without editing previous chain assignments. This corresponds to the on-line chain decomposition problem described by Felsner et al. [7, 3]: in this setting, any algorithm yields a chain decomposition of size $\mathrm{\Omega }(w{(G)}^2)$ in the worst case. Felsner also gives an algorithm producing a chain decomposition of size $W\le \frac{1}{2}w(G)(w(G)+1)=O(w{(G)}^2)$; see [3, Theorem 3.5] for a very concise description of this algorithm. The insertion time is dominated by the cost of $W$ reachability queries performed in $G$ (all using the inserted node). Beside the chain decomposition itself, this algorithm maintains a size-$O(W)$ manifest containing the last inserted vertices in each chain (and is only required for node insertions). Note that in our experiments (for graphs generated with our algorithm), we observe a linear dependency between $W$ and $w(G)$, see Figure 6 in appendix.

Used with the incremental chain decomposition by Felsner [7], the chain-based reachability index by Jagadish [9] offers an incremental index with $O(1)$ query time and $O(W)$ memory per node. We propose an improved version of this algorithm based on two anchor strategies, yielding a much lighter index while retaining incrementality. The query time becomes $O(\log n)$ in the most-compressed version and can be reduced to $O(1)$ depending on the desired time/memory trade-off. The theoretical memory upper bound remains $O(W)$ in the worst case.

We run experimental evaluations of our algorithm both on generated and real-life graphs. Compared to Jagadish [9], we obtain similar query times and reduce the index size by a factor close to 10. With these encouraging results, we compare our algorithm against a selection of non-incremental reachability index. We obtain in particular similar query time as our implementation of 2-hop, with competitive index size in real-life graphs and generated graphs of width up to $1.5\sqrt{n}$.

Section 2 presents the chain index obtained by combining Jagadish’s index [9] with Felsner’s online chain decomposition [7]; we then build upon this algorithm in Section 3 to present our anchor-based index. We then describe the set-up for the experimental evaluation in Section 4, and the conclusions in Section 5. Additional detailed results are given in appendix.

Since we rely on the chain decomposition by Felsner [7], we need to store the Chains list in the manifest. Furthermore, for each node $v$, we store:

• $\mathrm{■}$

  the identifier of the chain containing $v$ in $G$;

• $\mathrm{■}$

  the set $\{(C,t_v[C])\mid C\in \text{Chains}\text{ and }{t}_v[C]\ne -1\}$.

The manifest size is thus $W$, and each index entry has size $1+2|t_v|=O(W)$. The sets $t_v$ can be stored either as sorted lists (for optimal storage) or as hashmaps (for optimal look-up). We pick the latter for the theoretical analysis, since the asymptotic memory requirement is identical. In practice, one can store the sorted lists on disk, use them directly for isolated reachability queries, or build a hashmap when queries are expected to be repeated for the same vertex.

In order to test whether $u$ is an ancestor of $v$, we look up the index $C$ of the chain containing $u$, and return true if $u\le t_v[C]$. Using a hashmap for $t_v$, we get constant-time reachability queries.

Upon insertion of node $v$, we first compute the combined top vertices of the parents of $v$, defined as $c{t}_v[C]=\max \{t_p[C]\mid p\to v\}$. With this array we can answer reachability queries for $v$ in constant time. Indeed, for a node $u$ in chain $C$, $u$ is an ancestor of $v$ if $u=v$ or if $u\le c{t}_v[C]$ since any ancestor of $v$ (beside $v$ itself) is an ancestor of some parent $p$ of $v$. We can then assign a chain $C^{\ast }$ to $v$ in $O(W)$ with Felsner’s algorithm [7], and compute $t_v$ as follows: $t_v[C^{\ast }]=v$, and $t_v[C]=c{t}_v[C]$ for $C\ne C^{\ast }$.

The complexity for inserting $v$ is thus dominated by the computation of $c{t}_v$ in $O(W\delta (v))$. Note that for high-degree graphs ($\delta (v)>W$), this complexity can be reduced to $O(W^2+\delta (v))$ by considering only the top-most parent $p$ in each chain.

The plots in Figure 4 show the performances of the algorithms presented here. Each graph is assigned a dimension, defined as $N+100\ast k$. All graphs with the same dimension are grouped into a single point for each algorithm, with the query time as X coordinate and memory as y coordinate. The choice of the dimension allows to simplify the scatter plots, while keeping a good view of upper- and lower-bounds for each algorithms. Indeed, our anchor-based algorithms are mostly dependent on $k$, while other algorithms are mostly dependent on the graph size $N$. The right plot shows all algorithms, and the left plot gives a zoom-in on our anchor-based algorithms. Finally, Table 1 gives numeric results over the largest graphs of the data-set, corresponding to the top-right-most points of the plots.

Overall, each algorithm family behaves rather uniformly. As expected, chain-based approaches give the best (near-constant) query times, with a high memory cost for the original chains-only approach [9]. Algorithm BFL has prohibitive running times, even with up to 1024 semaphores. Considering 2-hop, the degree heuristic indeed reduces significantly the worst-case time and memory.

We choose the following four algorithms for more extensive performance analysis. Our Anchor algorithms with strategy 1 ($D=64$) and strategy 2 ($B=256$) are the two “extreme” algorithms in the memory/time trade-off. We also include the original chain algorithm [9], as well as the 2-hop algorithm with degree heuristic, giving the best performances among literature algorithms on our benchmark.

Figure 5 helps compare these algorithms for each criteria as a function of each graph parameter. As mentioned already, the memory requirements for the original chain algorithm are prohibitive, even for the smallest graph width, however its query and indexing times remain optimal for all dimensions. The memory requirements for our anchor-based heuristics are comparable with those of 2-hop in this favorable setting with bounded graph width, and queries remain an order of magnitude faster. Considering the degree of the graph, it can be seen that it mainly affects the indexing time (since all algorithms need to visit each arc at least once); however, it does not have a significant impact on the index performances.

Figure 7 shows the performances of our Anchor algorithm (with the lowest memory needs, i.e. Strategy 2 with $B=256$) compared with 2-Hop. Unsurprisingly, the worst-case query times appear for 2-hop. Considering memory, there appear to be many very simple graphs (e.g. with isolated nodes or small paths): on such graphs, the anchor algorithm’s memory is dominated by constant-size overheads (chain assignments, anchors, powers, etc.) rather than chain tops themselves, while 2-hop has no such overhead and also maintains very short hub lists. Detailed results are given in Table 2 in appendix.

We can see that strategy 2 (with a large enough value of $B$) has comparable or lower memory needs than 2-hop for all values of $k$ up to $1.5\sqrt{N}$. Compared to the original chain algorithm, we maintain bounded query and indexing times (within a factor 2 of the original), but improve by a factor 10 the memory requirements.

Performance with a real-life dataset indicates that our proof-of-concept algorithm performs similarly to our implementation of 2-hop, within the same order of magnitude.

Clearly, our benchmark does not cover all existing algorithms for the reachability problem, nor does it include the most efficient ones. The generated graphs are also very constrained, in order to precisely see the limits of each algorithm. The overarching goal is to ensure that performances are within the same order of magnitude as standard algorithms, while introducing the incremental feature required in many applications. A more precise benchmark would need to simulate real-life operations such as rollbacks, cache management, concurrent access, etc. where the incremental feature alone can save orders of magnitude in index maintenance. We hope our work can help introduce efficient reachability indexes in real-world applications, instead of a slow DFS, to help them scale up to larger graphs.