G. , T. Bsbm, L. Data, . Benchmark, and . Figure, Summarization times (s) and their scale-up with the input size, for various RDF datasets. maries to be mined instead of the original graph for better performance, with guaranteed bounds on the information loss. Graph compression with bounded " error " (number of edges to be added as " corrections " after decompression, to retrieve the original graph) is studied in [26, 18] Quantitative summarization, where nodes and edges are summarized by their counts, is the focus of [22]. [23] surveys many other quantitative, mining-oriented graph sampling and summarization methods. RDF summarization [10, 30, 31] study bisimulation-based RDF quotient summaries, in particular providing efficient parallel summarization algorithms [10] and showing they are representative for data-only queries [30]. However, these summaries ignore the special role type and schema triples play in RDF, and therefore cannot guarantee representativeness for the implicit data and type-aware queries. We have included bisimulation-based RDF summaries in our framework, and showed they admit our shortcut

C. Bizer, A. Schultz-cebiri´ccebiri´c, F. Goasdoué, and I. Manolescu, The Berlin SPARQL Benchmark Query-oriented summarization of RDF graphs, BICOD, 2015. [4] ?. ? Cebiri´cCebiri´c, F. Goasdoué, and I. Manolescu. Query-oriented summarization of RDF graphs, pp.1-24, 2009.

F. Cebiri´ccebiri´c, I. Goasdoué, ?. Manolescu, F. Cebiri´ccebiri´c, I. Goasdoué et al., Efficient representative summarization of RDF graphs Query-Oriented Summarization of RDF Graphs, PVLDB, vol.8, issue.12, 2015.

C. Chen, C. X. Lin, M. Fredrikson, M. Christodorescu, X. Yan et al., Mining graph patterns efficiently via randomized summaries, Proceedings of the VLDB Endowment, vol.2, issue.1, 2009.
DOI : 10.14778/1687627.1687711

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.301.687

C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu, Graph OLAP: Towards Online Analytical Processing on Graphs, 2008 Eighth IEEE International Conference on Data Mining, 2008.
DOI : 10.1109/ICDM.2008.30

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.3646

Q. Chen, A. Lim, and K. W. Ong, D(k)-index, Proceedings of the 2003 ACM SIGMOD international conference on on Management of data , SIGMOD '03, 2003.
DOI : 10.1145/872757.872776

M. P. Consens, V. Fionda, S. Khatchadourian, and G. Pirrò, S+EPPs, Proceedings of the VLDB Endowment, vol.8, issue.12, p.2015
DOI : 10.14778/2824032.2824128

M. P. Consens, R. J. Miller, F. Rizzolo, and A. A. Vaisman, Exploring XML web collections with DescribeX, ACM Transactions on the Web, vol.4, issue.3, 2010.
DOI : 10.1145/1806916.1806920

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.296.4331

W. Fan, J. Li, X. Wang, Y. Wu, R. Goldman et al., Query preserving graph compression Dataguides: Enabling query formulation and optimization in semistructured databases, SIGMOD, 2012. [13] VLDB, 1997.

Y. Guo, Z. Pan, and J. Heflin, LUBM: A benchmark for OWL knowledge base systems, Web Semantics: Science, Services and Agents on the World Wide Web, vol.3, issue.2-3, 2005.
DOI : 10.1016/j.websem.2005.06.005

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.406.3391

S. Gurajada, S. Seufert, I. Miliaraki, and M. Theobald, Using Graph Summarization for Join-Ahead Pruning in a Distributed RDF Engine, Proceedings of Semantic Web Information Management on Semantic Web Information Management, SWIM'14, 2014.
DOI : 10.1145/2630602.2630610

M. R. Henzinger, T. A. Henzinger, and P. W. Kopke, Computing simulations on finite and infinite graphs, Proceedings of IEEE 36th Annual Foundations of Computer Science, 1995.
DOI : 10.1109/SFCS.1995.492576

URL : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.3591&rep=rep1&type=pdf

R. Kaushik, P. Bohannon, J. F. Naughton, and H. F. Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data , SIGMOD '02, 2002.
DOI : 10.1145/564691.564707

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.8757

K. Khan, W. Nawaz, and Y. Lee, Set-based approximate approach for lossless graph summarization, Computing, vol.31, issue.4, pp.1185-1207, 2015.
DOI : 10.1007/s00607-015-0454-9

S. Khatchadourian and M. P. Consens, ExpLOD: Summary-Based Exploration of Interlinking and RDF Usage in the Linked Open Data Cloud, ESWC, 2010.
DOI : 10.1007/978-3-642-13489-0_19

S. Khatchadourian and M. P. Consens, Constructing Bisimulation Summaries on a Multi-Core Graph Processing Framework, Proceedings of the GRADES'15 on, GRADES'15, 2015.
DOI : 10.1145/2764947.2764955

W. Le, F. Li, A. Kementsietsidis, and S. Duan, Scalable Keyword Search on Large RDF Data, IEEE Transactions on Knowledge and Data Engineering, vol.26, issue.11, p.2014
DOI : 10.1109/TKDE.2014.2302294

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.639.314

K. Lefevre and E. Terzi, GraSS: Graph Structure Summarization, SDM, 2010.
DOI : 10.1137/1.9781611972801.40

S. Lin, M. Yeh, and C. Li, Sampling and summarization for social networks (tutorial, p.2013

Y. Luo, G. H. Fletcher, J. Hidders, Y. Wu, and P. D. Bra, External memory K-bisimulation reduction of big graphs, Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, CIKM '13, 2013.
DOI : 10.1145/2505515.2505752

T. Milo and D. Suciu, Index Structures for Path Expressions, ICDT, 1999.
DOI : 10.1007/3-540-49257-7_18

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.6664

S. Navlakha, R. Rastogi, and N. Shrivastava, Graph summarization with bounded error, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, 2008.
DOI : 10.1145/1376616.1376661

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.4242

M. Palmonari, A. Rula, R. Porrini, A. Maurino, B. Spahiu et al., ABSTAT: Linked Data Summaries with ABstraction and STATistics, ESWC Workshops, 2015.
DOI : 10.1145/1242572.1242668

F. Picalausa, Y. Luo, G. H. Fletcher, J. Hidders, and S. Vansummeren, A Structural Approach to Indexing Triples, 2012.
DOI : 10.1007/978-3-642-30284-8_34

M. Rudolf, M. Paradies, C. Bornhövd, and W. Lehner, SynopSys, First International Workshop on Graph Data Management Experiences and Systems, GRADES '13, 2013.
DOI : 10.1145/2484425.2484441

A. Schätzle, A. Neu, G. Lausen, and M. Przyjaciel-zablocki, Large-scale bisimulation of RDF graphs, Proceedings of the Fifth Workshop on Semantic Web Information Management, SWIM '13, 2013.
DOI : 10.1145/2484712.2484713

T. Tran, G. Ladwig, and S. Rudolph, Managing Structured and Semistructured RDF Data Using Structure Indexes, IEEE Transactions on Knowledge and Data Engineering, vol.25, issue.9, p.2013
DOI : 10.1109/TKDE.2012.134

T. Tran, H. Wang, S. Rudolph, and P. Cimiano, Top-k Exploration of Query Candidates for Efficient Keyword Search on Graph-Shaped (RDF) Data, 2009 IEEE 25th International Conference on Data Engineering, 2009.
DOI : 10.1109/ICDE.2009.119

P. Zhao, J. X. Yu, and P. S. Yu, Graph indexing: Tree + delta >= graph, VLDB, 2007.