Ontology type: schema:ScholarlyArticle Open Access: True
2022-02-19
AUTHORSWenfei Fan, Yuanhao Li, Muyang Liu, Can Lu
ABSTRACTThis paper proposes a scheme to reduce big graphs to small graphs. It contracts obsolete parts and regular structures into supernodes. The supernodes carry a synopsis SQ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S_\mathcal {Q}$$\end{document} for each query class Q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {Q}$$\end{document} in use, to abstract key features of the contracted parts for answering queries of Q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {Q}$$\end{document}. Moreover, for various types of graphs, we identify regular structures to contract. The contraction scheme provides a compact graph representation and prioritizes up-to-date data. Better still, it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible and decontracting the supernodes only when necessary. As a proof of concept, we show how to adapt existing algorithms for subgraph isomorphism, triangle counting, shortest distance, connected component and clique decision to contracted graphs. We also provide a bounded incremental contraction algorithm in response to updates, such that its cost is determined by the size of areas affected by the updates alone, not by the entire graphs. We experimentally verify that on average, the contraction scheme reduces graphs by 71.9% and improves the evaluation of these queries by 1.69, 1.44, 1.47, 2.24 and 1.37 times, respectively. More... »
PAGES1-25
http://scigraph.springernature.com/pub.10.1007/s00778-022-00731-7
DOIhttp://dx.doi.org/10.1007/s00778-022-00731-7
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1145717696
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information Systems",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "BDBC, Beihang University, Beijing, China",
"id": "http://www.grid.ac/institutes/grid.64939.31",
"name": [
"University of Edinburgh, Edinburgh, UK",
"Shenzhen Institute of Computing Sciences, Shenzhen, China",
"BDBC, Beihang University, Beijing, China"
],
"type": "Organization"
},
"familyName": "Fan",
"givenName": "Wenfei",
"id": "sg:person.010530666126.66",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010530666126.66"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Edinburgh, Edinburgh, UK",
"id": "http://www.grid.ac/institutes/grid.4305.2",
"name": [
"University of Edinburgh, Edinburgh, UK"
],
"type": "Organization"
},
"familyName": "Li",
"givenName": "Yuanhao",
"id": "sg:person.014010701261.81",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014010701261.81"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Edinburgh, Edinburgh, UK",
"id": "http://www.grid.ac/institutes/grid.4305.2",
"name": [
"University of Edinburgh, Edinburgh, UK"
],
"type": "Organization"
},
"familyName": "Liu",
"givenName": "Muyang",
"id": "sg:person.013017546073.65",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013017546073.65"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Shenzhen Institute of Computing Sciences, Shenzhen, China",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Shenzhen Institute of Computing Sciences, Shenzhen, China"
],
"type": "Organization"
},
"familyName": "Lu",
"givenName": "Can",
"id": "sg:person.015132346775.46",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015132346775.46"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1038/sdata.2016.35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039633073",
"https://doi.org/10.1038/sdata.2016.35"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-030-18579-4_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1113642198",
"https://doi.org/10.1007/978-3-030-18579-4_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-68125-0_84",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015857389",
"https://doi.org/10.1007/978-3-540-68125-0_84"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-18206-8_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025089564",
"https://doi.org/10.1007/978-3-642-18206-8_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10618-011-0224-z",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017664270",
"https://doi.org/10.1007/s10618-011-0224-z"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44816-0_11",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024211106",
"https://doi.org/10.1007/3-540-44816-0_11"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1038/43601",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009550067",
"https://doi.org/10.1038/43601"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01386390",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041716633",
"https://doi.org/10.1007/bf01386390"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1038/30918",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041985305",
"https://doi.org/10.1038/30918"
],
"type": "CreativeWork"
}
],
"datePublished": "2022-02-19",
"datePublishedReg": "2022-02-19",
"description": "This paper proposes a scheme to reduce big graphs to small graphs. It contracts obsolete parts and regular structures into supernodes. The supernodes carry a synopsis SQ\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$S_\\mathcal {Q}$$\\end{document} for each query class Q\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal {Q}$$\\end{document} in use, to abstract key features of the contracted parts for answering queries of Q\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal {Q}$$\\end{document}. Moreover, for various types of graphs, we identify regular structures to contract. The contraction scheme provides a compact graph representation and prioritizes up-to-date data. Better still, it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible and decontracting the supernodes only when necessary. As a proof of concept, we show how to adapt existing algorithms for subgraph isomorphism, triangle counting, shortest distance, connected component and clique decision to contracted graphs. We also provide a bounded incremental contraction algorithm in response to updates, such that its cost is determined by the size of areas affected by the updates alone, not by the entire graphs. We experimentally verify that on average, the contraction scheme reduces graphs by 71.9% and improves the evaluation of these queries by 1.69, 1.44, 1.47, 2.24 and 1.37 times, respectively.",
"genre": "article",
"id": "sg:pub.10.1007/s00778-022-00731-7",
"inLanguage": "en",
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.4273689",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.4576785",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1044889",
"issn": [
"1066-8888",
"0949-877X"
],
"name": "The VLDB Journal",
"publisher": "Springer Nature",
"type": "Periodical"
}
],
"keywords": [
"query classes",
"compact graph representation",
"big graphs",
"triangle counting",
"subgraph isomorphism",
"queries",
"graph representation",
"types of graphs",
"entire graph",
"supernodes",
"small graphs",
"exact answer",
"proof of concept",
"contraction algorithm",
"algorithm",
"graph",
"regular structure",
"obsolete parts",
"scheme",
"date data",
"key features",
"update",
"same time",
"labels",
"representation",
"cost",
"proof",
"decisions",
"features",
"class",
"concept",
"time",
"answers",
"counting",
"contraction scheme",
"data",
"part",
"evaluation",
"synopsis",
"isomorphism",
"size of area",
"distance",
"use",
"short distances",
"components",
"structure",
"area",
"types",
"size",
"response",
"contraction",
"paper"
],
"name": "Making graphs compact by lossless contraction",
"pagination": "1-25",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1145717696"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00778-022-00731-7"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00778-022-00731-7",
"https://app.dimensions.ai/details/publication/pub.1145717696"
],
"sdDataset": "articles",
"sdDatePublished": "2022-06-01T22:26",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_941.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00778-022-00731-7"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00778-022-00731-7'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00778-022-00731-7'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00778-022-00731-7'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00778-022-00731-7'
This table displays all metadata directly associated to this object as RDF triples.
173 TRIPLES
22 PREDICATES
84 URIs
67 LITERALS
4 BLANK NODES