Reductions in streaming algorithms, with an application to counting triangles in graphs

By Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar. ACM-SIAM Symposium on Discrete Algorithms, 2002

430 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/10dac777afc83308fd10782bc2bc529469cb9ce9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Efficient semi-streaming algorithms for local triangle counting in massive graphs (2008, background): “[2, 10]; here we deal with the problem of estimating the (local) number of triangles of all the individual nodes in the graph simultaneously.”
An optimal algorithm for the distinct elements problem (2010, background): “The problem of space-efficient F0-estimation is well-studied, beginning with the work of Flajolet and Martin [20], and continuing with a long line of research, [3, 4, 5, 6, 9, 12, 16, 17, 19, 23, 24, 26, 36].”
Graph sketches: sparsification, spanners, and subgraphs (2012, methodology): “Recent results include algorithms for constructing graph sparsifiers [1,35], spanners [16, 20], matchings [2, 3, 18, 36, 41], and counting small subgraphs such as triangles [6,9,30].”
Main-memory triangle computations for very large (sparse (power-law)) graphs (2008, methodology): “Approaches relying on streaming algorithms [23, 4, 25], approximate results [32, 25, 35], or compressed graphs [8, 9] also exist.”
Graph stream algorithms: a survey (2014, methodology): “[10] presented an algorithm based on the following relationship between T3 and the frequency moments of x, i.”
DOULION: counting triangles in massive graphs with a coin (2009, background): “Moreover, according to [5], triangle counting can benefit the query plan optimization in databases.”
Models and issues in data stream systems (2002, background): “In a recent paper, Bar-Yossef, Kumar, and Sivakumar [12] introduce the notion of reductions in streaming algorithms.”
Practical verified computation with streaming interactive proofs (2011, background): “Estimating the number of triangles in a graph has received significant attention because of its relevance to database query optimization—knowing the degree of transitivity of a relation is useful when estimating the cost of evaluation plans for certain relational queries— and investigating structura”
Counting Distinct Elements in a Data Stream (2002, methodology): “The algorithm in this section is a unified and improved version of two previous algorithms: one due to Bar-Yossef et al. [ BKS02 ] and one due to Gibbons and Tirthapura [GT01].”
Data streams: algorithms and applications (2005, methodology): “In fact, this method works in the Turnstile model as well even though the authors in [42] did not explicitly study it.”