Since 1997, two awards are given annually to the best papers published in PODS.
Best Paper Award: This is an award for the best of all papers submitted, as judged by the program committee.
Best Student Award (2009 – ): From PODS 2009 on the Best Newcomer Award is replaced by the Best Student Award. This is an award for the best submission, as judged by the program committee, written exclusively by a student or students. An author is considered as a student if at the time of submission, the author is enrolled in a program at a university or institution leading to a doctoral/master’s/bachelor’s degree.
Best Newcomer Award (1997 – 2008): This is an award to the best submission, as judged by the program committee, written solely by authors who have never published in earlier PODS proceedings.
The program committee reserves the right to give both awards to the same paper, not to give an award, or to split an award among several papers. Papers authored or co-authored by program committee members are not eligible for an award.
Recipients of the Best Paper Award:
2024
Albert Atserias, and Phokion Kolaitis:
Consistency of Relations over Monoids
Michael A. Bender, Martin Farach-Colton, Michael T. Goodrich, and Hanna Komlos:
History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures
2023
Balder Ten Cate, Victor Dalmau, Maurice Funk, and Carsten Lutz:
Extremal Fitting Problems for Conjunctive Queries
2022
Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang:
Convergence of Datalog over (Pre-) Semirings
Jelani Nelson, Huacheng Yu:
Optimal Bounds for Approximate Counting
2021
Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler and Pavel Vesely:
Relative Error Streaming Quantiles
2020
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff and Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms
2019
Marcelo Arenas, Luis Alberto Croqueviell, Rajesh Jayaram and Cristian Riveros:
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
2018
Yufei Tao:
Entity Matching with Active Monotone Classification
2017
André Hernich, Carsten Lutz, Fabio Papacchini and Frank Wolter:
Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
2016
Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra:
FAQ: Questions Asked Frequently
2015
Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick:
Parallel-Correctness and Transferability for Conjunctive Queries
2014
Tom J. Ameloot, Bas Ketsman, Frank Neven, and Daniel Zinn:
Weaker Forms of Monotonicity for Declarative Networking: A More Fine-Grained Answer to the CALM-Conjecture
2013
Mikolaj Bojanczyk, Luc Segoufin, and Szymon Torunczyk:
Verification of Database-Driven Systems via Amalgamation
2012
Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra:
Worst-case Optimal Join Algorithms
2011
Marcelo Arenas, Jorge Perez, Juan L. Reutter:
Data Exchange Beyond Complete Data
2010
Daniel M. Kane, Jelani Nelson, David P. Woodruff:
An Optimal Algorithm for the Distinct Elements Problem
2009
Georg Gottlob, Stephanie Lee, Gregory Valiant:
Size and Treewidth Bounds for Conjunctive Queries
2008
Anish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy:
Estimating PageRank on Graph Streams
2007
Georg Gottlob, Zoltan Miklos, Thomas Schwentick:
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants
2006
Mikolaj Bojanczyk, Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin:
Two-Variable Logic on Data Trees and XML Reasoning
2005
Dirk Leinders, Jan Van den Bussche:
On the complexity of division and set joins in the relational algebra
and Marcelo Arenas, Leonid Libkin:
XML Data Exchange: Consistency and Query Answering
2004
Maarten Marx:
XCPath, the first order complete XPath dialect
2003
Marcelo Arenas, Leonid Libkin:
An Information-Theoretic Approach to Normal Forms for Relational and XML Data
2002
Georg Gottlob, Christoph Koch:
Monadic Datalog and the Expressive Power of Languages for Web Information Extraction
2001
Ronald Fagin, Amnon Lotem, Moni Naor:
Optimal Aggregation Algorithms for Middleware
2000
Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Auditing Boolean Attributes
1999
Michael Benedikt, Leonid Libkin:
Exact and Approximate Aggregation in Constraint Query Languages
1998
Frank Neven, Jan Van den Bussche:
Expressiveness of Structured Document Query Languages Based on Attribute Grammars
Vasilis Samoladas, Daniel P. Miranker:
A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries
1997
Christos H. Papadimitriou, Mihalis Yannakakis:
On the Complexity of Database Queries
Recipients of the Best Student Paper Award:
- 2017
- Sepehr Assadi:
- Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem
- 2016
- Adam Sealfon:
- Shortest Paths and Distances with Differential Privacy
- 2009
- Pawel Parys:
- XPath Evaluation in Linear Time with Polynomial Combined Complexity
Recipients of the Best Newcomer Award:
- 2024
- Christoph Dorn, and Haikal Pribadi:
- TypeQL: A Type-Theoretic & Polymorphic Query Language
- 2008
- Karl Schnaitter, Neoklis Polyzotis:
- Evaluating Rank Joins with Optimal Cost
- 2007
- Joost Engelfriet, Hendrik Jan Hoogeboom, Bart Samwel:
- XML Transformation by Tree-Walking Transducers with Invisible Pebbles
- 2006
- Michael Bender, Haodong Hu:
- An Adaptive Packed-Memory Array
- 2005
- Martin Abadi, Bogdan Warinschi:
- Security Analysis of Cryptographically Controlled Access to XML Documents
- 2004
- Maarten Marx:
- XCPath, the first order complete XPath dialect
- 2003
- Samir Khuller, Yoo-Ah Kim, Yung-Chun (Justin) Wan:
- Algorithms for Data Migration with Cloning
- 2002
- Chung-Min Chen, Christine T. Cheng:
- From Discrepancy to Declustering: Near optimal multidimensional declustering strategies for range queries
- 2001
- Kim S. Larsen:
- Relaxed Multi-Way Trees with Group Updates
- 2000
- Marc Spielmann:
- Verification of Relational Transducers for Electronic Commerce
- 1999
- Steven Dawson, Sabrina De Capitani di Vimercati, Patrick Lincoln, Pierangela Samarati:
- Minimal Data Upgrading to Prevent Inference and Association
- 1998
- Vasilis Samoladas, Daniel P. Miranker:
- A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries
- 1997
- Oliver M. Duschka, Michael R. Genesereth:
- Answering Recursive Queries Using Views