PODS 2019: Accepted Research Papers

  • Ranked Enumeration of Minimal Triangulations
    Noam Ravid (Technion); Dori Medini (Technion); Benny Kimelfeld (Technion)

  • Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory
    Hubie Chen (Birkbeck, University of London); Yuichi Yoshida (National Institute of Informatics)

  • Regularizing Conjunctive Features for Classification
    Pablo Barceló (Universidad de Chile); Alexander Baumgartner (Universidad de Chile); Victor Dalmau (Universitat Pompeu Fabra); Benny Kimelfeld (Technion)

  • Probabilistic Databases with an Infinite Open-World Assumption
    Martin Grohe (RWTH Aachen University); Peter Lindner (RWTH Aachen University)

  • The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems
    Hubie Chen (Birkbeck, University of London)

  • HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings
    Wolfgang Fischl (Vienna University of Technology); Georg Gottlob (University of Oxford); Davide Mario Longo (Vienna University of Technology); Reinhard Pichler (Vienna University of Technology)

  • Split-Correctness in Information Extraction
    Johannes Doleschal (University of Bayreuth & Hasselt University); Benny Kimelfeld (Technion); Wim Martens (University of Bayreuth); Yoav Nahshon (Technion); Frank Neven (Hasselt University & Transnational University of Limburg)

  • Decidable XPath Fragments in the Real World
    David Baelde (LSV, ENS Paris-Saclay & Inria Paris); Anthony Lick (LSV, ENS Paris-Saclay & CNRS, Université Paris-Saclay); Sylvain Schmitz (ENS Paris-Saclay)

  • Topology Dependent Bounds for (Some) FAQs
    Michael Langberg (University at Buffalo, SUNY); Shi Li (University at Buffalo, SUNY); Sai Vikneshwar Mani Jayaraman (University at Buffalo, SUNY); Atri Rudra (University at Buffalo, SUNY)

  • Containment of Shape Expression Schemas for RDF
    Sławek Staworko (INRIA); Piotr Wieczorek (University of Wroclaw)

  • The Space-Efficient Core of Vadalog
    Gerald Berger (Vienna University of Technology); Georg Gottlob (University of Oxford); Andreas Pieris (University of Edinburgh); Emanuel Sallinger (University of Oxford)

  • Attacking Diophantus: Solving a Special Case of Bag Containment
    George Konstantinidis (University of Southampton); Fabio Mogavero (University of Naples Federico II)

  • Robust Set Reconciliation via Locality Sensitive Hashing
    Michael Mitzenmacher (Harvard University); Tom Morgan (Harvard University)

  • Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model
    Piotr Indyk (Massachusetts Institute of Technology); Ali Vakilian (Massachusetts Institute of Technology)

  • Query Evaluation in Election Databases
    Benny Kimelfeld (Technion); Phokion Kolaitis (UC Santa Cruz & IBM Research Almaden); Muhammad Tibi (Technion)

  • Compiling Existential Positive Queries to Bounded-Variable Fragments
    Christoph Berkholz (Humboldt-Universität); Hubie Chen (Birkbeck, University of London)

  • On Functional Aggregate Queries with Additive Inequalities
    Mahmoud Abo Khamis (relationalAI Inc.); Ryan Curtin (relationalAI Inc.); Ben Moseley (CMU); Hung Ngo (relationalAI Inc.); Long Nguyen (University of Michigan); Dan Olteanu (University of Oxford); Maximilian Schleich (University of Oxford)

  • What Storage Access Privacy is Achievable with Small Overhead?
    Sarvar Patel (Google LLC); Giuseppe Persiano (Google LLC & University of Salerno); Kevin Yeo (Google LLC)

  • Weighted Reservoir Sampling from Distributed Streams
    Rajesh Jayaram (Carnegie Mellon University); Gokarna Sharma (Kent State University); Srikanta Tirthapura (Iowa State University); David P. Woodruff (Carnegie Mellon University)

  • Distributed and Streaming Linear Programming in Low Dimensions
    Sepehr Assadi (University of Pennsylvania); Nikolai Karpov (Indiana University Bloomington); Qin Zhang (Indiana University Bloomington)

  • Instance and Output Optimal Parallel Algorithms for Acyclic Joins
    Xiao Hu (Hong Kong University of Science and Technology); Ke Yi (Hong Kong University of Science and Technology)

  • Complexity Bounds for Relational Algebra over Document Spanners
    Dominik D. Freydenberger (Loughborough University); Benny Kimelfeld (Technion); Markus Kröll (Vienna University of Technology); Liat Peterfreund (Technion)

  • On the Enumeration Complexity of Unions of Conjunctive Queries
    Nofar Carmeli (Technion); Markus Kröll (Vienna University of Technology)

  • Better Sliding Windows Algorithms for Subadditive and Diversity Maximization
    Michele Borassi (Google); Alessandro Epasto (Google); Silvio Lattanzi (Google); Sergei Vassilvitskii (Google); Morteza Zadimoghaddam (Google)

  • Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
    Antoine Amarilli (LTCI, CNRS, Télécom ParisTech, Université Paris-Saclay); Pierre Bourhis (CRIStAL, CNRS UMR 9189, Inria Lille); Stefan Mengel (CNRS, CRIL UMR 8188); Matthias Niewerth (University of Bayreuth)

  • Counting Database Repairs under Primary Keys Revisited
    Marco Calautti (University of Edinburgh); Marco Console (University of Edinburgh); Andreas Pieris (University of Edinburgh)

  • Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
    Marcelo Arenas (Pontificia Universidad Católica de Chile); Luis Alberto Croquevielle (Pontificia Universidad Católica de Chile); Rajesh Jayaram (Carnegie Mellon University); Cristian Riveros (Pontificia Universidad Católica de Chile)

  • Reachability in Database-Driven Systems with Numerical Attributes under Recency Bounding
    Parosh Aziz Abdulla (Uppsala University); C. Aiswarya (Chennai Mathematical Institute); Mohamed Faouzi Atig (Uppsala University); Marco Montali (KRDB Research Centre, Free University of Bozen-Bolzano)

  • The Complexity of Counting Cycles in the Adjacency List Streaming Model
    John Kallaugher (University of Texas at Austin); Andrew McGregor (University of Massachusetts Amherst); Eric Price (University of Texas at Austin); Sofya Vorotnikova (University of Massachusetts Amherst)