Counting Hypergraphs in Data Streams

Sun, He

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Paper

Counting Hypergraphs in Data Streams

MPS-Authors

/persons/resource/persons45576

Sun, He
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

arXiv:1304.7456.pdf
(Preprint), 180KB

Supplementary Material (public)

There is no public supplementary material available

Citation

Sun, H. (2013). Counting Hypergraphs in Data Streams. Retrieved from http://arxiv.org/abs/1304.7456.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-48DD-8

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.