Proceedings
PODS 2016 papers can be accessed here.
Conference Program: PODS Sessions
This page describes the complete PODS Conference program.
PODS Keynote
A Theory of Regular Queries
Monday 8:30-10:00
Location: Grand Ballroom BC
Moshe Y. Vardi
Session Chair: Tova Milo
RESEARCH SESSIONS
Award talks + 1 regular paper
Monday 10.30-12.00
Location: Grand Ballroom BC
Session Chair: Jan Van den Bussche
- ToT: Two-variable logic on data trees and XML reasoning
Mikolaj Bojanczyk; Claire David; Anca Muscholl; Thomas Schwentick; Luc Segoufin - Best Paper: FAQ: Questions Asked Frequently
Mahmoud Abo Khamis; Hung Ngo; Atri Rudra - Best Student Paper: Shortest Paths and Distances with Differential Privacy
Adam Sealfon - Paper 1: Minimization of Tree Pattern Queries
Wojciech Czerwinski; Wim Martens; Matthias Niewerth; Pawel Parys
Gems of PODS talks
Monday 13.30-15.00
Location: Grand Ballroom BC
Session Chair: Wang-Chiew Tan
- Optimal Score Aggregation Algorithms
Ronald Fagin (IBM Research - Almaden) - Hypertree Decompositions: Question and Answers
Georg Gottlob, Gianluigi Greco; Nicola Leone; Francesco Scarcello
Session 1: Query rewriting, views, and join algorithms
Monday 15.30-17.45
Location: Grand Ballroom BC
Session Chair: Dan Suciu
- Incremental View Maintenance For Collection Programming
Christoph Koch; Daniel Lupei; Val Tannen - Aggregations over Generalized Hypertree Decompositions
Manas Joglekar; Rohan Puttagunta; Christopher Re - Bounded Query Rewriting Using Views
Yang Cao; Wenfei Fan; Floris Geerts; Ping Lu - Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable
Tomasz Gogacz; Jerzy Marcinkowski - Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins
Xiao Hu; Ke Yi - On the Complexity of Inner Product Similarity Join
Thomas Dybdahl Ahle; Rasmus Pagh; Ilya Razenshteyn; Francesco Silvestri
Session 2: Workflows and Incomplete Information
Tuesday 13.30-15.00
Location: Grand Ballroom B
Session Chair: Claire David
- Verification of Hierarchical Artifact Systems
Alin Deutsch; Yuliang Li; Victor Vianu - Recency-Bounded Verification of Dynamic Database-Driven Systems
Parosh Aziz Abdulla; C. Aiswarya; Mohamed Faouzi Atig; Marco Montali; Othmane Rezine - Making SQL Queries Correct on Incomplete Databases: A Feasibility Study
Paolo Guagliardo; Leonid Libkin - Designing a Query Language for RDF: Marrying Open and Closed Worlds
Martin Ugarte; Marcelo Arenas
Session 3: Data Streams and Indexes
Tuesday 15.30-17.20
Location: Grand Ballroom B
Session Chair: Sudeepa Roy
- Schema validation via streaming circuits
Filip Murlak; Charles Paperman; Michal Pilipczuk - Variability in data streams
David Felber; Rafail Ostrovsky - Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors
Vladimir Braverman; Stephen Chestnut; David Woodruff; Lin Yang - Efficient Top-k Indexing via General Reductions
Rahul Saladi; Yufei Tao - Anti-Persistence on Persistent Storage: History-Independent Sparse Arrays and Dictionaries
Michael Bender; Jon Berry; Rob Johnson; Thomas M. Kroeger; Samuel McCauley; Cynthia A. Phillips; Bertrand Simon; Shikha Singh; David Zage
Session 4: Query evaluation
Wednesday 10.30-12.00
Location: Grand Ballroom B
Session Chair: Paris Kourtris
- Counting Answers to Existential Positive Queries: A Complexity Classification
Hubie Chen; Stefan Mengel - Worst-case Optimal Algorithms for Conjunctive Queries with Functional Dependencies
Mahmoud Abo Khamis; Hung Ngo; Dan Suciu - Semantic Acyclicity Under Constraints
Pablo Barcelo; Georg Gottlob; Andreas Pieris - Tractable Lineages on Treelike Instances: Limits and Extensions
Antoine Amarilli; Pierre Bourhis; Pierre Senellart
Session 5: Data Streams and Privacy
Wednesday 13.30-15.00
Location: Grand Ballroom B
Session Chair: Graham Comcorde
- Towards Tight Bounds for the Streaming Set Cover Problem
Sariel Har-Peled; Piotr Indyk; Sepideh Mahabadi; Ali Vakilian - An Optimal Algorithm for Heavy Hitters in Insertion Streams and Related Problems
Arnab Bhattacharyya; Palash Dey; David Woodruff - Better Algorithms for Counting Triangles in Data Streams
Andrew McGregor; Sofya Vorotnikova; Hoa Vu - Locating a Small Cluster Privately
Kobbi Nissim; Uri Stemmer; Salil Vadhan
Session 6: Algorithms and data structures
Wednesday 15.30-17.20
Location: Grand Ballroom B
Session Chair: Ke Yi
- Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures
Pankaj K. Agarwal; Kyle Fox; Kamesh Munagala; Abhinandan Nath - Space Lower Bounds for Itemset Frequency Sketches
Edo Liberty; Michael Mitzenmacher; Justin Thaler; Jonathan Ullman - Are Few Bins Enough: Testing Histogram Distributions
Clement Canonne - Range-Max Queries on Uncertain Data
Pankaj Agarwal; Nirman Kumar; Stavros Sintos; Subhash Suri - Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
Arturs Backurs; Krzysztof Onak.
POSTER SESSIONS
Session 1
Tuesday 3:30-5:00
Grand Ballroom A
- P1 - Minimization of Tree Pattern Queries
- P2 - Incremental View Maintenance For Collection Programming
- P3 - Aggregations over Generalized Hypertree Decompositions
- P4 - Bounded Query Rewriting Using Views
- P5 - Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable
- P6 - Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins
- P7 - On the Complexity of Inner Product Similarity Join
- P8 - Verification of Hierarchical Artifact Systems
- P9 - Recency-Bounded Verification of Dynamic Database-Driven Systems
- P10 - Making SQL Queries Correct on Incomplete Databases: A Feasibility Study
- P11 - Designing a Query Language for RDF: Marrying Open and Closed Worlds
- P12 - Towards Tight Bounds for the Streaming Set Cover Problem
- P13 - An Optimal Algorithm for Heavy Hitters in Insertion Streams and Related Problems
- P14 - Better Algorithms for Counting Triangles in Data Streams
- P15 - Locating a Small Cluster Privately
Session 2
Wednesday 3:30-5:00
Grand Ballroom A
- P16 - FAQ: Questions Asked Frequently
- P17 - Shortest Paths and Distances with Differential Privacy
- P18 - Schema validation via streaming circuits
- P19 - Variability in data streams
- P20 - Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors
- P21 - Efficient Top-k Indexing via General Reductions
- P22 - Anti-Persistence on Persistent Storage: History-Independent Sparse Arrays and Dictionaries
- P23 - Counting Answers to Existential Positive Queries: A Complexity Classification
- P24 - Worst-case Optimal Algorithms for Conjunctive Queries with Functional Dependencies
- P25 - Semantic Acyclicity Under Constraints
- P26 - Tractable Lineages on Treelike Instances: Limits and Extensions
- P27 - Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures
- P28 - Space Lower Bounds for Itemset Frequency Sketches
- P29 - Are Few Bins Enough: Testing Histogram Distributions
- P30 - Range-Max Queries on Uncertain Data
- P31 - Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
TUTORIAL SESSIONS
Tutorial 1
Tuesday 10:30-12:00
Location: Grand Ballroom B
Session Chair: Marcelo Arenas
- Data Management for Social Networking
Sara Cohen
Tutorial 2
Wednesday 8:30-10:00
Location: Grand Ballroom B
Session Chair: Pierre Senellart
- Logical Aspects of Massively Parallel and Distributed Systems
Frank Neven
