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-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_302.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 N7f91728809e644d0a4ca5255ca82378f
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 N08eb8a93b3714061ad1350de807030b8
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N43e889d015594b85a9db360f6052ddc1
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 N7128d1a02d0f409596cf0d67e42a689e
42 N79799a8d9d2943d58985c05c9e386d16
43 schema:publisher N9f9314b5f32348e5abda0e9c1f774e7e
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-10-01T06:57
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N16335d140fc3499ea01ce6beafd08bcd
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 N08d695116107420280b63f1f73a539c1 schema:familyName Wattenhofer
54 schema:givenName Roger
55 rdf:type schema:Person
56 N08eb8a93b3714061ad1350de807030b8 rdf:first N7f75618c7ecf4e24abcdab0cae5fe442
57 rdf:rest Ne38b867fd0e84ca4aa00984f00e10093
58 N16335d140fc3499ea01ce6beafd08bcd schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N30e8119f4c6841edaa19bd78bf39d8a7 schema:affiliation grid-institutes:grid.168010.e
61 schema:familyName Kane
62 schema:givenName Daniel M.
63 rdf:type schema:Person
64 N3d6c091bc9944579916dc2f3774d1075 schema:familyName Pitts
65 schema:givenName Andrew
66 rdf:type schema:Person
67 N43e889d015594b85a9db360f6052ddc1 schema:isbn 978-3-642-31584-8
68 978-3-642-31585-5
69 schema:name Automata, Languages, and Programming
70 rdf:type schema:Book
71 N57a0e9034df24d1bafc8a3d6ec19e75c rdf:first sg:person.012443273612.41
72 rdf:rest Nd6d07abb0b5c4fdeb23483525792f647
73 N7128d1a02d0f409596cf0d67e42a689e schema:name doi
74 schema:value 10.1007/978-3-642-31585-5_53
75 rdf:type schema:PropertyValue
76 N79799a8d9d2943d58985c05c9e386d16 schema:name dimensions_id
77 schema:value pub.1011001481
78 rdf:type schema:PropertyValue
79 N7f75618c7ecf4e24abcdab0cae5fe442 schema:familyName Czumaj
80 schema:givenName Artur
81 rdf:type schema:Person
82 N7f91728809e644d0a4ca5255ca82378f rdf:first N30e8119f4c6841edaa19bd78bf39d8a7
83 rdf:rest N8e9f11187ff44bd9bd3545e4e398431d
84 N8e9f11187ff44bd9bd3545e4e398431d rdf:first sg:person.011757371347.43
85 rdf:rest N57a0e9034df24d1bafc8a3d6ec19e75c
86 N9ba58c37a4bf4fc1b4490c50fff86a67 rdf:first N3d6c091bc9944579916dc2f3774d1075
87 rdf:rest Nb14e1c3fb7d54476866ed23c149de0ec
88 N9f9314b5f32348e5abda0e9c1f774e7e schema:name Springer Nature
89 rdf:type schema:Organisation
90 Nb14e1c3fb7d54476866ed23c149de0ec rdf:first N08d695116107420280b63f1f73a539c1
91 rdf:rest rdf:nil
92 Nd6d07abb0b5c4fdeb23483525792f647 rdf:first sg:person.016304035343.50
93 rdf:rest rdf:nil
94 Nd85453e06a004daa82bff0b4ac15c438 schema:familyName Mehlhorn
95 schema:givenName Kurt
96 rdf:type schema:Person
97 Ne38b867fd0e84ca4aa00984f00e10093 rdf:first Nd85453e06a004daa82bff0b4ac15c438
98 rdf:rest N9ba58c37a4bf4fc1b4490c50fff86a67
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)


...