Counting Hypergraphs in Data Streams

He Sun

Research output: Contribution to journalArticle (Academic Journal)

31 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 languageEnglish
Number of pages11
JournalarXiv
Publication statusPublished - 28 Apr 2013

Fingerprint

Dive into the research topics of 'Counting Hypergraphs in Data Streams'. Together they form a unique fingerprint.

Cite this