Article

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

Authors:

Ziv Bar-Yossef,

D. SivakumarAuthors Info & Claims

SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 623 - 632

Published: 06 January 2002 Publication History

Abstract

We introduce reductions in the streaming model as a tool in the design of streaming algorithms. We develop the concept of list-efficient streaming algorithms that are essential to the design of efficient streaming algorithms through reductions.Our results include a suite of list-efficient streaming algorithms for basic statistical primitives. Using the reduction paradigm along with these tools, we design streaming algorithms for approximately counting the number of triangles in a graph presented as a stream.A specific highlight of our work is the first algorithm for the number of distinct elements in a data stream that achieves arbitrary approximation factors. (Independently, Trevisan [Tre01] has solved this problem via a different approach; our algorithm has the advantage of being list-efficient.)

References

[1]

{AMS99} N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. JCSS, 58(1):137-147, 1999.]]

Digital Library

[2]

{AYZ97} N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997.]]

[3]

{Bab01} S. Babu. Work related to STREAM project, 2001. http://www-db.stanford.edu/stream/related.html.]]

[4]

{CW79} J. L. Carter and M. N. Wegman. Universal classes of hash functions. JCSS, 18(2):143-154, 1979.]]

[5]

{Dic58} L. E. Dickson. Linear Groups with an Exposition of the Galois Field Theory. Dover, 1958.]]

[6]

{EIO01} L. Engebretsen, P. Indyk, and R. O'Donnell. Derandomized dimensionality reduction with applications. Proc. 13th SODA, 2002.]]

Digital Library

[7]

{FKSV99} J. Feigenbaum, S. Kannan, M. Strauss, and M. Viswanathan. An approximate L1-difference algorithm for massive data streams. Proc. 40th FOCS, pp. 501-511, 1999.]]

Digital Library

[8]

{FM85} P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. JCSS, 31(2):182-209, 1985.]]

Digital Library

[9]

{FS00} J. Fong and M. Strauss. An approximate lp-difference algorithm for massive data streams. Proc. STAGS, pp. 193-204, 2000.]]

Digital Library

[10]

{GKMS01} A. C. Gilbert, Y. Kotidis, S. Muthuskrishnan, and M. J. Strauss. A few good terms: Efficient streaming computation of wavelet decompositions. Manuscript, 2001.]]

[11]

{Gol97} O. Goldreich. A sample of samplers --- a computational perspective on sampling (survey). ECCC, TR97-020, 1997.]]

[12]

{GKS01} S. Guha, N. Koudas, and K. Shim. Data streams and histograms. Proc. 33rd STOC, pp. 471-475, 2001.]]

Digital Library

[13]

{HRR99} M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. DIMACS series in Discr. Math. & Theor. Comp. Sc., 50:107-118, 1999.]]

Digital Library

[14]

{Ind00} P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. Proc. 41st FOCS, pp. 189-197, 2000.]]

Digital Library

[15]

{KN97} E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.]]

Digital Library

[16]

{NW94} N. Nisan and A. Wigderson. Hardness vs. randomness. JCSS, 49(2):149-167, 1994.]]

Digital Library

[17]

{Sip83} M. Sipser. A complexity theoretic approach to randomness. Proc. 15th STOC, pp. 330-335, 1983.]]

Digital Library

[18]

{Siv01} D. Sivakumar. Algorithmic derandomization via complexity theory. Manuscript, 2001.]]

[19]

{Sto83} L. J. Stockmeyer. The complexity of approximate counting. Proc. 15th STOC, pp. 118-126, 1983.]]

Digital Library

[20]

{Tre01} L. Trevisan. A note on counting distinct elements in the streaming model. Manuscript, 2001.]]

[21]

{Yao77} A.C-C. Yao. Probabilistic computations: toward a unified measure of complexity. Proc. 18th FOCS, pp. 222-227, 1977.]]

Cited By

Liu QSeshadhri CKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Improved Massively Parallel Triangle Counting in O(1) RoundsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662819(519-522)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662819
Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
https://dl.acm.org/doi/10.1145/3623800.3623808
Pavan AVinodchandran NBhattacharyya AMeel K(2022)Model Counting Meets Distinct Elements in a Data StreamACM SIGMOD Record10.1145/3542700.354272151:1(87-94)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1145/3542700.3542721
Show More Cited By

Recommendations

New Streaming Algorithms for Counting Triangles in Graphs
Proceedings of the 11th Annual International Conference on Computing and Combinatorics - Volume 3595

We present three streaming algorithms that ε,ï ź--- approximate the number of triangles in graphs. Similar to the previous algorithms [3], the space usage of presented algorithms are inversely proportional to the number of triangles while, for some ...
Counting triangles in data streams
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

We present two space bounded random sampling algorithms that compute an approximation of the number of triangles in an undirected graph given as a stream of edges. Our first algorithm does not make any assumptions on the order of edges in the stream. It ...
A distributed streaming framework for edge–cloud triangle counting in graph streams
Abstract
The triangle counting problem in graph streams has been extensively studied in social network analysis, recommendation systems, user portraits and other fields. However, cloud computing based streaming algorithms cause high bandwidth occupation ...
Highlights
- A framework of edge–cloud triangle counting to count triangles in graph streams.
- Algorithms TbEC and TbECOPT to reduce the transmission cost between the edge and cloud.
- Algorithms TbEC-BF and TbECOPT-BF to accurately count ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

January 2002

1018 pages

ISBN:089871513X

Conference Chair:
David Eppstein

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2002

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

107
Total Citations
View Citations
1,589
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu QSeshadhri CKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Improved Massively Parallel Triangle Counting in O(1) RoundsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662819(519-522)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662819
Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
https://dl.acm.org/doi/10.1145/3623800.3623808
Pavan AVinodchandran NBhattacharyya AMeel K(2022)Model Counting Meets Distinct Elements in a Data StreamACM SIGMOD Record10.1145/3542700.354272151:1(87-94)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1145/3542700.3542721
Fichtenberger HPeng PLibkin LBarceló P(2022)Approximately Counting Subgraphs in Data StreamsProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3524145(413-425)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3524145
Sheshbolouki AÖzsu M(2022)sGrapp: Butterfly Approximation in Streaming GraphsACM Transactions on Knowledge Discovery from Data10.1145/349501116:4(1-43)Online publication date: 8-Jan-2022
https://dl.acm.org/doi/10.1145/3495011
Yang XSong CYu MGu JLiu M(2022)Distributed Triangle Approximately Counting Algorithms in Simple Graph StreamACM Transactions on Knowledge Discovery from Data10.1145/349456216:4(1-43)Online publication date: 8-Jan-2022
https://dl.acm.org/doi/10.1145/3494562
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3469834
Gou XZou LLi GLi ZIdreos SSrivastava D(2021)Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate EdgesProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452800(645-657)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452800
Kara ANgo HNikolic MOlteanu DZhang H(2020)Maintaining Triangle Queries under UpdatesACM Transactions on Database Systems10.1145/339637545:3(1-46)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3396375
McGregor AVorotnikova SSuciu DTao YWei Z(2020)Triangle and Four Cycle Counting in the Data Stream ModelProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387652(445-456)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387652
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents