# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 4 Experiment  
We showed the experimental results through two aspects. First, we discussed the impact of the threshold, \(d\), on index construction and query answering. Second, we compared the performance of our approach and the recently published approaches, including _kReach_[10; 11] and _ESTI_[12]. Here, _kReach_ was the optimized algorithm using a \(k\)-relaxed partial vertex cover with budget \(b\) = 1000, which is the value suggested by the authors. We did not make a comparison with _BFSI-B_[13] and _HT_[14] due to the fact that they are tailored to _DAG_s and cannot process kHRQs when the input graph contains SCCs. We implemented our algorithms using C++ and compiled them with G++ 7.5.0. For existing algorithms, we obtained the source code of _ESTI_ and _kReach_ from the authors. All experiments were run on a PC with Intel(R) Core(TM) i5-4200M @ 2.5 GHz CPU, 16\(G\) dual-channel memory, and Ubuntu 18.043 Linux OS. Query time denotes the running time of a total of 1,000,000 kHRQs. For algorithms that \(ran\ \geq\ 24\) h or exceeded the memory limit (16 GB), we showed their results as \"-\" in the tables. **Datasets:** Table 3 contains the statistics of eight carefully selected real datasets used in our experiment, which could be divided into two groups. The first group consisted of four sparse graphs, including human, WikiTalk, twitter and web-uk datasets. **Human** ([[https://code.google.com/archive/p/grail/downloads](https://code.google.com/archive/p/grail/downloads)]([https://code.google.com/archive/p/grail/downloads](https://code.google.com/archive/p/grail/downloads)), accessed on 13 March 2021) is a graph which describes the genome and biochemical machinery of E. coli K-12 MG1655, and **WikiTalk** ([[http://snap.stanford.edu/data/index.html](http://snap.stanford.edu/data/index.html)]([http://snap.stanford.edu/data/index.html](http://snap.stanford.edu/data/index.html)), accessed on 13 March 2021) was transformed from communication network wiki-Talk. **Twitter** ([[https://code.google.com/p/ferrari-index/downloads/list](https://code.google.com/p/ferrari-index/downloads/list)]([https://code.google.com/p/ferrari-index/downloads/list](https://code.google.com/p/ferrari-index/downloads/list)), accessed on 13 March 2021) was transformed from a social network obtained from twitter.com (accessed on 13 March 2021), and web-uk ([[https://code.google.com/p/ferrari-index/downloads/list](https://code.google.com/p/ferrari-index/downloads/list)]([https://code.google.com/p/ferrari-index/downloads/list](https://code.google.com/p/ferrari-index/downloads/list)), accessed on 13 March 2021) is a web graph dataset. These datasets are sparse graphs that were used to test the performance when the number of vertices increased. The second group consisted of four dense graphs. BerKStan ([[http://snap.stanford.edu/data/index.html](http://snap.stanford.edu/data/index.html)]([http://snap.stanford.edu/data/index.html](http://snap.stanford.edu/data/index.html)), accessed on 13 March 2021) is a web graph describing the hyperlinks between berkely.edu and stanford.edu. EX6, 3 dtube, and bio are three directed graphs \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **Indexing Construction Time** & **Index Size** & **Query Time** \\ \hline kReach & \(O(\sum_{a\in S}|G_{k}(u)|)\) & \(O\Big{(}|S|^{2}\Big{)}\) & \(O(|V_{D}|+|E_{D}|)\) \\ ESTI & \(O\Big{(}|V|\ \log\Big{(}\hat{a}_{max}^{in}\Big{)}+|E|\Big{)}\) & \(O(|V|+|E|)\) & \(O(|V|+|E|)\) \\ VCRea & \(O(|S|(|V|+|E|)L)\) & \(O(|S|L)\) & \(O\Big{(}\hat{a}_{max}^{in}\hat{a}_{max}^{out}L\Big{)}\) \\ VCRea\({}^{+}\) & \(O(|S|(|V|+|E|)L)\) & \(O(1\,S|L)\) & \(O\big{(}\hat{a}^{2}L\big{)}\) \\ \hline \hline \end{tabular}
\end{table}