# SumMER: Structural Summarization for RDF/S KGs
## 5 Evaluation
### Execution Time  
Next, we evaluate the efficiency of the various components of our system. We present in each case the average time of 10 executions for summarizing the two KGs. All experiments ran on an Intel(R) CPU running at 2.70 GHz with 4 GB memory on Windows 10. **Calculating individual centrality measures. ** The average execution time for identifying the most important nodes on our largest test dataset (DBpedia v3.8) is shown in Figure 9 for the various centrality measures. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & & **10\%** & **15\%** & **20\%** & **25\%** & **30\%** \\ \hline DBpedia & RDFDigest+ & 9/35 & 21/53 & 29/70 & 45/88 & 55/106 \\ \cline{2-7} v3.8 & SumMER & 14/35 & 22/53 & 46/70 & 69/88 & 85/106 \\ \hline \multirow{2}{*}{SWDF} & RDFDigest+ & 9/12 & 9/18 & 17/24 & 20/30 & 27/36 \\ \cline{2-7}  & SumMER & 10/12 & 16/18 & 23/24 & 27/30 & 3/36 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: TP values for SumMER and RDFDigest+ for SWDF and DBpedia v3.8. Figure 8: Coverage for testing on SWDF. Figure 9: The average execution time for calculating the centrality measures on DBpedia v3.8 (ms). As presented, the execution times are grouped into three categories. The ones that compute the shortest paths of all pairs, the ones that need to iterate only on the nodes and the edges of the graph and the ones that need to perform local iterations on the nodes and the edges. The Betweenness, the Bridging Centrality, the Harmonic Centrality and the Radiality belong to the first category. They all calculate the shortest paths between all pairs of nodes in order to assign the proper weights. As such, their execution time is similar. The Betweenness calculates the set of all shortest paths for all schema node pairs and as such it requires more time. The Bridging Centrality uses the Betweenness and as such, it takes almost the same time. In the second category, we have the Hits, PageRank, Degree, and the Ego Centrality. The Degree needs only to iterate over all edges of the graph and use this for the weight calculation for each node. The Ego Centrality requires one more iteration over all nodes and edges of the graph. As such they need only nanoseconds to be calculated for our graphs. In the third category, we find Hits and PageRank, where the weight of the edges is initialized, then the entire graph is crossed node by node, changing the corresponding weights and repeating the whole process. **Using ML to calculate top-k nodes. ** The average execution times for the prediction of the most important nodes in our largest test dataset (DBpedia v3.8), are shown in Figure 10. As shown, running the described machine learning algorithms is rapid fast, as those algorithms usually work with many more samples. More specifically, Linear Regressors (Linear Regression, Bayesian Ridge, and Elastic Net) and Decision Trees are the best performing ones, while Random Forest is the worst performing one. However, even the worst takes on average 0.4 msec to return the results. Those results are in line with the complexity of the corresponding algorithms already presented in Section 4.2. Nevertheless, we can easily identify that the added overhead of the machine learning algorithms is negligible and we omit results for SWDF as the execution times are even smaller. **Linking top-k nodes. ** For linking the top-k schema nodes, according to the complexities of the corresponding algorithms, there is a linear functional relationship between the execution time and input data size for SDISTG and CHINS. The results are shown in Figure 11. HEUM is requires a quadratic time, as it must construct the shortest paths of all pairs. Considering that the number of the selected schema nodes is relatively small SDISTG and CHINS have a better execution time. HEUM grows linearly to the number of nodes and performs worst. MST depends on the size of the graph and performs better than SDISTG and CHINS which are highly dependent on the number of the top-k schema nodes and the shortest paths between them.