# Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming

arXiv: https://arxiv.org/abs/2007.13466 · HTML: https://mlsanity.com/paper/2007.13466/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)

## Abstract (arXiv)

The problem of counting small subgraphs, and specifically cycles, in the streaming model received a lot of attention over the past few years. In this paper, we consider arbitrary order insertion-only streams, improving over the state-of-the-art result on counting 4-cycles. Our algorithm computes a (1+ε)-approximation by taking three passes over the stream and using space O(fracm log nε2 T1/3), where m is the number of edges in the graph and T is the number of 4-cycles.