ד"ר יחזקאל אביב אלגוריתמי Streaming ונתוני עתק 83-562

Recommended related courses:

Sketching Algorithms for Big Data: Jelani Nelson (Harvard).
Sketching, Streaming, and Sub-linear Space algorithms: Piotr Indyk (MIT).
Sublinear and streaming algorithms: Paul Beame (University of Washington).
 

Course Books

Data Streams: Algorithms and Applications
Muthukrishnan S 
Foundations and Trends in Theoretical Computer Science, 2005, Vol. 1 No. 2 pp. 117–236 doi: https://doi.org/10.1561/0400000002
PDF

Mining of massive datasets
Jure Leskovec, Anand Rajaraman, Jeffrey David Ullman
Cambridge University Press, 2020
Third edition
eBook

Sketch Techniques for Approximate Query Processing
Graham Cormode
Cormode, G., Garofalakis, M., Haas, P. J., & Jermaine, C. (2011). Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases, 4(1–3), 1–294.
PDF

Data Streams: Models and Algorithms
Aggarwal, Charu C. 
Springer, 2007.
PDF

Algorithms and Data Structures for Massive Datasets
Dzejla Medjedovic, Emin Tahirovic
Manning Publications, 2022
eBook

Knowledge Discovery from Data Streams
João Gama
Chapman & Hall/CRC, 2010
 eBook

Additional Reading List

  1. Robert Morris, Counting Large Numbers of Events in Small Registers. ACM 1978

  2. Noga Alon, Yossi Matias, and Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci., 1999

  3. M. Charikar., K. Chen and M. Farach-Colton, Finding Frequent Items in Data Streams. Proceedings of the 29th International Colloquium on Automata Languages and Programming, 2002

  4. G. Cormode and S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. Journal of Algorithms, 2005

  5. Dmitris Achlioptas, Database-friendly random projections. PODS 2001

  6. Emmanuel J. Candès, Justin K. Romberg, Terence Tao: Stable Signal Recovery from Incomplete and Inaccurate Measurements. Communications on Pure and Applied Mathematics, 2006

  7. Petros Drineas, Ravi Kannan, Michael Mahoney. Fast Monte Carlo Algorithms for Matrices Approximating Matrix Multiplication. SIAM J. Computing, 2006

  8. Edo Liberty, Simple and Deterministic Matrix Sketching. KDD 2013

  9. Cai, Candes, Shen, A Singular Value Thresholding Algorithm for Matrix Completion
    Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O’Callaghan. Clustering Data Streams. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000.

  10. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., & Pandit, V., Local Search Heuristic for k-Median and Facility Location Problems. In Proceedings of the thirty-third annual ACM symposium on Theory of Computing, 2001. 

  11. R. Ostrovsky and V. Braverman, Smooth Histograms for Sliding Windows. FOCS 2007.
     

תאריך עדכון אחרון : 29/10/2026