TY - GEN
T1 - Fleet
T2 - 28th ACM International Conference on Information and Knowledge Management, CIKM 2019
AU - Sanei-Mehri, Seyed Vahid
AU - Sarıyüce, Ahmet Erdem
AU - Zhang, Yu
AU - Tirthapura, Srikanta
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/11/3
Y1 - 2019/11/3
N2 - We consider space-efficient single-pass estimation of the number of butterflies, a fundamental bipartite graph motif, from a massive bipartite graph stream where each edge represents a connection between entities in two different partitions. We present a space lower bound for any streaming algorithm that can estimate the number of butterflies accurately, as well as FLEET, a suite of algorithms for accurately estimating the number of butterflies in the graph stream. Estimates returned by the algorithms come with provable guarantees on the approximation error, and experiments show good tradeoffs between the space used and the accuracy of approximation. We also present space-efficient algorithms for estimating the number of butterflies within a sliding window of the most recent elements in the stream. While there is a significant body of work on counting subgraphs such as triangles in a unipartite graph stream, our work seems to be one of the few to tackle the case of bipartite graph streams.
AB - We consider space-efficient single-pass estimation of the number of butterflies, a fundamental bipartite graph motif, from a massive bipartite graph stream where each edge represents a connection between entities in two different partitions. We present a space lower bound for any streaming algorithm that can estimate the number of butterflies accurately, as well as FLEET, a suite of algorithms for accurately estimating the number of butterflies in the graph stream. Estimates returned by the algorithms come with provable guarantees on the approximation error, and experiments show good tradeoffs between the space used and the accuracy of approximation. We also present space-efficient algorithms for estimating the number of butterflies within a sliding window of the most recent elements in the stream. While there is a significant body of work on counting subgraphs such as triangles in a unipartite graph stream, our work seems to be one of the few to tackle the case of bipartite graph streams.
KW - Butterfly counting
KW - Data stream
KW - Rectangle counting
UR - https://www.scopus.com/pages/publications/85075420660
U2 - 10.1145/3357384.3357983
DO - 10.1145/3357384.3357983
M3 - Conference contribution
AN - SCOPUS:85075420660
T3 - International Conference on Information and Knowledge Management, Proceedings
SP - 1201
EP - 1210
BT - CIKM 2019 - Proceedings of the 28th ACM International Conference on Information and Knowledge Management
PB - Association for Computing Machinery
Y2 - 3 November 2019 through 7 November 2019
ER -