77 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Département d'InformatiqueFR13 papers
- École Normale Supérieure - PSLFR12 papers
- Centre National de la Recherche ScientifiqueFR5 papers
- Institut national de recherche en sciences et technologies du numériqueFR4 papers
- Laboratoire Traitement et Communication de l’InformationFR4 papers
- Université Paris Sciences et LettresFR3 papers
- Laboratoire d'Informatique Gaspard-MongeFR2 papers
- Télécom ParisFR2 papers
- Unité de Mathématiques Pures et AppliquéesFR2 papers
- Université Gustave EiffelFR2 papers
- University of EdinburghGB2 papers
- Aalto UniversityFI1 paper
15 papers
PG-Schema: Schemas for Property Graphs
Renzo Angles, Angela Bonifati, Stefania Dumbrava +18
Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a ne…
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Complexity Analysis
Nofar Carmeli, Luc Segoufin
Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-jo…
Fast Rate Learning in Stochastic First Price Bidding
Juliette Achddou, Olivier Cappé, Aurélien Garivier
First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. As far as learning is concerned, first-price auctio…
Tameness and the power of programs over monoids in DA
Nathan Grosshans, Pierre Mckenzie, Luc Segoufin
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class . Here we make progress in understanding…
Handling SQL Nulls with Two-Valued Logic
Leonid Libkin, Liat Peterfreund
The design of SQL is based on a three-valued logic (3VL), rather than the familiar Boolean logic. 3VL adds a truth value unknown to true and false to handle nulls. Viewed as indisp…
A Comparative Study of Gamma Markov Chains for Temporal Non-Negative Matrix Factorization
Louis Filstroff, Olivier Gouvert, Cédric Févotte +1
Non-negative matrix factorization (NMF) has become a well-established class of methods for the analysis of non-negative data. In particular, a lot of effort has been devoted to pro…
Algorithms for Non-Stationary Generalized Linear Bandits
Yoan Russac, Olivier Cappé, Aurélien Garivier
The statistical framework of Generalized Linear Models (GLM) can be applied to sequential problems involving categorical or ordinal rewards associated, for instance, with clicks, l…
Weighted Linear Bandits for Non-Stationary Environments
Yoan Russac, Claire Vernade, Olivier Cappé
We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regressi…
A Single Approach to Decide Chase Termination on Linear Existential Rules
Michel Leclere, Marie-Laure Mugnier, Michael Thomazo +1
Existential rules, long known as tuple-generating dependencies in database theory, have been intensively studied in the last decade as a powerful formalism to represent ontological…
BelMan: Bayesian Bandits on the Belief--Reward Manifold
Debabrota Basu, Pierre Senellart, Stéphane Bressan
We propose a generic, Bayesian, information geometric approach to the exploration--exploitation trade-off in multi-armed bandit problems. Our approach, BelMan, uniformly supports p…
First-order queries on classes of structures with bounded expansion
Wojtek Kazana, Luc Segoufin
We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree,…
Connecting Width and Structure in Knowledge Compilation (Extended Version)
Antoine Amarilli, Mikaël Monet, Pierre Senellart
Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it…
On the Height of Towers of Subsequences and Prefixes
Štěpán Holub, Tomáš Masopust, Michaël Thomazo
A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. The height of the tower is the number of word…
Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version)
Antoine Amarilli, Pierre Bourhis, Mikaël Monet +1
We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We introduce a new Datalog frag…
Top-k Querying of Unknown Values under Order Constraints (Extended Version)
Antoine Amarilli, Yael Amsterdamer, Tova Milo +1
Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a…