# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 4 Experimentation
In fact, despite the super-cubic worst-case time per update, queue-2 hc is always much faster than fs-2 hc in our experiments, up to several orders of magnitude faster. Moreover, it is also faster than bidir-2 hc, on average. Of particular interest are the improvements observed in weighted instances, where bidir-2 hc is not particularly effective and slow enough to be close to fs-2 hc (see instances nld or lux). More specifically, queue-2 hc achieves superior performance with respect to bidir-2 hc update times, up to several orders of magnitude smaller update times (see, e.g., baa or biolinstances). The only exception is graph erd, where the two solutions behave similarly and both exhibit extremely low update times, compared to the time spent by fs-2 hc. This might be due to the fact that a small number of operations suffice to update the labeling in this instance (as the graph is quite dense). Hence, the performance of the algorithm is very low, and the performance of the algorithm is very low. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{5}{c}{**Average Update Time per Graph Mod (s)**} \\ \cline{2-7}  & \multicolumn{2}{c}{**fs-2 hc**} & \multicolumn{2}{c}{**bidir-2 hc**} & \multicolumn{2}{c}{**queue–2 hc**} \\ \cline{2-7}  & **parallel** & **mean** & **median** & **mean** & **median** & **mean** & **median** \\ \hline nld & o & \(7.73\times 10^{2}\) & \(7.76\times 10^{2}\) & \(1.55\times 10^{2}\) & \(1.81\times 10^{2}\) & \(\mathbf{3.06\times 10^{1}}\) & \(\mathbf{7.22\times 10^{0}}\) \\ \hline ytb & o & \(6.94\times 10^{2}\) & \(6.94\times 10^{2}\) & \(1.43\times 10^{2}\) & \(1.57\times 10^{2}\) & \(\mathbf{1.58\times 10^{1}}\) & \(\mathbf{7.19\times 10^{0}}\) \\ \hline wtk & o & \(7.48\times 10^{2}\) & \(7.48\times 10^{2}\) & \(3.61\times 10^{1}\) & \(2.84\times 10^{1}\) & \(\mathbf{2.14\times 10^{1}}\) & \(\mathbf{7.60\times 10^{0}}\) \\ \hline bio & o & \(3.05\times 10^{3}\) & \(3.05\times 10^{3}\) & \(1.60\times 10^{2}\) & \(5.28\times 10^{-4}\) & \(\mathbf{7.36\times 10^{-1}}\) & \(\mathbf{1.59\times 10^{-4}}\) \\ \hline ski & o & \(2.21\times 10^{5}\) & \(2.21\times 10^{5}\) & \(3.67\times 10^{2}\) & \(4.01\times 10^{2}\) & \(\mathbf{1.23\times 10^{2}}\) & \(\mathbf{3.02\times 10^{1}}\) \\ \hline dbp & o & \(2.44\times 10^{3}\) & \(2.44\times 10^{3}\) & \(7.65\times 10^{1}\) & \(6.18\times 10^{1}\) & \(\mathbf{3.19\times 10^{0}}\) & \(\mathbf{1.56\times 10^{0}}\) \\ \hline erd & o & \(9.48\times 10^{3}\) & \(9.47\times 10^{3}\) & \(\mathbf{1.83\times 10^{-4}}\) & \(\mathbf{1.02\times 10^{-4}}\) & \(5.08\times 10^{-4}\) & \(5.36\times 10^{-4}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: _Cont._  
Figure 7: Running times of fs–2 hc, bidir–2 hc and queue–2 hc on some of the considered inputs. The y-axis is log-scaled to magnify the differences. both solutions are very effective, likely close to an optimal behavior, and the difference is just induced by the determination of the cover graphs. For the sake of fairness, similar behavior is observed in instance ntr, where however queue-2 hc is slightly faster. Thus, on the whole, the performance of queue-2 hc is much closer to that of the very efficient resume-2 hc for incremental updates [8], which is considered suited to be applied to mine distances from massive time-evolving graphs in real-time contexts [27]. This suggests queue-2 hc as well can be considered a reasonable solution for real-time contexts, and that in any case should the preferred option to be adopted in time-evolving scenarios when decremental graph operations must be handled.