# SumMER: Structural Summarization for RDF/S KGs
## 4 Constructing Schema Summaries
### Linking Selected Schema Nodes
We use the following top-three well-known and good performing methods SDISTG, CHINS and HEUM [24]. These approximations have a worst-case bound of 2, i.e., \(Z_{T}\)/Z\({}_{opt}\leq 2\cdot(1-l/|Q|)\), where \(Z_{T}\) and \(Z_{opt}\) denote the objective function values of a feasible solution and an optimal solution respectively, \(Q\) the set of terminals and \(l\) a constant [25]. SDISTG (Shortest distance graph)  
1. Construct a complete graph \(G^{\prime}\) for the node set \(Q\) (set of terminal nodes) with each edge having the weight of a shortest path between the corresponding nodes in \(G\). 2. Construct a minimum spanning tree \(T^{\prime}\) of \(G^{\prime}\). 3. Replace each edge of the tree \(T^{\prime}\) by its corresponding shortest path in \(G\). CHINS (Cheapest insertion)  
1. Start with a partial solution \(T=(w,0)\) consisting of a single terminal node \(w\). 2. While \(T\) does not contain all terminal nodes do
3. Find the nearest nodes \(u*\in V_{t}\) and \(p*\) being a terminal node not in \(V_{t}\). HEUM (Heuristic measure)  
1. Start with a partial solution \(T=(Q,0)\) consisting of \(Q\) singleton components (terminal nodes). 2. While \(T\) is not connected do choose a node \(u\) using a heuristic function \(F\) and unite the two components of \(T\) which are nearest to \(u\) by combining them with \(u\) via shortest paths (the nodes and edges of these paths are added to \(T\)). 3. Up to now the most promising way is to choose \(F\) according to: \(min_{i}\leq t\leq\sigma\Big{\{}\frac{1}{t}\ \sum_{i=0}^{t}d(u,\ T_{i})\Big{\}}\) where \(T_{0,\ldots}\ T_{\sigma}\) are the components of \(T\) such that \(d(u,T_{i})\leq d(u,T_{i})\)\(\forall i,j\in\sigma,i<j\). Besides these approximations, many heuristics can be employed to improve even more the corresponding algorithms. The most promising ones are the I-MST+P and the TRAFO [24]. I-MST+P is a pruning routine that ensures that all leaves are terminal nodes whereas TRAFO transforms a feasible solution to another one trying to overcome the deficiency of bad local optima by allowing the temporary deterioration of the actual solutions. In this paper we use only the I-MST+P since TRAFO requires considerably more time to run and the improvements are insignificant--due to the sparsity of the examined ontologies. **I-MST + P (Improvement procedure with MST + P)**  
1. Let \(T=(V_{t},E_{t})\) be a feasible solution of the GSTP. The subgraph of \(G\) induced by \(V_{t}\) will be defined as \(G_{t}\). 2. Construct a minimum spanning tree \(T=(Vt^{\prime},Et^{\prime})\) of \(G_{t}\). 3. While there exists a leaf of \(T^{\prime}\) being a terminal do delete that leaf and its incident edge. **Complexities** Using a Breadth-first search (BFS) requires \(O(V+E)\) time (where \(E\) is \(O(V)\)) to find the shortest paths from a source vertex \(v\) to all other vertices in the graph. All-pairs shortest paths for unweighted undirected graphs can be computed in \(O(V\ (V+E))\) time by running the BFS algorithm for each node of the graph. The complexity of SDISTG, CHINS and HEUM differs, due to the usage of different heuristics. Table 4 provides the worsts case complexity of those algorithms for weighted and unweighted graphs.