Graph summarization is a well-established problem in large-scale graph data management. Its goal is to produce a summary graph, which is a coarse-grained version of a graph, whose use in substitution for the original graph enables downstream task execution and query processing at scale. Despite the extensive literature on graph summarization, still nowadays query processing on summary graphs is accomplished by either reconstructing the original graph, or in a query-specific manner. No general methods exist that operate on the summary graph only, with no graph reconstruction. In this paper, we fill this gap, and study for the first time general-purpose (approximate) query processing on summary graphs. This is a new important tool to support data-management tasks that rely on scalable graph query processing, including social network analysis. We set the stage of this problem, by devising basic, yet principled algorithms, and thoroughly analyzing their peculiarities and capabilities of performing well in practice, both conceptually and experimentally. The ultimate goal of this work is to make researchers and practitioners aware of this so-far overlooked problem, and define an authoritative starting point to stimulate and drive further research.

General-purpose query processing on summary graphs / Anagnostopoulos, Aris; Arrigoni, Valentina; Gullo, Francesco; Salvatori, Giorgia; Severini, Lorenzo. - In: SOCIAL NETWORK ANALYSIS AND MINING. - ISSN 1869-5469. - 14:1(2024). [10.1007/s13278-024-01314-w]

General-purpose query processing on summary graphs

Anagnostopoulos, Aris;Gullo, Francesco
;
Salvatori, Giorgia;Severini, Lorenzo
2024

Abstract

Graph summarization is a well-established problem in large-scale graph data management. Its goal is to produce a summary graph, which is a coarse-grained version of a graph, whose use in substitution for the original graph enables downstream task execution and query processing at scale. Despite the extensive literature on graph summarization, still nowadays query processing on summary graphs is accomplished by either reconstructing the original graph, or in a query-specific manner. No general methods exist that operate on the summary graph only, with no graph reconstruction. In this paper, we fill this gap, and study for the first time general-purpose (approximate) query processing on summary graphs. This is a new important tool to support data-management tasks that rely on scalable graph query processing, including social network analysis. We set the stage of this problem, by devising basic, yet principled algorithms, and thoroughly analyzing their peculiarities and capabilities of performing well in practice, both conceptually and experimentally. The ultimate goal of this work is to make researchers and practitioners aware of this so-far overlooked problem, and define an authoritative starting point to stimulate and drive further research.
2024
Graph data management; Graph summarization; Query processing; Scalable graph processing
01 Pubblicazione su rivista::01a Articolo in rivista
General-purpose query processing on summary graphs / Anagnostopoulos, Aris; Arrigoni, Valentina; Gullo, Francesco; Salvatori, Giorgia; Severini, Lorenzo. - In: SOCIAL NETWORK ANALYSIS AND MINING. - ISSN 1869-5469. - 14:1(2024). [10.1007/s13278-024-01314-w]
File allegati a questo prodotto
File Dimensione Formato  
Anagnostopoulos_General‑purpose-query_2024.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.55 MB
Formato Adobe PDF
1.55 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1732725
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact