# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 4 Experimentation
Dispersion of (some of) the samples is shown through the scatterplots of Figure 7 where we report all observed values of running time for a meaningful subset of the tested inputs. Please note that we omit the measures of average labeling size and average query times, since they are essentially identical for the three computed labelings (that recomputed from scratch and the two obtained via dynamic algorithms). This is expected by the theoretical results, since both the dynamic algorithms and fs-2 hc produce minimal labelings (small, negligible variations are observed due to ties in the vertex ordering, which are broken arbitrarily). Notice also that our choice of considering randomly selected updates is dictated by the fact that unfortunately, datasets containing real-world graphs with real-world sequences of decremental updates are not so easy to find in publicly available repositories. However, we employed quite large sequences of updates and this is considered rather effective in capturing the typical performance of this kind of algorithms, as well documented in the literature [42; 43]. Clearly, the larger the size of the sequences, the better is with respect to variance in the observed results. To the purpose, in our case, the value of k is selected so to obtained observed average running times that are quite stable between different runs considering different sequences. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{3}{*}{**Dataset**} & \multicolumn{6}{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 CAI & \(\circ\) & \(4.89\times 10^{-1}\) & \(4.75\times 10^{-1}\) & \(2.14\times 10^{-1}\) & \(2.46\times 10^{-1}\) & \(\mathbf{3.77\times 10^{-2}}\) & \(\mathbf{4.18\times 10^{-2}}\) \\ \hline LUX & \(\circ\) & \(4.99\times 10^{0}\) & \(4.99\times 10^{0}\) & \(9.46\times 10^{-1}\) & \(1.05\times 10^{0}\) & \(\mathbf{2.24\times 10^{-1}}\) & \(\mathbf{9.36\times 10^{-2}}\) \\ \hline GNU & \(\circ\) & \(7.83\times 10^{1}\) & \(7.84\times 10^{1}\) & \(1.30\times 10^{1}\) & \(7.82\times 10^{0}\) & \(\mathbf{4.64\times 10^{0}}\) & \(\mathbf{1.43\times 10^{-1}}\) \\ \hline bKT & \(\bullet\) & \(1.23\times 10^{1}\) & \(1.23\times 10^{1}\) & \(2.28\times 10^{0}\) & \(3.06\times 10^{0}\) & \(\mathbf{3.90\times 10^{-1}}\) & \(\mathbf{2.68\times 10^{-1}}\) \\ \hline efZ & \(\circ\) & \(3.97\times 10^{2}\) & \(3.96\times 10^{2}\) & \(4.83\times 10^{1}\) & \(3.65\times 10^{1}\) & \(\mathbf{3.30\times 10^{1}}\) & \(\mathbf{1.58\times 10^{0}}\) \\ \hline eUA & \(\bullet\) & \(1.25\times 10^{1}\) & \(1.25\times 10^{1}\) & \(1.18\times 10^{0}\) & \(1.56\times 10^{0}\) & \(\mathbf{1.51\times 10^{-1}}\) & \(\mathbf{9.34\times 10^{-2}}\) \\ \hline ePN & \(\bullet\) & \(8.28\times 10^{1}\) & \(8.28\times 10^{1}\) & \(7.67\times 10^{0}\) & \(9.30\times 10^{0}\) & \(\mathbf{3.34\times 10^{0}}\) & \(\mathbf{5.69\times 10^{-1}}\) \\ \hline baa & \(\circ\) & \(1.56\times 10^{2}\) & \(1.56\times 10^{2}\) & \(9.42\times 10^{1}\) & \(1.28\times 10^{2}\) & \(\mathbf{4.11\times 10^{0}}\) & \(\mathbf{3.27\times 10^{0}}\) \\ \hline ntr & \(\bullet\) & \(1.23\times 10^{2}\) & \(1.23\times 10^{2}\) & \(1.37\times 10^{0}\) & \(1.93\times 10^{0}\) & \(\mathbf{1.33\times 10^{0}}\) & \(\mathbf{5.16\times 10^{-1}}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Experimental results: average update time of queue-2 hc against that of bidir-2 hc and fs-2 hc. For each network, we report both mean and median values. The column named parallel indicates whether fs-2 hc is accelerated by executing part of its code in parallel among the cores (for unweighted instances [8], \(\bullet\) = true, \(\circ\) = false). Analysis.Our experiments' main outcomes are essentially two. First and foremost, we observe that queue-2 hc worst-case analysis deviates from the performance in practice.