Summarizing semantic graphs: a survey <s> Mining rules <s> We are given a large database of customer transactions. Each transaction consists of items purchased by a customer in a visit. We present an efficient algorithm that generates all significant association rules between items in the database. The algorithm incorporates buffer management and novel estimation and pruning techniques. We also present results of applying this algorithm to sales data obtained from a large retailing company, which shows the effectiveness of the algorithm. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Mining rules <s> Linked data has experienced accelerated growth in recent years. With the continuing proliferation of structured data, demand for RDF compression is becoming increasingly important. In this study, we introduce a novel lossless compression technique for RDF datasets, called Rule Based compression (RB compression) that compresses datasets by generating a set of new logical rules from the dataset and removing triples that can be inferred from these rules. We employ existing frequent pattern mining algorithms for generating new logical rules. Unlike other compression techniques, our approach not only takes advantage of syntactic verbosity and data redundancy but also utilizes intraand inter-property associations in the RDF graph. Depending on the nature of the dataset, our system is able to prune more than 50% of the original triples without affecting data integrity. <s> BIB002 </s> Summarizing semantic graphs: a survey <s> Mining rules <s> Linked data has experienced accelerated growth in recent years. With the continuing proliferation of structured data, demand for RDF compression is becoming increasingly important. In this study, we introduce a novel lossless compression technique for RDF datasets, called Rule Based Compression (RB Compression) that compresses datasets by generating a set of new logical rules from the dataset and removing triples that can be inferred from these rules. Unlike other compression techniques, our approach not only takes advantage of syntactic verbosity and data redundancy but also utilizes semantic associations present in the RDF graph. Depending on the nature of the dataset, our system is able to prune more than 50% of the original triples without affecting data integrity. <s> BIB003 </s> Summarizing semantic graphs: a survey <s> Mining rules <s> The Linked Open Data (LOD) cloud brings together information described in RDF and stored on the web in (possibly distributed) RDF Knowledge Bases (KBs). The data in these KBs are not necessarily described by a known schema and many times it is extremely time consuming to query all the interlinked KBs in order to acquire the necessary information. To tackle this problem, we propose a method of summarizing large RDF KBs using approximate RDF graph patterns and calculating the number of instances covered by each pattern. Then we transform the patterns to an RDF schema that describes the contents of the KB. Thus we can then query the RDF graph summary to identify whether the necessary information is present and if so its size, before deciding to include it in a federated query result. <s> BIB004
Methods described here use rule mining techniques in order to extract rules for summarizing the RDF graph. A common limitation of such methods is that, by design, the summary is not an RDF graph, thus it cannot be exploited using the common set of RDF tools (e.g., SPARQL querying, reasoning etc.) Joshi et al. BIB002 BIB003 propose compressing the RDF datasets removing triples that can be inferred using logical and inference rules. Thus, graph decompression infers such triples again, to retrieve the original graph. This approach, which is depicted in Fig. 12 , generates, from a given RDF graph G, an active graph G A containing the triples that adhere to certain logical rules, and a dormant graph G D , which contains the set of triples of the original graph which none of the identified rule can infer. This leads to viewing an RDF graph G as being R(G A )∪G D , where R represents the set of rules to be applied to the active graph G A , Fig. 11 Zneika et al. BIB004 approach Fig. 12 Graph compression technique for Joshi et al. BIB003 while (G A , G D ) together represent the compressed graph. An association rule mining algorithm is employed to automatically identify the set of logical rules. The authors leverage the Apriori BIB001 or FP-Growth [31] frequent pattern-mining algorithms, to identify sets of association rules. First, for each property p, a "transaction" (in classical data mining terms) is a list of objects which are the values of property p for a given subject. Each rule thus is defined by: a property p, an object item k, and a frequent itemset x associated with k. One sample rule is: , stating that the subjects that carry the value k for property p, carry also the values u i for the same property. Based on such a rule, the triple (x, p, k) is encoded in the summary, while the inferred triples n i=1 (x, p, v i ) can be removed. Further, the authors extend the approach to use as a transaction, the lists of all ( p, o) pairs for a given subject, and similarly mine for frequent itemsets in this context, each of which will be interpreted as a logical compression rule. The specific approach works well when the original graph contains many different nodes, sharing many same "neighbors", but it is not effective when the contrary is true. To deal with the last issue, the authors of  extend the previous approach by exploiting a graph pattern with two variables instead of one, which makes it applicable to more generic graph structures, reducing the size of the summary graph. This is because the number of triples in the summary graph is halved (a rule can now represent more triples). The time complexity of the two previous approaches is where M is the total number of triples, R is the number of the generated logical rules, N p and N s are respectively the number of distinct properties and subjects/resources in the graph, and O v is the average number of different objects/values that are assigned to a property p (we should remember that we are looking for common neighbors and thus for common values for the properties in the object/value part, (s, p, o) or (s, p, v) in the triple notation); thus, the lower the average number of different values the more common the neighborhood and the better the algorithm behaves as already stated earlier (Fig. 13) .