preamb.tex

% !TeX root = 00_nesting_paper-short.tex
% THIS IS AN EXAMPLE DOCUMENT FOR VLDB 2012
% based on ACM SIGPROC-SP.TEX VERSION 2.7
% Modified by  Gerald Weber <gerald@cs.auckland.ac.nz>
% Removed the requirement to include *bbl file in here. (AhmetSacan, Sep2012)
% Fixed the equation on page 3 to prevent line overflow. (AhmetSacan, Sep2012)

\documentclass[sigconf]{acmart}
%\setcopyright{acmlicensed}

%%\usepackage{lastpage}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
%\usepackage{balance}  % for  \balance command ON LAST PAGE  (only there!)

\usepackage{braket}

\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{axiom}{Axiom}

\usepackage{algorithm}
\usepackage{thmtools}
\usepackage{varioref}
\renewcommand{\thmcontinues}[1]{cont'd p. \pageref{#1}}
\newtheorem{ex}{Example}
\usepackage[noend]{algpseudocode}
\makeatletter
\renewcommand{\ALG@beginalgorithmic}{\small}
\makeatother
\makeatletter

\usepackage{listings}
%\usepackage[dvipsnames]{xcolor}
\definecolor{eclipseBlue}{RGB}{42,0.0,255}
\definecolor{eclipseGreen}{RGB}{63,127,95}
\definecolor{eclipsePurple}{RGB}{127,0,85}
\lstset{basicstyle=\ttfamily\small,%
	%backgroundcolor=\color[rgb]{0.85,0.85,0.86},%
	frame=single,
	framerule=0pt,
	xleftmargin=\fboxsep,
	xrightmargin=\fboxsep,
	commentstyle=\color{eclipseGreen}, % style of comments
	keywordstyle=\color{eclipsePurple}, % style of keywords
	stringstyle=\color{eclipseBlue},
	breaklines=true,
	postbreak=\raisebox{0ex}[0ex][0ex]{\ensuremath{\color{red}\hookrightarrow\space}}
}
\lstdefinelanguage{sparql}{
	morecomment=[l][]{\#},
	morestring=[b][]\",
	morekeywords={BIND,URI,CONCAT,SELECT,CONSTRUCT,DESCRIBE,ASK,WHERE,FROM,NAMED,PREFIX,BASE,OPTIONAL,FILTER,GRAPH,LIMIT,OFFSET,SERVICE,UNION,EXISTS,NOT,BINDINGS,MINUS,a},
	sensitive=true
}
\lstdefinelanguage{cypher}{
	morekeywords={MATCH,RETURN,WHERE,DISTINCT,WITH,CREATE,COUNT,AS,UNION,ALL,is,null,NOT,AND,OR},
	sensitive=true,
	morecomment=[l]{//}, % l is for line comment
}
\lstdefinelanguage{AQL}{
	morekeywords={
		FOR,IN,COLLECT,INTO,RETURN
	},
	morestring=[b]",
	stringstyle=\color{eclipseGreen},
	morecomment=[l]{--}, % l is for line comment
}

\usepackage{multirow}
\usepackage{subcaption}
\usepackage{booktabs}
\usepackage{adjustbox}

\usepackage{float}
\newfloat{lstfloat}{htbp}{lop}
\floatname{lstfloat}{Listing}

\definecolor{webgreen}{rgb}{0,.5,0}
\newcommand{\mstr}[1]{\textup{\color{webgreen}``#1''}}

\newcommand{\nested}{\ensuremath{G_o}}
\newcommand{\ngraph}{{g}}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\cod}{cod}
\newcommand{\ONTA}{\mstr{onta}}
\newcommand{\RELA}{\mstr{rela}}
\newcommand{\SRC}{\mstr{src}}
\newcommand{\DST}{\mstr{dst}}
\newcommand{\VS}{\mathcal{V}}
\newcommand{\ES}{\mathcal{E}}
\newcommand{\Keys}{K}
\newcommand{\Val}{V}
\newcommand{\valF}{F}
\newcommand{\nestF}{\nu}
\newcommand{\prov}{\epsilon}

\copyrightyear{2018}
\acmYear{2018}
\setcopyright{acmcopyright}
\acmConference[GRADES-NDA'18 ]{1st Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)}{June 10--15, 2018}{Houston, TX, USA}
\acmBooktitle{GRADES-NDA'18 : 1st Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), June 10--15, 2018, Houston, TX, USA}
\acmPrice{15.00}
\acmDOI{10.1145/3210259.3210267}
\acmISBN{978-1-4503-5695-4/18/06}
%\hypersetup{draft}

\begin{abstract}
	Despite the growing popularity of techniques related to graph summarization, a general operator for the flexible nesting of graphs is still missing.
	We propose a novel nested graph data model and a powerful graph nesting operator. In contrast to existing approaches, our approach is able to summarize vertices and paths among vertex groups within a single query. Further on, our model supports partial nestings under the preservation of original graph elements as well as the full recovery of the original graph. We propose an efficient nesting algorithm (THoSP) that is able to perform vertex and path nestings in a single visit of the input graph. Results of an experimental evaluation show that THoSP outperforms equivalent implementations based on graph (Cypher, SPARQL), relational (SQL) and document oriented (ArangoDB) databases.
\end{abstract}

\fancyhead{}
\title{THoSP: an Algorithm for Nesting Property Graphs}
\author{Giacomo Bergami}
\affiliation{\institution{University of Bologna}}
\email{giacomo.bergami2@unibo.it}

\author{André Petermann}
\affiliation{\institution{University of Leipzig}}
\email{petermann@informatik.uni-leipzig.de}

\author{Danilo Montesi}
\affiliation{\institution{University of Bologna}}
\email{danilo.montesi@unibo.it}