PODS Best Paper Awards

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:

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 
         – and
         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:

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