Fast, Accurate and Provable Triangle Counting in Fully Dynamic Graph Streams
Abstract
Given a stream of edge additions and deletions, how can we estimate the count of triangles in it? If we can store only a subset of the edges, how can we obtain unbiased estimates with small variances?
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 09, 2020
- Source ID
- 10.1145/3375392
Entities
People
- Bryan Hooi
- Christos Faloutsos
- Jisu Kim
- Kijung Shin
- Sejoon Oh
Organizations
- Carnegie Mellon University
- Georgia Tech
- Institut National de Recherche en Informatique et en Automatique
- KAIST
- National Research Foundation of Korea
- National Science Foundation
- National University of Singapore
- United States Army Research Laboratory