Counting Arbitrary Subgraphs in Data Streams View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Daniel M. Kane , Kurt Mehlhorn , Thomas Sauerwald , He Sun

ABSTRACT

We study the subgraph counting problem in data streams. We provide the first non-trivial estimator for approximately counting the number of occurrences of an arbitrary subgraph H of constant size in a (large) graph G. Our estimator works in the turnstile model, i.e., can handle both edge-insertions and edge-deletions, and is applicable in a distributed setting. Prior to this work, only for a few non-regular graphs estimators were known in case of edge-insertions, leaving the problem of counting general subgraphs in the turnstile model wide open. We further demonstrate the applicability of our estimator by analyzing its concentration for several graphs H and the case where G is a power law graph. More... »

PAGES

598-609

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_53

DOI

http://dx.doi.org/10.1007/978-3-642-31585-5_53

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1011001481


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Stanford University, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Department of Mathematics, Stanford University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kane", 
        "givenName": "Daniel M.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sauerwald", 
        "givenName": "Thomas", 
        "id": "sg:person.012443273612.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012443273612.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute for Modern Mathematics and Physics, Fudan University, China", 
          "id": "http://www.grid.ac/institutes/grid.8547.e", 
          "name": [
            "Max Planck Institute for Informatics, Germany", 
            "Institute for Modern Mathematics and Physics, Fudan University, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sun", 
        "givenName": "He", 
        "id": "sg:person.016304035343.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016304035343.50"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We study the subgraph counting problem in data streams. We provide the first non-trivial estimator for approximately counting the number of occurrences of an arbitrary subgraph H of constant size in a (large) graph G. Our estimator works in the turnstile model, i.e., can handle both edge-insertions and edge-deletions, and is applicable in a distributed setting. Prior to this work, only for a few non-regular graphs estimators were known in case of edge-insertions, leaving the problem of counting general subgraphs in the turnstile model wide open. We further demonstrate the applicability of our estimator by analyzing its concentration for several graphs H and the case where G is a power law graph.", 
    "editor": [
      {
        "familyName": "Czumaj", 
        "givenName": "Artur", 
        "type": "Person"
      }, 
      {
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "type": "Person"
      }, 
      {
        "familyName": "Pitts", 
        "givenName": "Andrew", 
        "type": "Person"
      }, 
      {
        "familyName": "Wattenhofer", 
        "givenName": "Roger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31585-5_53", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31584-8", 
        "978-3-642-31585-5"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "data streams", 
      "turnstile model", 
      "subgraph counting problem", 
      "power-law graphs", 
      "graph estimator", 
      "arbitrary subgraphs", 
      "general subgraphs", 
      "counting problem", 
      "number of occurrences", 
      "subgraphs", 
      "constant size", 
      "streams", 
      "graph", 
      "graph H", 
      "subgraph H", 
      "graph G.", 
      "model", 
      "estimator", 
      "applicability", 
      "work", 
      "number", 
      "setting", 
      "cases", 
      "size", 
      "occurrence", 
      "G.", 
      "problem", 
      "concentration"
    ], 
    "name": "Counting Arbitrary Subgraphs in Data Streams", 
    "pagination": "598-609", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011001481"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31585-5_53"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31585-5_53", 
      "https://app.dimensions.ai/details/publication/pub.1011001481"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_382.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31585-5_53"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

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/978-3-642-31585-5_53'

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/978-3-642-31585-5_53'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_53'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_53'


 

This table displays all metadata directly associated to this object as RDF triples.

129 TRIPLES      22 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31585-5_53 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na651d993ddf74f7eb220232fde07cd02
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description We study the subgraph counting problem in data streams. We provide the first non-trivial estimator for approximately counting the number of occurrences of an arbitrary subgraph H of constant size in a (large) graph G. Our estimator works in the turnstile model, i.e., can handle both edge-insertions and edge-deletions, and is applicable in a distributed setting. Prior to this work, only for a few non-regular graphs estimators were known in case of edge-insertions, leaving the problem of counting general subgraphs in the turnstile model wide open. We further demonstrate the applicability of our estimator by analyzing its concentration for several graphs H and the case where G is a power law graph.
7 schema:editor N80ebf5435c384730b33b24bb0a37dbf2
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nfbd68b74b1e847129a6cb4b7f98fe418
11 schema:keywords G.
12 applicability
13 arbitrary subgraphs
14 cases
15 concentration
16 constant size
17 counting problem
18 data streams
19 estimator
20 general subgraphs
21 graph
22 graph G.
23 graph H
24 graph estimator
25 model
26 number
27 number of occurrences
28 occurrence
29 power-law graphs
30 problem
31 setting
32 size
33 streams
34 subgraph H
35 subgraph counting problem
36 subgraphs
37 turnstile model
38 work
39 schema:name Counting Arbitrary Subgraphs in Data Streams
40 schema:pagination 598-609
41 schema:productId N911949abe3d54af1903cd99436a51b82
42 Na4375d62475c4b2a94be05cd6631620d
43 schema:publisher N280ac18763f64b7c82e16eb37b49f4c1
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011001481
45 https://doi.org/10.1007/978-3-642-31585-5_53
46 schema:sdDatePublished 2022-11-24T21:17
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N9667986bc2ee40769819c26bca71011c
49 schema:url https://doi.org/10.1007/978-3-642-31585-5_53
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N1fa37d2dfd5e44e68fbfc87d6395d39c rdf:first sg:person.011757371347.43
54 rdf:rest N52e319b39933421c94edd1f0b32acb54
55 N25e097fa037b4302bbbbfdc671f0601d rdf:first N890989055b7947ccb78fe55b56699752
56 rdf:rest Necb9a90a010944bb8f3da3406b0a0eb2
57 N280ac18763f64b7c82e16eb37b49f4c1 schema:name Springer Nature
58 rdf:type schema:Organisation
59 N52e319b39933421c94edd1f0b32acb54 rdf:first sg:person.012443273612.41
60 rdf:rest N8bd8d37fea2d4c0889bc346a11069dc9
61 N6625f72494fc48b79e213ddbafbaed34 schema:familyName Czumaj
62 schema:givenName Artur
63 rdf:type schema:Person
64 N788a2167be7e483887d5902be4b0f7d9 schema:affiliation grid-institutes:grid.168010.e
65 schema:familyName Kane
66 schema:givenName Daniel M.
67 rdf:type schema:Person
68 N80ebf5435c384730b33b24bb0a37dbf2 rdf:first N6625f72494fc48b79e213ddbafbaed34
69 rdf:rest Nc20bb7a9b4444201ba47993f4191b0b7
70 N890989055b7947ccb78fe55b56699752 schema:familyName Pitts
71 schema:givenName Andrew
72 rdf:type schema:Person
73 N8bd8d37fea2d4c0889bc346a11069dc9 rdf:first sg:person.016304035343.50
74 rdf:rest rdf:nil
75 N8e8c77f19adb4c2b8da818a5eded9412 schema:familyName Mehlhorn
76 schema:givenName Kurt
77 rdf:type schema:Person
78 N911949abe3d54af1903cd99436a51b82 schema:name dimensions_id
79 schema:value pub.1011001481
80 rdf:type schema:PropertyValue
81 N9667986bc2ee40769819c26bca71011c schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 Na4375d62475c4b2a94be05cd6631620d schema:name doi
84 schema:value 10.1007/978-3-642-31585-5_53
85 rdf:type schema:PropertyValue
86 Na651d993ddf74f7eb220232fde07cd02 rdf:first N788a2167be7e483887d5902be4b0f7d9
87 rdf:rest N1fa37d2dfd5e44e68fbfc87d6395d39c
88 Na6ca63bc02124d6a97c201fd49ac1b5a schema:familyName Wattenhofer
89 schema:givenName Roger
90 rdf:type schema:Person
91 Nc20bb7a9b4444201ba47993f4191b0b7 rdf:first N8e8c77f19adb4c2b8da818a5eded9412
92 rdf:rest N25e097fa037b4302bbbbfdc671f0601d
93 Necb9a90a010944bb8f3da3406b0a0eb2 rdf:first Na6ca63bc02124d6a97c201fd49ac1b5a
94 rdf:rest rdf:nil
95 Nfbd68b74b1e847129a6cb4b7f98fe418 schema:isbn 978-3-642-31584-8
96 978-3-642-31585-5
97 schema:name Automata, Languages, and Programming
98 rdf:type schema:Book
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computation Theory and Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
106 schema:familyName Mehlhorn
107 schema:givenName Kurt
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
109 rdf:type schema:Person
110 sg:person.012443273612.41 schema:affiliation grid-institutes:grid.419528.3
111 schema:familyName Sauerwald
112 schema:givenName Thomas
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012443273612.41
114 rdf:type schema:Person
115 sg:person.016304035343.50 schema:affiliation grid-institutes:grid.8547.e
116 schema:familyName Sun
117 schema:givenName He
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016304035343.50
119 rdf:type schema:Person
120 grid-institutes:grid.168010.e schema:alternateName Department of Mathematics, Stanford University, USA
121 schema:name Department of Mathematics, Stanford University, USA
122 rdf:type schema:Organization
123 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Germany
124 schema:name Max Planck Institute for Informatics, Germany
125 rdf:type schema:Organization
126 grid-institutes:grid.8547.e schema:alternateName Institute for Modern Mathematics and Physics, Fudan University, China
127 schema:name Institute for Modern Mathematics and Physics, Fudan University, China
128 Max Planck Institute for Informatics, Germany
129 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...