Dan Olteanu and Jakub Závodný win test-of-time award for 2012 paper

 The International Conference on Database Theory (ICDT) presented the 2022 Test of Time Award to Dan Olteanu and Jakub Závodný. The award recognizes a paper presented 10 years prior at the ICDT conference that has best met the "test of time" and had the highest impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade. The award is presented during the EDBT/ICDT 2022 Joint Conference in March 2022.

The 2012 paper that earned the award is "Factorized Representations of Query Results: Size Bounds and Readability." The paper was written while Dan was a professor and Jakub a DPhil with the Department of Computer Science at the University of Oxford.

The paper introduces the fundamental concept of factorized databases. Such factorized databases give a proper balance between succinctness of the data representation and efficiency of subsequent processing. The paper presents several contributions in terms of mathematical characterizations, algorithmic techniques, and computational complexity. The paper initiated a new line of research and had a significant impact on theoretical and systems research and development in the field of data management, in particular on graph database systems, representation and enumeration of answers to database queries and of their provenance, low computational complexity for answering quantitative queries, and training machine learning models over large databases. This work also laid the foundations for Dan's 2015 ERC consolidator grant and his 2014 Google Faculty Award.

Together with his former Oxford research team, Dan previously won a Best Paper Award at the International Conference on Database Theory for their 2019 work on the first dynamic algorithm for counting triangles in graphs in worst-case optimal time.