Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Conference Proceeding

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-2013

Journal or Book Title

Proceedings of the VLDB Endowment

Volume

6

Issue

14

First Page

1870

Last Page

1881

DOI

10.14778/2556549.2556569

Conference Date

August 26-30, 2013

City

Trento, Italy

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.

Comments

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.

Copyright Owner

VLDB Endowment

Language

en

File Format

application/pdf

Published Version

Share

Article Location

 
COinS