2013 ASpaceEfficientStreamingAlgorit

• (Jha et al., 2013) ⇒ Madhav Jha, C. Seshadhri, and Ali Pinar. (2013). “A Space Efficient Streaming Algorithm for Triangle Counting Using the Birthday Paradox.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487678

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+A+Space+Efficient+Streaming+Algorithm+for+Triangle+Counting+Using+the+Birthday+Paradox
• http://dl.acm.org/citation.cfm?id=2487575.2487678&preflayout=flat#citedby

Quotes

Author Keywords

• Computations on discrete structures; graph algorithms; streaming algorithms; triangle counting

Abstract

We design a space efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Our procedure is based on the classic probabilistic result, the birthday paradox. When the transitivity is constant and there are more edges than wedges (common properties for social networks), we can prove that our algorithm requires O (√ n) space (n is the number of vertices) to provide accurate estimates. We run a detailed set of experiments on a variety of real graphs and demonstrate that the memory requirement of the algorithm is a tiny fraction of the graph. For example, even for a graph with 200 million edges, our algorithm stores just 60,000 edges to give accurate results. Being a single pass streaming algorithm, our procedure also maintains a real-time estimate of the transitivity / number of triangles of a graph, by storing a miniscule fraction of edges.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 ASpaceEfficientStreamingAlgorit	C. Seshadhri Madhav Jha Ali Pinar			A Space Efficient Streaming Algorithm for Triangle Counting Using the Birthday Paradox				10.1145/2487575.2487678		2013