## 5 Experiments
\begin{table}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|} \cline{2-9} \multicolumn{1}{c|}{} & \multicolumn{3}{|c|}{BV [3]} & \multicolumn{3}{|c|}{BC [7]} & \multicolumn{3}{|c|}{[PERSON] _et al._[2]} & \multicolumn{3}{|c|}{This Paper} \\ \cline{2-9} \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{\(R=3\)} & \multicolumn{1}{c|}{\(R=\infty\)} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} \\ \cline{2-9} \multicolumn{1}{c|}{} & BFS & \multicolumn{1}{c|}{BFS} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} \\ \hline \multicolumn{1}{|c|}{cnr-2000} & 3.92 & 3.56 & 3.23 & 2.84 & - & 1.99 & 1.87 & 2.64 & 3.33 \\ in-2004 & 3.05 & 2.82 & 2.35 & 2.17 & - & 1.71 & 1.43 & 2.19 & 2.85 \\ eu-2005 & 4.83 & 5.17 & 4.05 & 4.38 & 2.90 & 2.78 & 2.71 & 3.48 & 4.20 \\ indversion (\(R=3\)) performs with comparable speed. However, settling for \(l=4\) our method becomes faster. \begin{table}
\begin{tabular}{|l|c|c|} \cline{2-3} \multicolumn{1}{c|}{} & \multicolumn{2}{|c|}{This Paper} \\ \cline{2-3} \multicolumn{1}{c|}{} & \(l=8\) & \(l=4\) \\ \hline \multicolumn{1}{|c|}{cnr-2000} & 0.86 \(\mu\)s & 0.59 \(\mu\)s \\ in-2004 & 0.95 \(\mu\)s & 0.70 \(\mu\)s \\ eu-2005 & 1.73 \(\mu\)s & 1.20 \(\mu\)s \\ indochina-2004 & 1.55 \(\mu\)s & 1.11 \(\mu\)s \\ uk-2002 & 1.30 \(\mu\)s & 0.95 \(\mu\)s \\ arabic-2005 & 1.81 \(\mu\)s & 1.23 \(\mu\)s \\ \hline \end{tabular}
\end{table} 
Table 10: Average times to test adjacency between pairs of random nodes. \begin{table}
\begin{tabular}{|l|c|c|} \cline{2-3} \multicolumn{1}{c|}{} & \multicolumn{2}{|c|}{BV [3]} & \multicolumn{2}{|c|}{This Paper} \\ \cline{2-3} \multicolumn{1}{c|}{} & \(R=3\) & \(R=\infty\) & \(l=8\) & \(l=4\) \\ \hline \multicolumn{1}{|c|}{cnr-2000} & 1.66 \(\mu\)s & 1.22 ms & 1.40 \(\mu\)s & 0.95 \(\mu\)s \\ in-2004 & 1.89 \(\mu\)s & 0.65 ms & 1.55 \(\mu\)s & 1.13 \(\mu\)s \\ eu-2005 & 2.58 \(\mu\)s & 2.35 ms & 3.16 \(\mu\)s & 2.09 \(\mu\)s \\ indochina-2004 & 2.31 \(\mu\)s & 0.93 ms & 2.42 \(\mu\)s & 1.72 \(\mu\)s \\ uk-2002 & 2.35 \(\mu\)s & 0.20 ms & 2.16 \(\mu\)s & 1.52 \(\mu\)s \\ arabic-2005 & 2.80 \(\mu\)s & 1.15 ms & 3.09 \(\mu\)s & 2.11 \(\mu\)s \\ \hline \end{tabular}
\end{table} 
Table 9: Average times to retrieve the adjacency list of a node. Figure 4: Algorithm to check if the directed link (\(v_{i}\), \(v_{j}\)) exists. By virtue of the underlying BFS, we can implement a fast query to check whether or not a link \((v_{i},v_{j})\) exists. In fact, we know that a node \(v_{i}\) has \(k_{i}\) links that belong to the BFS tree, say, to \(v_{a}\), \(\ldots\), \(v_{a+k_{i}-1}\). We also know that \(v_{i}\) does not have any link with a node \(v_{b}\) where \(b\geq a+k_{i}\), so we need to generate the adjacency list of \(v_{i}\) only if \(j<a\). Figure 4 displays the pseudocode of this query. Table 10 shows average times to test the connectivity of \(2\cdot 10^{7}\) pairs of random nodes. The average time is less than \(60\%\) of the retrieval time. Finally, Figure 5 presents the actual main memory (top) respectively required by BV and our method, and the space-time tradeoff (bottom). As said, we do not compress the offsets. The space requirement of our compression level 8 is 80% of BV at \(R=3\).