Article
Counting and Sampling Triangles from a Graph Stream
Proceedings of the VLDB Endowment
Document Type
Conference Proceeding
Disciplines
Conference
39th International Conference on Very Large Data Bases (VLDB 2013)
Publication Version
Accepted Manuscript
Link to Published Version
https://doi.org/10.14778/2556549.2556569
Publication Date
9-1-2013
DOI
10.14778/2556549.2556569
Conference Date
August 26-30, 2013
Geolocation
(46.0747793, 11.121748600000046)
Abstract
This paper presents a new space-efficient algorithm for counting and sampling triangles--and more generally, constant-sized cliques--in a massive graph whose edges arrive as a stream. Compared to prior work, our algorithm yields significant improvements in the space and time complexity for these fundamental problems. Our algorithm is simple to implement and has very good practical performance on large graphs.
Copyright Owner
VLDB Endowment
Copyright Date
2013
Language
en
File Format
application/pdf
Citation Information
A. Pavan, IBM T. J. Watson Research Center, IBM T. J. Watson Research Center and Srikanta Tirthapura. "Counting and Sampling Triangles from a Graph Stream" Trento, ItalyProceedings of the VLDB Endowment Vol. 6 Iss. 14 (2013) p. 1870 - 1881 Available at: http://works.bepress.com/srikanta-tirthapura/35/
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Pavan, Aduri, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. "Counting and sampling triangles from a graph stream." Proceedings of the VLDB Endowment 6, no. 14 (2013): 1870-1881. DOI: 10.14778/2556549.2556569.