PODS 2016: Accepted Papers
-
Are Few Bins Enough: Testing Histogram Distributions
Clement Canonne (Columbia Univ.)
-
Verification of Hierarchical Artifact Systems
Alin Deutsch (UCSD); Yuliang Li (UCSD); Victor Vianu (UCSD)
-
Anti-Persistence on Persistent Storage: History-Independent Sparse Arrays and Dictionaries
Michael Bender (Stony Brook Univ.); Jon Berry (Sandia National Labs); Rob Johnson (Stony Brook Univ.); Thomas M. Kroeger (Sandia National Labs); Samuel McCauley (Stony Brook Univ.); Cynthia A. Phillips (Sandia National Labs); Bertrand Simon (LIP, ENS de Lyon); Shikha Singh (Stony Brook Univ.); David Zage (Sandia National Labs)
-
Variability in Data Streams
David Felber; Rafail Ostrovsky (UCLA)
-
Space Lower Bounds for Itemset Frequency Sketches
Edo Liberty (Yahoo Labs); Michael Mitzenmacher (Harvard Univ.); Justin Thaler (Yahoo Labs); Jonathan Ullman (Northeastern Univ.)
-
Counting Answers to Existential Positive Queries: A Complexity Classification
Hubie Chen (Universidad del Pais Vasco and Ikerbasque); Stefan Mengel (CNRS)
-
FAQ: Questions Asked Frequently
Mahmoud Abo Khamis (Logicblox and Univ. at Buffalo); Hung Ngo (Logicblox and Univ. at Buffalo); Atri Rudra (Univ. at Buffalo)
-
Range-Max Queries on Uncertain Data
Pankaj Agarwal (Duke Univ.); Nirman Kumar (UCSB); Stavros Sintos (Duke Univ.); Subhash Suri (UCSB)
-
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors
Vladimir Braverman (John Hopkins Univ.); Stephen Chestnut (ETH Zurich); David Woodruff (IBM); Lin Yang (John Hopkins Univ.)
-
Better Algorithms for Counting Triangles in Data Streams
Andrew McGregor (UMass); Sofya Vorotnikova (UMass); Hoa Vu (UMass)
-
An Optimal Algorithm for Heavy Hitters in Insertion Streams and Related Problems
Arnab Bhattacharyya (Indian Institute of Science, Bangalore); Palash Dey (Indian Institute of Science, Bangalore); David Woodruff (IBM)
-
On the Complexity of Inner Product Similarity Join
Thomas Dybdahl Ahle (IT Univ. of Copenhagen); Rasmus Pagh (IT Univ. of Copenhagen); Ilya Razenshteyn (CSAIL, MIT); Francesco Silvestri (IT Univ. of Copenhagen)
-
Incremental View Maintenance For Collection Programming
Christoph Koch (EPFL); Daniel Lupei (EPFL); Val Tannen (UPenn)
-
Towards Tight Bounds for the Streaming Set Cover Problem
Sariel Har-Peled (UIUC); Piotr Indyk (MIT); Sepideh Mahabadi (MIT); Ali Vakilian (MIT)
-
Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable
Tomasz Gogacz (Univ. of Wroclaw); Jerzy Marcinkowski (Univ. of Wroclaw)
-
Worst-case Optimal Algorithms for Conjunctive Queries with Functional Dependencies
Mahmoud Abo Khamis (Logicblox and Univ. at Buffalo); Hung Ngo (Logicblox and Univ. at Buffalo); Dan Suciu (Logicblox and Univ. of Washington)
-
Efficient Top-k Indexing via General Reductions
Rahul Saladi (Univ. of Minnesota); Yufei Tao (Chinese Univ. of Hong Kong)
-
Shortest Paths and Distances with Differential Privacy
Adam Sealfon (MIT)
-
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins
Xiao Hu (HKUST); Ke Yi (HKUST)
-
Aggregations over Generalized Hypertree Decompositions
Manas Joglekar (Stanford Univ.); Rohan Puttagunta (Stanford Univ.); Chris Re (Stanford Univ.)
-
Bounded Query Rewriting Using Views
Yang Cao (Univ. of Edinburgh); Wenfei Fan (Univ. of Edinburgh); Floris Geerts (Univ. of Antwerp); Ping Lu (Beihang Univ.)
-
Minimization of Tree Pattern Queries
Wojciech Czerwinski (Univ. of Warsaw); Wim Martens (Univ. of Bayreuth); Matthias Niewerth (Univ. of Niewerth); Pawel Parys (Univ. of Warsaw)
-
Locating a Small Cluster Privately
Kobbi Nissim (Ben-Gurion Univ. and CRCS@Harvard); Uri Stemmer (Ben-Gurion Univ.); Salil Vadhan (Harvard Univ.)
-
Making SQL Queries Correct on Incomplete Databases: A Feasibility Study
Paolo Guagliardo (Univ. of Edinburgh); Leonid Libkin (Univ. of Edinburgh)
-
Designing a Query Language for RDF: Marrying Open and Closed Worlds
Martin Ugarte (Universite Libre de Bruxelles); Marcelo Arenas (PUC Chile)
-
Schema Validation via Streaming Circuits
Filip Murlak (Univ. of Warsaw); Charles Paperman (Univ. of Warsaw); Michal Pilipczuk (Univ. of Warsaw)
-
Recency-Bounded Verification of Dynamic Database-Driven Systems
Parosh Aziz Abdulla (Uppsala Univ.); C. Aiswarya (Uppsala Univ.); Mohamed Faouzi Atig (Uppsala Univ.); Marco Montali (Free Univ. of Bolzano); Othmane Rezine (Uppsala Univ.)
-
Tractable Lineages on Treelike Instances: Limits and Extensions
Antoine Amarilli (Institut Telecom, Telecom ParisTech, CNRS LTCI); Pierre Bourhis (CNRS CRIStAL); Pierre Senellart (Institut Mines - Telecom, Telecom ParisTech, CNRS LTCI)
-
Semantic Acyclicity Under Constraints
Pablo Barcelo (Univ. of Chile); Georg Gottlob (Univ. of Oxford); Andreas Pieris (Vienna Univ. of Technology)
-
Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures
Pankaj K. Agarwal (Duke Univ.); Kyle Fox (Duke Univ.); Kamesh Munagala (Duke Univ.); Abhinandan Nath (Duke Univ.)
-
Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
Arturs Backurs (MIT); Krzysztof Onak (IBM)
