Summarizing semantic graphs: a survey <s> Oriented toward schema extraction <s> We present SchemEX, an approach and tool for a stream-based indexing and schema extraction of Linked Open Data (LOD) at web-scale. The schema index provided by SchemEX can be used to locate distributed data sources in the LOD cloud. It serves typical LOD information needs such as finding sources that contain instances of one specific data type, of a given set of data types (so-called type clusters), or of instances in type clusters that are connected by one or more common properties (so-called equivalence classes). The entire process of extracting the schema from triples and constructing an index is designed to have linear runtime complexity. Thus, the schema index can be computed on-the-fly while the triples are crawled and provided as a stream by a linked data spider. To demonstrate the web-scalability of our approach, we have computed a SchemEX index over the Billion Triples Challenge (BTC) dataset 2011 consisting of 2,170 million triples. In addition, we have computed the SchemEX index on a dataset with 11 million triples. We use this smaller dataset for conducting a detailed qualitative analysis. We are capable of locating relevant data sources with recall between 71% and 98% and a precision between 74% and 100% at a window size of 100 K triples observed in the stream and depending on the complexity of the query, i.e. if one wants to find specific data types, type clusters or equivalence classes. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Oriented toward schema extraction <s> The Web has become a huge information space consisting of interlinked datasets, enabling the design of new applications. The meaningful usage of these datasets is a challenge, as it requires some knowledge about their content such as their types and properties. In this paper, we present an automatic approach for schema discovery in RDF(S)/OWL datasets. <s> BIB002
In this subsection, we focus on methods that try to create schema-like structures of the available data sources. One of the challenges when working with Linked Open Data is the lack of a concise schema, or a clear description of the data that can be found in the data source. SchemEX  BIB001 , an indexing and schema extraction tool for the LOD cloud, attempts to solve this problem. Out of an RDF graph, it produces a three-layered index, based on resource types. Each layer groups input data sources of the LOD cloud into nodes, as follows: (i) in the first layer, each node is a single class c from the input, to which the data sources containing triples whose subject is of type c are associated; (ii) in the second layer, each node, now named as an RDF type cluster, is a set of classes C mapped to those data sources having instances whose exact set of types is C; (iii) in the third layer, each node is an equivalence class, where: two nodes u and v from the input belong to the same equivalence class if and only if they have the exact same set of types, they are both subjects of the same data property p, and the objects of that property p belong to the same RDF type cluster. Further, each equivalence class is mapped to all data sources comprising of triples (s, p, o) from an input RDF graph, such that s belongs to the equivalence class of the node. To build the index, a stream-based computation approach is proposed, depicted in Fig. 10 . The restriction to a certain window size of the data stream typically leads to incomplete results, thus the choice of the appropriate window size is an essential parameter for the quality of the extracted index. The specific approach does not consider implicit triples, nor untyped resources. In addition, the resulting index is not a quotient, since in each layer data sources may be mapped to multiple index nodes (while a quotient partitions the graph nodes). Finally, the time complexity of the approach is O (N  *  log N ) or O(M * log M), where N is the number of RDF classes available and M is the number of properties. Toward the same goal of building a compact representation of an RDF graph to be used as a schema, BIB002 proposes an approach to extract a schema-like directed graph, as follows. A density-based clustering algorithm is used on the input RDF graph to identify the summary nodes: each such node, called a (derived) type, corresponds to a set of resources with sufficient structural similarity. Further, each of these types is described by a profile, i.e., a set of (property, probability) pairs of the form ( − → p , α) or ( ← − p , α) meaning that a resource of that type has the outgoing or incoming property p with probability α. These profiles are used to define output schema edges of two kinds: (i) There is a p-labeled edge from a type node T 1 to a type node T 2 , i.e., T 1 p − → T 2 , whenever p is an outgoing property of T 1 's profile and an incoming property of T 2 's profile. (ii) There is an rdfs:subClassOf-labeled edge from a type node T 1 to a type node T 2 , i.e., T 1 rdfs:subClassOf − −−−−−−−− → T 2 , whenever T 1 is found more specific than T 2 by an ascending hierarchical clustering algorithm applied to their profiles. The time complexity of the corresponding algorithm is O (N 2 ) where N is the number of entities in the dataset. The out- Fig. 10 Graph compression technique for SchemEX put directed graph can be seen as a summary describing first, types which correspond to structurally similar resources, and second, how properties relate resources of various types.