Yossi Matias

Digital Library

ACM Paris Kanellakis Theory and Practice Award

Israel - 2019

citation

For foundational work on streaming algorithms and their application to large scale data analytics

Noga Alon, Phillip Gibbons, Yossi Matias and Mario Szegedy pioneered a framework of algorithmic techniques for analyzing streaming data sets. Massive data is processed while retaining only small randomized "synopses", or "sketches", that require limited memory and provide approximate answers. In a groundbreaking line of research work they introduced techniques for several key problems including estimation of frequency moments.

Due to its simplicity and elegance, their work has been instrumental in the development of the field of streaming algorithms, which is one of the most prolific and highly regarded areas of data management research. Their framework broadly applies to data analytic tasks with areas of application that include databases, network monitoring, usage analytics in internet products, natural language processing and machine learning.

ACM Fellows

Israel - 2009

citation

For contributions to the analysis of large data sets and data streams.

2019 ACM Paris Kanellakis Theory and Practice Award

ACM has named Noga Alon of Princeton University and Tel Aviv University; Phillip Gibbons of Carnegie Mellon University; Yossi Matias of Google and Tel Aviv University; and Mario Szegedy of Rutgers University recipients of the ACM Paris Kanellakis Theory and Practice Award for seminal work on the foundations of streaming algorithms and their application to large-scale data analytics.

Alon, Gibbons, Matias and Szegedy pioneered a framework for algorithmic treatment of streaming massive datasets. Today, their sketching and streaming algorithms remain the core approach for streaming big data and constitute an entire subarea of the field of algorithms. Additionally, the concepts of sketches and synopses that they introduced are now routinely used in a variety of data analysis tasks in databases, network monitoring, usage analytics in internet products, natural language processing and machine learning.

In their seminal paper, “The Space Complexity of Approximating the Frequency Moments,” Alon, Matias and Szegedy laid the foundations of the analysis of data streams using limited memory. Follow-up papers, including “Tracking Join and Self-join Sizes in Limited Storage,” by Alon, Gibbons, Matias, and Szegedy, and “New Sampling-Based Summary Statistics for Improving Approximate Query Answers,” by Gibbons and Matias, expanded on the idea of data synopses and were instrumental in the development of the burgeoning fields of streaming and sketching algorithms. This work has been applied to query planning and processing in databases and the design of small synopses to monitor vast quantities of data generated in networks.