Test of Time Awards

EDBT 2015 Test of Time Award

In 2014, Extended Database Technologies (EDBT http://www.edbt.org/) began awarding the EDBT test-of-time (ToT) award, with the goal of recognizing one paper, or a small number of papers, presented at EDBT earlier and that have best met the "test of time", i.e. that has had the most impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade(s). The EDBT ToT award for 2015 will be presented during the EDBT/ICDT 2015 Joint Conference, March 23-27, Brussels (Belgium) http://edbticdt2015.be.

The EDBT 2015 Test of Time Award committee was formed by
        Martin Kersten (CWI, The Netherlands),
        Guido Moerkotte (Uni Mannheim, Germany),
        Christoph Koch (EPFL, Switzerland),
all members of the EDBT 2015 PC and chaired by Gustavo Alonso, the EDBT 2015 PC chair.

The committee was charged with selecting a paper or a small number of papers from the proceedings of the following 4 editions: EDBT'88 - Venice, EDBT'90 - Venice, EDBT'92 - Vienna, EDBT'94 - Cambridge.

After careful consideration, the committee has decided to select the following paper as the EDBT ToT Award  winner for 2015:

        Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems,
        by Prof. Dr. Ralf Hartmut G├╝ting, University of Hagen, Germany
        published in the EDBT 1988 proceedings, 506-527.

The paper addresses the user's conceptual model of a database system for geometric data. It proposes to extend relational database management systems by integrating geometry at all levels: At the conceptual level, relational algebra is extended to include geometric data types and operators. At the implementation level, the wealth of algorithms and data structures for geometric problems developed in the past decade in the field of Computational Geometry is exploited. The paper starts from a view of relational algebra as a many-sorted algebra which allows to easily embed geometric data types and operators. A concrete algebra for two-dimensional applications is developed. It can be used as a highly expressive retrieval and data manipulation language for geometric as well as standard data. Also, geo-relational database systems and their implementation strategy are discussed.

The committee members unanimously agreed that this paper clearly stands out in terms of relevance, impact, and influence in databases. Of all the papers considered, this is the one that had had the most and longest lasting impact with results that are still relevant today and whose influence can be traced to many real systems and a significant amount of follow up work.

The paper pioneered an important application area well before it became mainstream and did it in a systematic and clean way that has been very influential in both research and practice. Modern commercial systems all support geographic data types that are nowadays used in a wide range of applications and use cases (maps, locations based services, geographic information systems, mobility, etc.).

The selection committee also appreciated very much the cleanliness, completeness, insights, formalism, and systematic treatment of the problem as well as the approach followed by the author in selecting and solving a research problem.


ICDT 2015 Test of Time Award

In 2013, the International Conference on Database Theory (ICDT) began awarding the ICDT test-of-time (ToT) award, with the goal of recognizing one paper, or a small number of  papers, presented at ICDT a decade earlier that have best met the "test of time". In 2015, the award will recognize 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 award will be presented during the EDBT/ICDT 2015 Joint   Conference, March 23-27, 2014 in Brussels, Belgium.

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.