Summarizing semantic graphs: a survey <s> Other summarization methods <s> It has often been asserted that since hierarchical clustering algorithms require pairwise interobject proximities, the complexity of these clustering procedures is at least O(N 2 ). Recent work has disproved this by incorporating efficient nearest neighbour searching algorithms into the clustering algorithms. A general framework for hierarchical, agglomerative clustering algorithms is discussed here, which opens up the prospect of much improvement on current, widely-used algorithms. This 'progress report' details new algorithmic approaches in this area, and reviews recent results. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> The popularity of the Web and Internet commerce provides many extremely large datasets from which information can be gleaned by data mining. This book focuses on practical algorithms that have been used to solve key problems in data mining and which can be used on even the largest datasets. It begins with a discussion of the map-reduce framework, an important tool for parallelizing algorithms automatically. The authors explain the tricks of locality-sensitive hashing and stream processing algorithms for mining data that arrives too fast for exhaustive processing. The PageRank idea and related tricks for organizing the Web are covered next. Other chapters cover the problems of finding frequent itemsets and clustering. The final chapters cover two applications: recommendation systems and Web advertising, each vital in e-commerce. Written by two authorities in database and Web technologies, this book is essential reading for students and practitioners alike. <s> BIB002 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> RDF is the common data model to publish structured data on the Web. RDF data sets are given as subject-predicateobject triples and typically are represented as directed edgelabeled graphs. To make the information represented by such graphs comprehensible, RDF-schema (RDFS) provides concepts to dene a class-structure as part of the given RDFgraph and thus supports a more abstract view on the data set. In this paper we follow a dierent approach and propose to make an RDF graph more comprehensible by reducing its size by partitioning to discover subgraphs which are similar with respect to their structure. The methods applied to derive a partition are based on bisimulation and agglomerative clustering. We demonstrate the usefulness of the approach by applying it on several synthetic and one real world RDF datasets. <s> BIB003 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> While much work has focused on continuously publishing Linked Open Data, little work considers how to help consumers to better understand existing datasets. ABSTAT framework aims at providing a better understanding of big and complex datasets by extracting summaries of linked data sets based on an ontology-driven data abstraction model. Our ABSTAT framework takes as input a data set and an ontology and returns an ontology-driven data summary as output. The summary is exported into RDF and then made accessible through a SPARQL endpoint and a web interface to support the navigation. <s> BIB004 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> The Resource Description Framework (RDF) is a graph-based data model promoted by the W3C as the standard for Semantic Web applications. Its associated query language is SPARQL. RDF graphs are often large and varied, produced in a variety of contexts, e.g., scientific applications, social or online media, government data etc. They are heterogeneous, i.e., resources described in an RDF graph may have very different sets of properties. An RDF resource may have: no types, one or several types (which may or may not be related to each other). RDF Schema (RDFS) information may optionally be attached to an RDF graph, to enhance the description of its resources. Such statements also entail that in an RDF graph, some data is implicit. According to the W3C RDF and SPARQL specification, the semantics of an RDF graph comprises both its explicit and implicit data; in particular, SPARQL query answers must be computed reflecting both the explicit and implicit data. These features make RDF graphs complex, both structurally and conceptually. It is intrinsically hard to get familiar with a new RDF dataset, especially if an RDF schema is sparse or not available at all. <s> BIB005 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> We motivate and describe techniques that allow to detect an "emergent" relational schema from RDF data. We show that on a wide variety of datasets, the found structure explains well over 90% of the RDF triples. Further, we also describe technical solutions to the semantic challenge to give short names that humans find logical to these emergent tables, columns and relationships between tables. Our techniques can be exploited in many ways, e.g., to improve the efficiency of SPARQL systems, or to use existing SQL-based applications on top of any RDF dataset using a RDBMS. <s> BIB006 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> An increasing number of research and industrial initiatives have focused on publishing Linked Open Data, but little attention has been provided to help consumers to better understand existing data sets. In this paper we discuss how an ontology-driven data abstraction model supports the extraction and the representation of summaries of linked data sets. The proposed summarization model is the backbone of the ABSTAT framework, that aims at helping users understanding big and complex linked data sets. The proposed model produces a summary that is correct and complete with respect to the assertions of the data set and whose size scales well with respect to the ontology and data size. Our framework is evaluated by showing that it is capable of unveiling information that is not explicitly represented in underspecified ontologies and that is valuable to users, e.g., helping them in the formulation of SPARQL queries. <s> BIB007 </s> Summarizing semantic graphs: a survey <s> Other summarization methods <s> Estimating the cardinality (i.e., the number of answers) of conjunctive queries is extensively used in data management systems. This problem is particularly difficult in RDF systems since queries over RDF data are navigational and thus tend to involve many joins. In this paper we present a new technique for estimating the cardinality of conjunctive queries in RDF. We use a summary of an RDF graph as a synopsis that we interpret using a possible world semantics. We formalise the estimation problem as computing the expectation of query cardinality over all RDF graphs represented by the summary, and we present a closed-form formula for computing the expectation of arbitrary queries. We also discuss approaches to RDF graph summarisation. Finally, we show empirically that our cardinality technique is more accurate and more consistent, often by orders of magnitude, than several state-of-the-art approaches. <s> BIB008
In this section, we present approaches that combine methods from the structural, statistical and pattern-mining categories in order to get better results. In addition, there are methods going beyond RDF graph summaries, for example summarizing DL ontologies. An overview of the works in this category is shown in Table 7 . Alzogbi and Lausen BIB003 proposes a hybrid structural summarization technique for RDF graphs, the purpose of which is to reduce their size while retaining their structure as much as possible. It consists of a graph quotient step followed by a graph clustering step. The first one adopts bounded forward bisimulation, as according to the authors, previous studies showed that, in general, unbounded bisimulation is not amenable to significant graph size reduction. This BIB001 , where N is the number of nodes of the aforementioned intermediate graph. This technique produces a standard graph out of an RDF one, without user input, which summarizes the whole input graph (nodes and edges). However, it does not perform particular treatment on RDF Schema triples, hence does not capture the implicit triples they entail, unless input RDF graph are saturated prior to summarization. ABSTAT BIB004 BIB007 BIB007 ] is a summarization method for RDF graphs (and OWL KBs), which aims at reflecting how class instances are related through properties. A summary is not a graph but a set of abstract knowledge patterns (AKPs) of the form (c 1 , p, c 2 ) representing the (s, p, o) graph triples with c 1 (resp. c 2 ) one of the most specific types of s (resp. o); there may have several such c 1 , c 2 pairs for a given property p. An ABSTAT summary is built in polynomial time in the size of the input RDF graph, by first computing for every value presents in the graph all its types, from which are pruned out the redundant ones. Then, for each property assertion (s, p, o), an AKP (c 1 , p, c 2 ) is built if c 1 (resp. c 2 ) is a most specific type for value s (resp. o). ABSTAT is available online. BIB005 Stefanoni et al. BIB008 proposes to use structural summaries of RDF graphs for estimating the cardinality of conjunctive queries. The authors build a graph summary of an RDF graph by grouping together nodes having exactly the same set of types, same outgoing and same incoming properties. A summary edge is labeled with the number of edges of G that have been collapsed due to merging (thus, the summary is not a quotient). The classes (appearing in the object position of type triples), and properties appearing in the property position are preserved, i.e., they are represented in the summary by themselves. However, properties appearing in the subject/object positions are not preserved; moreover, possible RDFS properties are summarized just as any other data property; thus, the schema is not conserved either. These summaries, built in time linear in M, the number of graph edges, may be too large; therefore, the authors propose an algorithm to reduce the summary to a target size specified by the user, by merging nodes having similar incoming and outgoing properties. The similarity is determined by a Jaccard index, approximated by MinHashing BIB002 ; to efficiently compute the similarity between all pairs of summary nodes, locality-sensitive hashing BIB002 is used. The approach gets as input only instances and optional parameters for summary refinement and returns an instance graph. This graph is fur- BIB005 http://abstat.disco.unimib.it/search. ther used to enable the estimation of the cardinality for easing query answering and evaluation. Pham et al. BIB006 combines structural non-quotient and statistical methods to create a summary of an RDF graph, which they call relational schema. The initial summary is generated, in linear time of the RDF graph size (average complexity), by computing sets of properties joining on the subject, the so-called characteristic sets, denoted C S. A summary node is created for each C S, thus representing nodes of G having the same outgoing properties. An edge exists between two summary nodes, labeled by a property p, if there exist two G nodes in their respective extents, such that there exists an edge labeled by p in G between the two G nodes. This structural aspect therefore considers only the instance component of an RDF graph. In the second step, a short human-friendly label is computed for summary nodes and edges, by relying on type triples, or in their absence, on ontology information. To reduce the summary size, summary nodes are subsequently merged. In semantic merging, two summary nodes can be merged in two ways: (i) if they have the same label, taken from an ontology, or (ii) if their labels, originating from different ontologies, have a common superclass, and the generality score of this superclass is lower than a certain threshold. The generality score of an ontology class v is computed as the ratio between the number of instances of v's subclasses and the total number of instances covered by the ontology to which v belongs. Moreover, the two ways in which two summary nodes can be merged in structural merging are as follows: (i) if they both have an incoming edge with the same property, from another summary node, or (ii) if the properties in their respective C Ss have the TF/IDF similarity score higher than a given threshold. The merging order of the nodes, affects the resulting summary. The summary is modeled relationally: a table is created per summary node, with a column for each property in the C S represented by the summary node; the relationships between the nodes are stored as foreign keys. The chosen relational model proves challenging for storing the possibly highly heterogeneous graph structure, inherent to RDF graphs, and it drives the modifications to the summary. First, the C S of each summary node may be a result of merging multiple summary nodes and thus their C Ss. Therefore, a G node in the extent of a summary node may not have a value for each property in the C S of the summary node, and will have a NULL value in the table for each such property. Properties having few non-NULL values are deleted. Second, a single property in RDF may have multiple literal values, possibly of different types. In such cases, Pham et al. BIB006 chooses to add a column for each distinct literal value type per property, which other than incurring space costs, may lead to more NULL values. Therefore, for each literal value type below the infrequency threshold, all triples are moved to a separate single PSO table. Finally, infrequent edges are deleted from the summary, while a summary node