Summarizing semantic graphs: a survey | The VLDB Journal Skip to main content
Springer Nature Link
Log in

Summarizing semantic graphs: a survey

  • Regular Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

The explosion in the amount of the available RDF data has lead to the need to explore, query and understand such data sources. Due to the complex structure of RDF graphs and their heterogeneity, the exploration and understanding tasks are significantly harder than in relational databases, where the schema can serve as a first step toward understanding the structure. Summarization has been applied to RDF data to facilitate these tasks. Its purpose is to extract concise and meaningful information from RDF knowledge bases, representing their content as faithfully as possible. There is no single concept of RDF summary, and not a single but many approaches to build such summaries; each is better suited for some uses, and each presents specific challenges with respect to its construction. This survey is the first to provide a comprehensive survey of summarization method for semantic RDF graphs. We propose a taxonomy of existing works in this area, including also some closely related works developed prior to the adoption of RDF in the data management community; we present the concepts at the core of each approach and outline their main technical aspects and implementation. We hope the survey will help readers understand this scientifically rich area and identify the most pertinent summarization method for a variety of usage scenarios.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Notes

  1. http://www.w3.org.

  2. https://www.snomed.org/snomed-ct.

  3. https://www.w3.org/TR/rdf-sparql-query/.

  4. Thanks to William van Voensel from schema.org for sharing this application with us.

  5. https://github.com/yikeliu/VoG-Overlap.

  6. https://gitlab.inria.fr/cedar/quotientSummary.

  7. http://www.essepuntato.it/kce.

  8. http://www.ics.forth.gr/isl/rdf-digest/.

  9. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview.

  10. http://www.cin.ufpe.br/~speed/OWLSummarizer/.

  11. http://lod2-dev.vse.cz/lodsight/about.html.

  12. https://github.com/jindrichmynarz/rdf-path-examples.

  13. http://abstat.disco.unimib.it/search.

References

  1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)

    MATH  Google Scholar 

  2. Agrawal, R., Imielinski, T., Swami, A.N.: Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, May 26–28, 1993, pp. 207–216 (1993)

  3. Alzogbi, A., Lausen, G.: Similar structures inside RDF-graphs. In: Proceedings of the WWW2013 Workshop on Linked Data on the Web, Rio de Janeiro, Brazil, May 14, 2013 (2013)

  4. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)

    MATH  Google Scholar 

  5. Basca, C., Bernstein, A.: Avalanche: putting the spirit of the web back into semantic web querying. In: Proceedings of the ISWC 2010 Posters & Demonstrations Track: Collected Abstracts, Shanghai, China, November 9, 2010 (2010)

  6. Blom, S., Orzan, S.: A distributed algorithm for strong bisimulation reduction of state spaces. STTT 7(1), 74–86 (2005)

    Article  MATH  Google Scholar 

  7. Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)

    Article  MATH  Google Scholar 

  8. Boldi, P., Vigna, S.: Axioms for centrality. Internet Math. 10(3–4), 222–262 (2014)

    Article  MathSciNet  Google Scholar 

  9. Bursztyn, D., Goasdoué, F., Manolescu, I.: Efficient query answering in DL-Lite through FOL reformulation (extended abstract). In: Proceedings of the 28th International Workshop on Description Logics, Athens, Greece, June 7–10, 2015 (2015)

  10. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: the DL-Lite family. J. Autom. Reason. 39(3), 385–429 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Campinas, S., Perry, T., Ceccarelli, D., Delbru, R., Tummarello, G.: Introducing RDF graph summary with application to assisted SPARQL formulation. In: 23rd International Workshop on Database and Expert Systems Applications, DEXA 2012, Vienna, Austria, September 3–7, 2012, pp. 261–266 (2012)

  12. Čebirić, Š., Goasdoué, F., Guzewicz, P., Manolescu, I.: Compact Summaries of Rich Heterogeneous Graphs. Research report RR-8920, INRIA Saclay; Université Rennes 1 (2017). https://hal.inria.fr/hal-01325900

  13. Čebirić, Š., Goasdoué, F., Manolescu, I.: Query-oriented summarization of RDF graphs. PVLDB 8(12), 2012–2015 (2015)

    Google Scholar 

  14. Cebiric, S., Goasdoué, F., Manolescu, I.: Query-oriented summarization of RDF graphs. In: Proceedings of the Data Science—30th British International Conference on Databases, BICOD 2015, Edinburgh, UK, July 6–8, 2015, pp. 87–91 (2015)

  15. Chen, C., Lin, C.X., Fredrikson, M., Christodorescu, M., Yan, X., Han, J.: Mining graph patterns efficiently via randomized summaries. PVLDB 2(1), 742–753 (2009)

    Google Scholar 

  16. Chen, C., Yan, X., Zhu, F., Han, J., Yu, P.S.: Graph OLAP: towards online analytical processing on graphs. In: Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), December 15–19, 2008, Pisa, Italy (2008)

  17. Consens, M.P., Fionda, V., Khatchadourian, S., Pirrò, G.: S+EPPs: construct and explore bisimulation summaries, plus optimize navigational queries; all on existing SPARQL systems. PVLDB 8(12), 2028–2031 (2015)

    Google Scholar 

  18. Consens, M.P., Miller, R.J., Rizzolo, F., Vaisman, A.A.: Exploring XML web collections with DescribeX. TWEB 4(3), 11:1–11:46 (2010)

    Article  Google Scholar 

  19. Dolby, J., Fokoue, A., Kalyanpur, A., Kershenbaum, A., Schonberg, E., Srinivas, K., Ma, L.: Scalable semantic retrieval through summarization and refinement. In: Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22–26, 2007, Vancouver, British Columbia, Canada, pp. 299–304 (2007)

  20. Dolby, J., Fokoue, A., Kalyanpur, A., Schonberg, E., Srinivas, K.: Scalable highly expressive reasoner (SHER). J. Web Semant. 7(4), 357–361 (2009)

    Article  Google Scholar 

  21. Dudás, M., Svátek, V., Mynarz, J.: Dataset summary visualization with LODSight. In: The Semantic Web: ESWC 2015 Satellite Events—ESWC 2015 Satellite Events Portorož, Slovenia, May 31–June 4, 2015, Revised Selected Papers, pp. 36–40 (2015)

  22. Fan, W., Li, J., Wang, X., Wu, Y.: Query preserving graph compression. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20–24, 2012, pp. 157–168 (2012)

  23. Fokoue, A., Kershenbaum, A., Ma, L.: SHIN ABox reduction. In: Proceedings of the 2006 International Workshop on Description Logics (DL2006), Windermere, Lake District, UK, May 30–June 1, 2006 (2006)

  24. Fokoue, A., Kershenbaum, A., Ma, L., Schonberg, E., Srinivas, K.: The summary Abox: cutting ontologies down to size. In: Proceedings of the Semantic Web—ISWC 2006, 5th International Semantic Web Conference, ISWC 2006, Athens, GA, USA, November 5–9, 2006, pp. 343–356 (2006)

  25. Glimm, B., Kazakov, Y., Liebig, T., Tran, T., Vialard, V.: Abstraction refinement for ontology materialization. In: Proceedings of the Semantic Web—ISWC 2014—13th International Semantic Web Conference, Riva del Garda, Italy, October 19–23, 2014, Part II, pp. 180–195 (2014)

  26. Goasdoué, F., Karanasos, K., Leblay, J., Manolescu, I.: View selection in semantic web databases. PVLDB 5(2), 97–108 (2011)

    Google Scholar 

  27. Goasdoué, F., Manolescu, I., Roatis, A.: Efficient query answering against dynamic RDF databases. In: Joint 2013 EDBT/ICDT Conferences, EDBT ’13 Proceedings, Genoa, Italy, March 18–22, 2013, pp. 299–310 (2013)

  28. Goldman, R., Widom, J.: Dataguides: enabling query formulation and optimization in semistructured databases. In: VLDB’97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25–29, 1997, Athens, Greece, pp. 436–445 (1997)

  29. Gurajada, S., Seufert, S., Miliaraki, I., Theobald, M.: Using graph summarization for join-ahead pruning in a distributed RDF engine. In: Proceedings of the Sixth Workshop on Semantic Web Information Management, SWIM 2014, Snowbird, UT, USA, June 22–27, 2014 (2014)

  30. Hakimi, S.L.: Steiner’s problem in graphs and its implications. Networks 1(2), 113–133 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  31. Han, J., Pei, J., Yin, Y., Mao, R.: Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Min. Knowl. Discov. 8(1), 53–87 (2004)

    Article  MathSciNet  Google Scholar 

  32. Henzinger, M.R., Henzinger, T.A., Kopke, P.W.: Computing simulations on finite and infinite graphs. In: FOCS (1995)

  33. Hose, K., Schenkel, R.: Towards benefit-based RDF source selection for SPARQL queries. In: Proceedings of the 4th International Workshop on Semantic Web Information Management, SWIM 2012, Scottsdale, AZ, USA, May 20, 2012, p. 2 (2012)

  34. Jiang, X., Zhang, X., Gao, F., Pu, C., Wang, P.: Graph compression strategies for instance-focused semantic mining. In: Linked Data and Knowledge Graph—7th Chinese Semantic Web Symposium and 2nd Chinese Web Science Conference, CSWS 2013, Shanghai, China, August 12–16, 2013. Revised Selected Papers, pp. 50–61 (2013)

  35. Joshi, A.K., Hitzler, P., Dong, G.: Towards logical linked data compression. In: Proceedings of the Joint Workshop on Large and Heterogeneous Data and Quantitative Formalization in the Semantic Web, LHD+ SemQuant2012, at the 11th International Semantic Web Conference, ISWC2012. Citeseer (2012)

  36. Joshi, A.K., Hitzler, P., Dong, G.: Logical linked data compression. In: The Semantic Web: Semantics and Big Data, 10th International Conference, ESWC 2013, Montpellier, France, May 26–30, 2013. Proceedings, pp. 170–184 (2013)

  37. Kaushik, R., Bohannon, P., Naughton, J.F., Korth, H.F.: Covering indexes for branching path queries. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3–6, 2002, pp. 133–144 (2002)

  38. Kaushik, R., Shenoy, P., Bohannon, P., Gudes, E.: Exploiting local similarity for indexing paths in graph-structured data. In: Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26–March 1, 2002, pp. 129–140 (2002)

  39. Kellou-Menouer, K., Kedad, Z.: Schema discovery in RDF data sources. In: Conceptual Modeling—Proceedings of the 34th International Conference, ER 2015, Stockholm, Sweden, October 19–22, 2015 (2015)

  40. Khan, A., Bhowmick, S.S., Bonchi, F.: Summarizing static and dynamic big graphs. PVLDB 10(12), 1981–1984 (2017)

    Google Scholar 

  41. Khan, K., Nawaz, W., Lee, Y.: Set-based approximate approach for lossless graph summarization. Computing 97(12), 1185–1207 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  42. Khatchadourian, S., Consens, M.P.: Explod: summary-based exploration of interlinking and RDF usage in the linked open data cloud. In: The Semantic Web: Research and Applications, 7th Extended Semantic Web Conference, ESWC 2010, Heraklion, Crete, Greece, May 30–June 3, 2010, Proceedings, Part II, pp. 272–287 (2010)

  43. Khatchadourian, S., Consens, M.P.: Exploring RDF usage and interlinking in the Linked Open Data Cloud using ExpLOD. In: WWW2010 Workshop on Linked Data on the Web (LDOW) (2010)

  44. Khatchadourian, S., Consens, M.P.: Understanding billions of triples with usage summaries. In: Semantic Web Challenge (2011)

  45. Khatchadourian, S., Consens, M.P.: Constructing bisimulation summaries on a multi-core graph processing framework. In: Proceedings of the Third International Workshop on Graph Data Management Experiences and Systems, GRADES 2015, Melbourne, VIC, Australia, May 31–June 4, 2015 (2015)

  46. Kondylakis, H., Plexousakis, D.: Ontology evolution in data integration: Query rewriting to the rescue. In: Conceptual Modeling–ER 2011, 30th International Conference, ER2011, Brussels, Belgium, October 31–November 3, 2011. Proceedings, pp. 393–401 (2011)

  47. Kondylakis, H., Plexousakis, D.: Ontology evolution: assisting query migration. In: Conceptual Modeling—31st International Conference ER 2012, Florence, Italy, October 15–18, 2012. Proceedings, pp. 331–344 (2012)

  48. Kondylakis, H., Plexousakis, D.: Ontology evolution without tears. J. Web Semant. 19, 42–58 (2013)

    Article  Google Scholar 

  49. Konrath, M., Gottron, T., Scherp, A.: Schemex–web-scale indexed schema extraction of Linked Open Data. In: Semantic Web Challenge, Submission to the Billion Triple Track, pp. 52–58 (2011)

  50. Konrath, M., Gottron, T., Staab, S., Scherp, A.: Schemex—efficient construction of a data catalogue by stream-based indexing of linked data. J. Web Semant. 16, 52–58 (2012)

    Article  Google Scholar 

  51. Koutra, D., Kang, U., Vreeken, J., Faloutsos, C.: Summarizing and understanding large graphs. Stat. Anal. Data Min. 8(3), 183–202 (2015)

    Article  MathSciNet  Google Scholar 

  52. Kyrola, A., Blelloch, G.E., Guestrin, C.: Graphchi: Large-scale graph computation on just a PC. In: 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8–10, 2012, pp. 31–46 (2012)

  53. Lanti, D., Rezk, M., Xiao, G., Calvanese, D.: The NPD benchmark: Reality check for OBDA systems. In: Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23–27, 2015, pp. 617–628 (2015)

  54. Le, W., Li, F., Kementsietsidis, A., Duan, S.: Scalable keyword search on large RDF data. IEEE TKDE 26(11), 2774–2788 (2014)

    Google Scholar 

  55. LeFevre, K., Terzi, E.: Grass: Graph structure summarization. In: Proceedings of the SIAM International Conference on Data Mining, SDM 2010, April 29–May 1, 2010, Columbus, Ohio, USA, pp. 454–465 (2010)

  56. Leskovec, J., Rajaraman, A., Ullman, J.D.: Mining of Massive Datasets, 2nd edn. Cambridge University Press, Cambridge (2014)

    Book  Google Scholar 

  57. Lin, S.D., Yeh, M.Y., Li, C.T.: Sampling and summarization for social networks. In: 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) (tutorial) (2013)

  58. Liu, X., Tian, Y., He, Q., Lee, W., McPherson, J.: Distributed graph summarization. In: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM 2014, Shanghai, China, November 3–7, 2014, pp. 799–808 (2014)

  59. Liu, Y., Safavi, T., Dighe, A., Koutra, D.: Graph summarization methods and applications: a survey. ACM Comput. Surv. 51(3), 62:1–62:34 (2018)

    Article  Google Scholar 

  60. Louati, A., Aufaure, M., Lechevallier, Y.: Graph aggregation: application to social networks. In: Advances in Theory and Applications of High Dimensional and Symbolic Data Analysis, HDSDA 2011, October 27–30, 2011, Beihang University, Beijing, China, pp. 157–177 (2011)

  61. Lucchese, C., Orlando, S., Perego, R.: A unifying framework for mining approximate top-\(k\) binary patterns. IEEE Trans. Knowl. Data Eng. 26(12), 2900–2913 (2014)

    Article  Google Scholar 

  62. Luo, Y., Fletcher, G.H.L., Hidders, J., Wu, Y., Bra, P.D.: External memory k-bisimulation reduction of big graphs. In: 22nd ACM International Conference on Information and Knowledge Management, CIKM’13, San Francisco, CA, USA, October 27–November 1, 2013, pp. 919–928 (2013)

  63. Marketakis, Y., Minadakis, N., Kondylakis, H., Konsolaki, K., Samaritakis, G., Theodoridou, M., Flouris, G., Doerr, M.: X3ML mapping framework for information integration in cultural heritage and beyond. Int. J. Digit. Libr. 18(4), 301–319 (2017)

    Article  Google Scholar 

  64. Milo, T., Suciu, D.: Index structures for path expressions. In: Database Theory—ICDT ’99, 7th International Conference, Jerusalem, Israel, January 10–12, 1999, Proceedings, pp. 277–295 (1999)

  65. Minadakis, N., Marketakis, Y., Kondylakis, H., Flouris, G., Theodoridou, M., de Jong, G., Doerr, M.: X3ML framework: An effective suite for supporting data mappings. In: Proceedings of the Workshop on Extending, Mapping and Focusing the CRM Co-located with 19th International Conference on Theory and Practice of Digital Libraries (2015), Poznań, Poland, September 17, 2015, pp. 1–12 (2015)

  66. Motta, E., Mulholland, P., Peroni, S., d’Aquin, M., Gómez-Pérez, J.M., Mendez, V., Zablith, F.: A novel approach to visualizing and navigating ontologies. In: The Semantic Web—ISWC 2011—10th International Semantic Web Conference, Bonn, Germany, October 23–27, 2011, Proceedings, Part I, pp. 470–486 (2011)

  67. Murtagh, F.: A survey of recent advances in hierarchical clustering algorithms. Comput. J. 26(4), 354–359 (1983)

    Article  MATH  Google Scholar 

  68. Mynarz, J., Dudás, M., Tomeo, P., Svátek, V.: Generating examples of paths summarizing RDF datasets. In: Joint Proceedings of the Posters and Demos Track of the 12th International Conference on Semantic Systems—SEMANTiCS2016 and the 1st International Workshop on Semantic Change & Evolving Semantics (SuCCESS’16) Co-located with the 12th International Conference on Semantic Systems (SEMANTiCS 2016), Leipzig, Germany, September 12–15, 2016 (2016)

  69. Navlakha, S., Rastogi, R., Shrivastava, N.: Graph summarization with bounded error. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10–12, 2008 (2008)

  70. Neumann, T., Weikum, G.: The RDF-3X engine for scalable management of RDF data. VLDB J. 19(1), 91–113 (2010)

    Article  Google Scholar 

  71. Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  72. Palmonari, M., Rula, A., Porrini, R., Maurino, A., Spahiu, B., Ferme, V.: ABSTAT: linked data summaries with abstraction and statistics. In: The Semantic Web: ESWC 2015 Satellite Events—ESWC 2015 Satellite Events Portorož, Slovenia, May 31–June 4, 2015, Revised Selected Papers, pp. 128–132 (2015)

  73. Pan, J.Z., Gómez-Pérez, J.M., Ren, Y., Wu, H., Wang, H., Zhu, M.: Graph pattern based RDF data compression. In: Semantic Technology - 4th Joint International Conference, JIST 2014, Chiang Mai, Thailand, November 9–11, 2014. Revised Selected Papers, pp. 239–256 (2014)

  74. Pappas, A., Troullinou, G., Roussakis, G., Kondylakis, H., Plexousakis, D.: Exploring importance measures for summarizing RDF/S kbs. In: The Semantic Web—14th International Conference, ESWC 2017, Portorož, Slovenia, May 28–June 1, 2017, Proceedings, Part I, pp. 387–403 (2017)

  75. Peroni, S., Motta, E., d’Aquin, M.: Identifying key concepts in an ontology, through the integration of cognitive principles with statistical and topological measures. In: The Semantic Web, 3rd Asian Semantic Web Conference, ASWC 2008, Bangkok, Thailand, December 8-11, 2008. Proceedings, pp. 242–256 (2008)

  76. Pham, M., Passing, L., Erling, O., Boncz, P.A.: Deriving an emergent relational schema from RDF data. In: Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18–22, 2015, pp. 864–874 (2015)

  77. Picalausa, F., Luo, Y., Fletcher, G.H.L., Hidders, J., Vansummeren, S.: A structural approach to indexing triples. In: The Semantic Web: Research and Applications—9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 27–31, 2012. Proceedings (2012)

  78. Pires, C.E.S., Queiroz-Sousa, P.O., Kedad, Z., Salgado, A.C.: Summarizing ontology-based schemas in PDMS. In: Workshops Proceedings of the 26th International Conference on Data Engineering, ICDE 2010, March 1–6, 2010, Long Beach, California, USA, pp. 239–244 (2010)

  79. Pouriyeh, S.A., Allahyari, M., Kochut, K., Arabnia, H.R.: A comprehensive survey of ontology summarization: measures and methods. CoRR arXiv:1801.01937 (2018)

  80. Presutti, V., Aroyo, L., Adamou, A., Schopman, B.A.C., Gangemi, A., Schreiber, G.: Extracting core knowledge from linked data. In: Proceedings of the Second International Workshop on Consuming Linked Data (COLD2011), Bonn, Germany, October 23, 2011 (2011)

  81. Queiroz-Sousa, P.O., Salgado, A.C., Pires, C.E.S.: A method for building personalized ontology summaries. JIDM 4(3), 236–250 (2013)

    Google Scholar 

  82. Qun, C., Lim, A., Ong, K.W.: D(k)-index: An adaptive structural summary for graph-structured data. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9–12, 2003, pp. 134–144 (2003)

  83. Riondato, M., García-Soriano, D., Bonchi, F.: Graph summarization with quality guarantees. Data Min. Knowl. Discov. 31(2), 314–349 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  84. Rissanen, J.: Modeling by shortest data description. Automatica 14(5), 465–471 (1978)

    Article  MATH  Google Scholar 

  85. Rudolf, M., Paradies, M., Bornhövd, C., Lehner, W.: Synopsys: large graph analytics in the SAP HANA database through summarization. In: First International Workshop on Graph Data Management Experiences and Systems, GRADES 2013, Co-loated with SIGMOD/PODS 2013, New York, NY, USA, June 24, 2013, p. 16 (2013)

  86. Schätzle, A., Neu, A., Lausen, G., Przyjaciel-Zablocki, M.: Large-scale bisimulation of RDF graphs. In: Proceedings of the Fifth Workshop on Semantic Web Information Management, SWIM@SIGMOD Conference 2013, New York, NY, USA, June 23, 2013, pp. 1:1–1:8 (2013)

  87. Schmachtenberg, M., Bizer, C., Paulheim, H.: State of the LOD Cloud 2014. http://linkeddatacatalog.dws.informatik.uni-mannheim.de/state/. Accessed 30 Mar 2017

  88. Schwarte, A., Haase, P., Hose, K., Schenkel, R., Schmidt, M.: FedX: optimization techniques for federated query processing on linked data. In: The Semantic Web—ISWC 2011—10th International Semantic Web Conference, Bonn, Germany, October 23–27, 2011, Proceedings, Part I, pp. 601–616 (2011)

  89. Seah, B., Bhowmick, S.S., Dewey, C.F., Yu, H.: FUSE: a profit maximization approach for functional summarization of biological networks. BMC Bioinform. 13(S–3), S10 (2012)

    Article  Google Scholar 

  90. Song, Q., Wu, Y., Dong, X.L.: Mining summaries for knowledge graph search. In: IEEE 16th International Conference on Data Mining, ICDM 2016, December 12–15, 2016, Barcelona, Spain, pp. 1215–1220 (2016)

  91. Spahiu, B., Porrini, R., Palmonari, M., Rula, A., Maurino, A.: ABSTAT: ontology-driven linked data summaries with pattern minimalization. In: SumPre (2016)

  92. Spahiu, B., Porrini, R., Palmonari, M., Rula, A., Maurino, A.: ABSTAT: ontology-driven linked data summaries with pattern minimalization. In: The Semantic Web—ESWC 2016 Satellite Events, Heraklion, Crete, Greece, May 29–June 2, 2016, Revised Selected Papers, pp. 381–395 (2016)

  93. Stefanoni, G., Motik, B., Kostylev, E.V.: Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation. Research report, University of Oxford (2017). https://www.cs.ox.ac.uk/isg/tools/SumRDF/paper-tr.pdf

  94. Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C., Reynolds, D.: SPARQL basic graph pattern optimization using selectivity estimation. In: Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21–25, 2008, pp. 595–604 (2008)

  95. Sydow, M., Pikula, M., Schenkel, R.: The notion of diversity in graphical entity summarisation on semantic knowledge graphs. J. Intell. Inf. Syst. 41(2), 109–149 (2013)

    Article  Google Scholar 

  96. Tian, Y., Hankins, R.A., Patel, J.M.: Efficient aggregation for graph summarization. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10–12, 2008, pp. 567–580 (2008)

  97. Tian, Y., Patel, J.M.: Interactive graph summarization. In: Link Mining: Models, Algorithms, and Applications, pp. 389–409. Springer (2010)

  98. Tran, T., Ladwig, G., Rudolph, S.: Managing structured and semistructured RDF data using structure indexes. IEEE TKDE 25(9), 2076–2089 (2013)

    Google Scholar 

  99. Troullinou, G., Kondylakis, H., Daskalaki, E., Plexousakis, D.: RDF digest: efficient summarization of RDF/S kbs. In: The Semantic Web. Latest Advances and New Domains—12th European Semantic Web Conference, ESWC 2015, Portoroz, Slovenia, May 31–June 4, 2015. Proceedings, pp. 119–134 (2015)

  100. Troullinou, G., Kondylakis, H., Daskalaki, E., Plexousakis, D.: RDF digest: ontology exploration using summaries. In: Proceedings of the ISWC 2015 Posters & Demonstrations Track Co-located with the 14th International Semantic Web Conference (ISWC-2015), Bethlehem, PA, USA, October 11, 2015 (2015)

  101. Troullinou, G., Kondylakis, H., Daskalaki, E., Plexousakis, D.: Ontology understanding without tears: The summarization approach. Semant. Web 8(6), 797–815 (2017)

    Article  Google Scholar 

  102. Troullinou, G., Kondylakis, H., Stefanidis, K., Plexousakis, D.: Exploring RDFS kbs using summaries. In: The Semantic Web—ISWC 2018—17th International Semantic Web Conference, Monterey, CA, USA, October 8–12, 2018, Proceedings, Part I, pp. 268–284 (2018)

  103. Troullinou, G., Kondylakis, H., Stefanidis, K., Plexousakis, D.: Rdfdigest+: a summary-driven system for kbs exploration. In: Proceedings of the ISWC 2018 Posters & Demonstrations, Industry and Blue Sky Ideas Tracks Co-located with 17th International Semantic Web Conference (ISWC 2018), Monterey, USA, October 8–12, 2018 (2018)

  104. Udrea, O., Pugliese, A., Subrahmanian, V.S.: GRIN: a graph based RDF index. In: Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22–26, 2007, Vancouver, British Columbia, Canada, pp. 1465–1470 (2007)

  105. Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)

    Article  Google Scholar 

  106. W3C: Resource description framework. http://www.w3.org/RDF/

  107. W3C: Owl 1 web ontology language. https://www.w3.org/TR/owl-features/ (2012)

  108. W3C: Owl 2 web ontology language. https://www.w3.org/TR/owl2-overview/ (2012)

  109. W3C: SPARQL 1.1 query language. http://www.w3.org/TR/sparql11-query/ (2013)

  110. Wu, G., Li, J., Feng, L., Wang, K.: Identifying potentially important concepts and relations in an ontology. In: The Semantic Web—ISWC 2008, 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, October 26–30, 2008. Proceedings, pp. 33–49 (2008)

  111. Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structure-based approach. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13–18, 2004, pp. 335–346 (2004)

  112. You, J., Pan, Q., Shi, W., Zhang, Z., Hu, J.: Towards graph summary and aggregation: a survey. In: Zhou, S., Wu, Z. (eds.) Social Media Retrieval and Mining, pp. 3–12. Springer (2013)

  113. Zhang, H., Duan, Y., Yuan, X., Zhang, Y.: ASSG: adaptive structural summary for RDF graph data. In: Proceedings of the ISWC 2014 Posters & Demonstrations Track a track within the 13th International Semantic Web Conference, ISWC 2014, Riva del Garda, Italy, October 21, 2014., pp. 233–236 (2014)

  114. Zhang, N., Tian, Y., Patel, J.M.: Discovery-driven graph summarization. In: Proceedings of the 26th International Conference on Data Engineering, ICDE 2010, March 1–6, 2010, Long Beach, California, USA, pp. 880–891 (2010)

  115. Zhang, X., Cheng, G., Ge, W., Qu, Y.: Summarizing vocabularies in the global semantic web. J. Comput. Sci. Technol. 24(1), 165–174 (2009)

    Article  Google Scholar 

  116. Zhang, X., Cheng, G., Qu, Y.: Ontology summarization based on rdf sentence graph. In: Proceedings of the 16th International Conference on World Wide Web, WWW 2007, Banff, Alberta, Canada, May 8–12, 2007, pp. 707–716 (2007)

  117. Zhao, P., Yu, J.X., Yu, P.S.: Graph indexing: tree + delta \(>\)= graph. In: Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23–27, 2007 (2007)

  118. Zheng, W., Zou, L., Peng, W., Yan, X., Song, S., Zhao, D.: Semantic SPARQL similarity search over RDF knowledge graphs. PVLDB 9(11), 840–851 (2016)

    Google Scholar 

  119. Zneika, M., Lucchese, C., Vodislav, D., Kotzinos, D.: RDF graph summarization based on approximate patterns. In: Information Search, Integration, and Personalization—10th International Workshop, ISIP 2015, Grand Forks, ND, USA, October 1–2, 2015, Revised Selected Papers, pp. 69–87 (2015)

  120. Zneika, M., Lucchese, C., Vodislav, D., Kotzinos, D.: Summarizing linked data RDF graphs using approximate graph pattern mining. In: Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016, Bordeaux, France, March 15–16, 2016, pp. 684–685 (2016)

  121. Zneika, M., Vodislav, D., Kotzinos, D.: Quality Metrics For RDF Graph Summarization. Semant. Web J. (SWJ) (2018) (accepted, to appear)

Download references

Acknowledgements

This research is implemented through IKY scholarships programme and co-financed by the European Union and Greek national funds through the action entitled “Reinforcement of Postdoctoral Researchers”, in the framework of the Operational Programme “Human Resources Development Program, Education and Life-long Learning“ of the National Strategic Reference Framework (NSRF) 2014–2020.

Author information

Authors and Affiliations

  1. Inria and LIX (UMR 7161, CNRS and Ecole polytechnique), Palaiseau, France

    Šejla Čebirić & Ioana Manolescu

  2. Univ Rennes, Inria, CNRS, IRISA, Rennes, France

    François Goasdoué

  3. Institute of Computer Science, FORTH, Heraklion, Greece

    Haridimos Kondylakis & Georgia Troullinou

  4. Lab. ETIS UMR 8051, University of Paris-Seine, University of Cergy-Pontoise, ENSEA, CNRS, 95000, Pontoise, France

    Dimitris Kotzinos & Mussab Zneika

Authors
  1. Šejla Čebirić
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. François Goasdoué
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Haridimos Kondylakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dimitris Kotzinos
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ioana Manolescu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Georgia Troullinou
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Mussab Zneika
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Haridimos Kondylakis.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Čebirić, Š., Goasdoué, F., Kondylakis, H. et al. Summarizing semantic graphs: a survey. The VLDB Journal 28, 295–327 (2019). https://doi.org/10.1007/s00778-018-0528-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-018-0528-3

Keywords

Search

Navigation