Approximate Counting of Cycles in Streams View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Madhusudan Manjunath , Kurt Mehlhorn , Konstantinos Panagiotou , He Sun

ABSTRACT

We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the naïve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i. e., the input stream is a sequence of edge insertions and deletions. More... »

PAGES

677-688

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_57

DOI

http://dx.doi.org/10.1007/978-3-642-23719-5_57

DIMENSIONS

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


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": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Manjunath", 
        "givenName": "Madhusudan", 
        "id": "sg:person.012214516515.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012214516515.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, 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, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Panagiotou", 
        "givenName": "Konstantinos", 
        "id": "sg:person.010066472565.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010066472565.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Fudan University, Shanghai, China", 
          "id": "http://www.grid.ac/institutes/grid.8547.e", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
            "Fudan University, Shanghai, 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": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the na\u00efve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i.\u00a0e., the input stream is a sequence of edge insertions and deletions.", 
    "editor": [
      {
        "familyName": "Demetrescu", 
        "givenName": "Camil", 
        "type": "Person"
      }, 
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-23719-5_57", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-23718-8", 
        "978-3-642-23719-5"
      ], 
      "name": "Algorithms \u2013 ESA 2011", 
      "type": "Book"
    }, 
    "keywords": [
      "non-trivial algorithms", 
      "subgraph counting problem", 
      "first non-trivial algorithm", 
      "subgraphs of size", 
      "data streams", 
      "turnstile model", 
      "input stream", 
      "edge insertions", 
      "counting problem", 
      "algorithm", 
      "approximate counting", 
      "sampling algorithm", 
      "number of occurrences", 
      "fixed size", 
      "streams", 
      "subgraphs", 
      "instances", 
      "random variables", 
      "idea", 
      "counting", 
      "model", 
      "number", 
      "sequence", 
      "size", 
      "setting", 
      "variables", 
      "cycle", 
      "insertion", 
      "contrast", 
      "occurrence", 
      "deletion", 
      "problem", 
      "approach"
    ], 
    "name": "Approximate Counting of Cycles in Streams", 
    "pagination": "677-688", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038114440"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-23719-5_57"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-23719-5_57", 
      "https://app.dimensions.ai/details/publication/pub.1038114440"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:52", 
    "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_11.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-23719-5_57"
  }
]
 

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-23719-5_57'

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-23719-5_57'

Turtle is a human-readable linked data format.

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

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-23719-5_57'


 

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

122 TRIPLES      22 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-23719-5_57 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N788b40be00954429880a3b67cc876137
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the naïve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i. e., the input stream is a sequence of edge insertions and deletions.
7 schema:editor N75fc1fab8baf4dffb98876e5c5df49c3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N5ab39d9eac024255aa19e7374a57cdcb
11 schema:keywords algorithm
12 approach
13 approximate counting
14 contrast
15 counting
16 counting problem
17 cycle
18 data streams
19 deletion
20 edge insertions
21 first non-trivial algorithm
22 fixed size
23 idea
24 input stream
25 insertion
26 instances
27 model
28 non-trivial algorithms
29 number
30 number of occurrences
31 occurrence
32 problem
33 random variables
34 sampling algorithm
35 sequence
36 setting
37 size
38 streams
39 subgraph counting problem
40 subgraphs
41 subgraphs of size
42 turnstile model
43 variables
44 schema:name Approximate Counting of Cycles in Streams
45 schema:pagination 677-688
46 schema:productId N79c318869ab448d1b078fd3d3e523f0f
47 Nb61b11bcf80044ebacd161d811423808
48 schema:publisher N02a9167bb60240e6946f3a07074b318c
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038114440
50 https://doi.org/10.1007/978-3-642-23719-5_57
51 schema:sdDatePublished 2022-10-01T06:52
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Nd3cc1ad1b2ac422c95b7a739a99feac8
54 schema:url https://doi.org/10.1007/978-3-642-23719-5_57
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N02a9167bb60240e6946f3a07074b318c schema:name Springer Nature
59 rdf:type schema:Organisation
60 N478350f252f24a9082233476a0802129 rdf:first sg:person.011757371347.43
61 rdf:rest N9ddce7bc20d2405fa88b86bd31d9118e
62 N5ab39d9eac024255aa19e7374a57cdcb schema:isbn 978-3-642-23718-8
63 978-3-642-23719-5
64 schema:name Algorithms – ESA 2011
65 rdf:type schema:Book
66 N652cf2f8e1264e18b342628b5a8249b7 rdf:first sg:person.016304035343.50
67 rdf:rest rdf:nil
68 N66cadc76127a471d919ab2dcee21e124 schema:familyName Halldórsson
69 schema:givenName Magnús M.
70 rdf:type schema:Person
71 N73ec330225c04784b5bf20337017b043 schema:familyName Demetrescu
72 schema:givenName Camil
73 rdf:type schema:Person
74 N75fc1fab8baf4dffb98876e5c5df49c3 rdf:first N73ec330225c04784b5bf20337017b043
75 rdf:rest N7f22e31d88b9480d88802dc55287f35d
76 N788b40be00954429880a3b67cc876137 rdf:first sg:person.012214516515.87
77 rdf:rest N478350f252f24a9082233476a0802129
78 N79c318869ab448d1b078fd3d3e523f0f schema:name dimensions_id
79 schema:value pub.1038114440
80 rdf:type schema:PropertyValue
81 N7f22e31d88b9480d88802dc55287f35d rdf:first N66cadc76127a471d919ab2dcee21e124
82 rdf:rest rdf:nil
83 N9ddce7bc20d2405fa88b86bd31d9118e rdf:first sg:person.010066472565.92
84 rdf:rest N652cf2f8e1264e18b342628b5a8249b7
85 Nb61b11bcf80044ebacd161d811423808 schema:name doi
86 schema:value 10.1007/978-3-642-23719-5_57
87 rdf:type schema:PropertyValue
88 Nd3cc1ad1b2ac422c95b7a739a99feac8 schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.010066472565.92 schema:affiliation grid-institutes:grid.419528.3
97 schema:familyName Panagiotou
98 schema:givenName Konstantinos
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010066472565.92
100 rdf:type schema:Person
101 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
102 schema:familyName Mehlhorn
103 schema:givenName Kurt
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
105 rdf:type schema:Person
106 sg:person.012214516515.87 schema:affiliation grid-institutes:grid.419528.3
107 schema:familyName Manjunath
108 schema:givenName Madhusudan
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012214516515.87
110 rdf:type schema:Person
111 sg:person.016304035343.50 schema:affiliation grid-institutes:grid.8547.e
112 schema:familyName Sun
113 schema:givenName He
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016304035343.50
115 rdf:type schema:Person
116 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Saarbrücken, Germany
117 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
118 rdf:type schema:Organization
119 grid-institutes:grid.8547.e schema:alternateName Fudan University, Shanghai, China
120 schema:name Fudan University, Shanghai, China
121 Max Planck Institute for Informatics, Saarbrücken, Germany
122 rdf:type schema:Organization
 




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


...