# SumMER: Structural Summarization for RDF/S KGs
## 5 Evaluation  
Next, we present in details the datasets used for our experimental evaluation and the methodology followed. **Datasets. ** As we shall show in the sequel, we exploit query logs for evaluating the quality of the summaries constructed. As such we can only use KGs where query logs are available. Three real world KG with such query logs available are DBpedia v3.8 and v3.9, and the Semantic Web Dog Food (SWDF) which we subsequently used. We could not identify other KGs with big query logs available online. Finally, although WikiData has such a query log available its huge size (more than 1.4 billion statements) does not allow schema extraction that would be used then for summarization and as such was not used in this paper. Nevertheless, we argue that three real world datasets with thousands of user queries are enough for evaluating our approach. DBpedia v3.8 contains 315 classes, 1323 properties and more than 2.3 M instances, and DBpedia v3.9, contains 533 classes, 1805 properties and more than 3.3 M instances. The dataset occupies 103 GB of storage for v3.8 and 114 GB for v3.9. We had also available a query log with 50 K user queries for v3.8 and 110 K user queries for v3.9, as provided by the DBpedia SPARQL end-point. The v3.9 of DBpedia does not contain all samples of v3.8 since it was a major update, with many updates/deletions in the old triples, and the introduction of new ones. Although the two versions of the DBpedia are not the most recent ones, they have already proved their value in various benchmarks and experiments (e.g., [26]) and give us an interesting dataset to experiment with, especially because we have also thousands of user queries available. In addition, we used the Semantic Web Dog Food (SWDF) [27]. SWDF is a KG containing information about semantic web conferences. Its schema contains 120 classes, 72 properties, 304,583 triples, 36,879 distinct subjects, 185 distinct predicates, and 95,501 distinct objects. The dataset occupies 50 MB of storage. For this dataset, we exploited also a query log containing 2.5 K user queries, provided by LSQ. Table 5 presents the characteristics of the KGs used for our evaluation. **Constructing a \"golden standard\". ** For constructing a \"golden standard\" to be used for the evaluation of the selection of the top-k nodes, we exploit the query logs available for the three KGs. More specifically, based on these query logs we calculate the frequencies of the schema nodes in the user queries. For calculating those frequencies, we are not considering only the direct appearances of the schema nodes in the queries but also include the appearance of the instances that they belong to those schema nodes. Using this frequency, we argue that the most important ones are the ones more frequently queried, a reasonable assumption as the more user queries involve a specific schema node the more important this node should be. Certainly, if thousands of user queries were available for all KGs then we could construct an ideal summary for all of them, based exactly on the schema nodes that are \begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Weighted Graph** & **Un-Weighted Graph** \\ \hline MST & \(O(E\cdot logV)\) & \(O(\mid V+E\mid)\) \\ SDISTG & \(O(Q\cdot\mid V\;logV\mid)\) & \(O(Q\cdot\mid V+E\mid)\) \\ CHINS & \(O(Q\cdot\mid V\;logV\mid)\) & \(O(Q\cdot\mid V+E\mid)\) \\ HEUM & \(O(V\cdot\mid V\;logV\mid)\) & \(O(V\cdot\mid V+E\mid)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Worst-case complexities for linking the most important nodes in a graph. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Classes** & **Properties** & **User Queries** & **Storage** \\ \hline DBpedia v3.8 & 315 & 1323 & 50 K & 103 GB \\ DBpedia v3.9 & 497 & 1805 & 110 K & 114 GB \\ SWDF & 120 & 72 & 2.5 K & 50 GB \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Characteristics of the KGs used for experimental evaluation. most frequently queried.