Counting Hypergraphs in Data Streams

He Sun

Counting Hypergraphs in Data Streams

He Sun

Department of Computer Science

Research output: Contribution to journal › Article (Academic Journal)

59 Downloads (Pure)

Abstract

We present the first streaming algorithm for counting an arbitrary hypergraph H of constant size in a massive hypergraph G. Our algorithm can handle both edge-insertions and edge-deletions, and is applicable for the distributed setting. Moreover, our approach provides the first family of graph polynomials for the hypergraph counting problem. Because of the close relationship between hypergraphs and set systems, our approach may have applications in studying similar problems.

Original language	English
Number of pages	11
Journal	arXiv
Publication status	Published - 28 Apr 2013

Access to Document

Full-text PDF (accepted author manuscript)
This is the author accepted manuscript (AAM). The final published version (version of record) is available online via arXiv at http://arxiv.org/abs/1304.7456. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 180 KB

Handle.net

Persistent link

Cite this

@article{4485e8baad254b3f8872efbb4e00489e,

title = "Counting Hypergraphs in Data Streams",

abstract = "We present the first streaming algorithm for counting an arbitrary hypergraph H of constant size in a massive hypergraph G. Our algorithm can handle both edge-insertions and edge-deletions, and is applicable for the distributed setting. Moreover, our approach provides the first family of graph polynomials for the hypergraph counting problem. Because of the close relationship between hypergraphs and set systems, our approach may have applications in studying similar problems. ",

author = "He Sun",

year = "2013",

month = apr,

day = "28",

language = "English",

journal = "arXiv",

publisher = "Cornell University",

}

TY - JOUR

T1 - Counting Hypergraphs in Data Streams

AU - Sun, He

PY - 2013/4/28

Y1 - 2013/4/28

N2 - We present the first streaming algorithm for counting an arbitrary hypergraph H of constant size in a massive hypergraph G. Our algorithm can handle both edge-insertions and edge-deletions, and is applicable for the distributed setting. Moreover, our approach provides the first family of graph polynomials for the hypergraph counting problem. Because of the close relationship between hypergraphs and set systems, our approach may have applications in studying similar problems.

AB - We present the first streaming algorithm for counting an arbitrary hypergraph H of constant size in a massive hypergraph G. Our algorithm can handle both edge-insertions and edge-deletions, and is applicable for the distributed setting. Moreover, our approach provides the first family of graph polynomials for the hypergraph counting problem. Because of the close relationship between hypergraphs and set systems, our approach may have applications in studying similar problems.

UR - http://arxiv.org/abs/1304.7456

M3 - Article (Academic Journal)

JO - arXiv

JF - arXiv

ER -

Counting Hypergraphs in Data Streams

Abstract

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this