Prof. Divyakant Agrawal and Prof. Amr El Abbadi to receive the ICDT 2015 Test of Time Award

By Rich Kildare

The "ICDT 2015 Test of Time Award" will be presented to Professors Agrawal and El Abbadi during the EDBT/ICDT 2015 Joint Conference. The conference is held March 23-27 in Brussels Belgium.

Both Professors work in the Department of Computer Science, UC Santa Barbara.

The award recognizes a paper from the ICDT 2005 proceedings that has had the most impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade.  

The committee consisting of Serge Abiteboul, Sudeepa Roy, and chaired by Leonid Libkin (2005 PC co-chair) has chosen the following recipient of the 2015 ICDT Test of Time Award:

   Efficient Computation of Frequent and Top-k Elements in Data Streams
   by Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi

The paper studies the problem of finding items which occur most frequently in a data stream. This is a basic algorithmic problem of great practical importance. The paper proposed a SpaceSaving algorithm which was shown to both provide theoretical guarantees and to perform significantly better than others in practical scenarios.  Since its publication, the paper has made impact in both algorithms research and practical implementations of streaming algorithms.  Several implementations of the algorithm have been made available, and they are used both in industry and as benchmarks to compare against other streaming algorithms.  The paper has been highly cited: many papers have made use of the data structure, either directly, or to solve new problems.  The algorithm itself is easy to motivate and state, and consequently it is taught in a number of algorithms courses.