Selected Papers by Topic
A more complete and searchable list of papers is also available.
Query Evaluation
On the Optimization of Recursive Relational Queries: Application to Graph Queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data, June ACM, 2020 (SIGMOD'20). 
|
| Abstract: Graph databases have received a lot of attention as they are particularly useful in many applications such as social networks, life sciences and the semantic web. Various languages have emerged to query graph databases, many of which embed forms of recursion which reveal essential for navigating in graphs. The relational model has benefited from a huge body of research in the last half century and that is why many graph databases rely on techniques of relational query engines. Since its introduction, the relational model has seen various attempts to extend it with recursion and it is now possible to use recursion in several SQL or Datalog based database systems. The optimization of recursive queries remains, however, a challenge. We propose mu-RA, a variation of the Relational Algebra equipped with a fixpoint operator for expressing recursive relational queries. mu-RA can notably express unions of conjunctive regular path queries. Leveraging the fact that this fixpoint operator makes recursive terms more amenable to algebraic transformations, we propose new rewrite rules. These rules makes it possible to generate new query execution plans, that cannot be obtained with previous approaches. We present the syntax and semantics of mu-RA, and the rewriting rules that we specifically devised to tackle the optimization of recursive queries. We report on practical experiments that show that the newly generated plans can provide significant performance improvements for evaluating recursive queries over graphs. |
BibTeX:
@inproceedings{geneves-sigmod2020,
author = {Louis Jachiet and Pierre Genevès and Nils Gesbert and Nabil Layaïda},
title = {On the Optimization of Recursive Relational Queries: Application to Graph Queries},
booktitle = {Proceedings of the ACM SIGMOD International Conference on Management of Data},
publisher = {ACM},
year = {2020},
pages = {681--697},
doi = {10.1145/3318464.3380567}
}
|
Tree Logic
| Efficiently Deciding Mu-Calculus with Converse over Finite Trees. ACM Transactions on Computational Logic Vol. 16(2), 2015 (TOCL'15).
[Abstract] [PDF] [doi] [ACM DL] [Website] [Implementation] [BibTeX] |
| Abstract: A tree logic and an efficient solver for checking satisfiability of a formula of the logic... |
BibTeX:
@article{geneves-tocl2015,
author = {Pierre Genevès and Nabil Layaïda and Alan Schmitt and Nils Gesbert},
title = {Efficiently Deciding Mu-Calculus with Converse over Finite Trees},
journal = {ACM Trans. Comput. Log.},
year = {2015},
volume = {16},
number = {2},
pages = {16},
note = {\href{https://hal.inria.fr/hal-00868722v5/document}{https://hal.inria.fr/hal-00868722v5}},
doi = {10.1145/2724712}
}
|
| Expressive Logical Combinators for Free. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, 2015 (IJCAI'15). |
| Abstract: Combinators form a succinct and expressive language without increasing complexity. |
BibTeX:
@inproceedings{geneves-ijcai2015b,
author = {Pierre Genevès and Alan Schmitt},
title = {Expressive Logical Combinators for Free},
booktitle = {Proceedings of the 24th International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {311--317},
url = {http://ijcai.org/Abstract/15/050}
}
|
Type Systems
| Backward type inference for XML queries. Theoretical Computer Science Vol. 823, 2020 (TCS'20). |
| Abstract: Although XQuery is a statically typed, functional query language for XML data, some of its features such as upward and horizontal XPath axes are typed imprecisely. The main reason is that while the XQuery data model allows us to navigate upwards and between siblings from a given XML node, the type model, e.g., regular tree types, can describe only the subtree structure of the given node. To alleviate this limitation, precise forward type inference systems for XQuery were recently proposed using an extended regular type language that can describe not only a given XML node but also its context. In this paper, as a different approach, we propose a novel backward type inference system for XQuery, based on a type language extended with logical formulas. Our backward type inference system provides an exact typing result for XPath axes and a sound typing result for XQuery expressions. |
BibTeX:
@article{geneves-tcs2020,
author = {Hyeonseung Im and Pierre Genevès and Nils Gesbert and Nabil Layaïda},
title = {Backward type inference for XML queries},
journal = {Theoretical Computer Science},
year = {2020},
volume = {823},
pages = {69--99},
url = {http://www.sciencedirect.com/science/article/pii/S0304397520301791},
doi = {10.1016/j.tcs.2020.03.020}
}
|
| XQuery and Static Typing: Tackling the Problem of Backward Axes. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming, 2015 (ICFP'15). |
| Abstract: A static type-checker for XQuery programs, that improves the XQuery standard type system, by solving the long-standing problem of typing backward axes. The prototype jointly uses two solvers. |
BibTeX:
@inproceedings{geneves-icfp2015,
author = {Pierre Genevès and Nils Gesbert},
title = {XQuery and Static Typing: Tackling the Problem of Backward Axes},
booktitle = {Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (ICFP)},
year = {2015},
pages = {88--100},
note = {\href{https://hal.inria.fr/hal-01082635v3/document}{https://hal.inria.fr/hal-01082635v3/}},
doi = {10.1145/2784731.2784746}
}
|
| A Logical Approach to Deciding Semantic Subtyping. ACM Transactions on Programming Language and Systems Vol. 38(1), 2015 (TOPLAS'15). (Preliminary results were presented at the 16th International Conference on Functional Programming, 2011 (ICFP'11) |
BibTeX:
@article{geneves-toplas2015,
author = {Nils Gesbert and Pierre Genevès and Nabil Layaïda},
title = {A Logical Approach to Deciding Semantic Subtyping},
journal = {ACM Trans. Program. Lang. Syst.},
year = {2015},
volume = {38},
number = {1},
pages = {3},
note = {\href{https://hal.inria.fr/hal-00848023v2/document}{https://hal.inria.fr/hal-00848023v2}},
url = {http://doi.acm.org/10.1145/2812805},
doi = {10.1145/2812805}
}
|
Static Analysis
| On the Analysis of Cascading Style Sheets. In Proceedings of the 21st International Conference on World Wide Web, April 2012 (WWW'12). |
| Abstract: We present an original method for proving the absence of errors in CSS style sheets. |
BibTeX:
@inproceedings{geneves-www2012,
author = {Pierre Genevès and Nabil Layaïda and Vincent Quint},
title = {On the Analysis of Cascading Style Sheets},
booktitle = {Proceedings of the 21st World Wide Web Conference},
year = {2012},
pages = {809-818},
note = {\href{https://hal.inria.fr/hal-00643075/document}{https://hal.inria.fr/hal-00643075}},
doi = {10.1145/2187836.2187946}
}
|
| Efficient Static Analysis of XML Paths and Types. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, California, USA, 2007 (PLDI'07). |
| Abstract: A new logic for reasoning over finite trees is proposed. This logic currently offers the best balance known between expressivity and complexity for decidability. It is as expressive as monadic second-order logic whereas its satisfiability is shown decidable in time complexity 2^O(n) w.r.t. size n of the formula. We present an effective algorithm in practice using symbolic techniques (BDDs), and use it for the static analysis of XPath queries in the presence of regular tree types, including XPath typing. |
BibTeX:
@inproceedings{geneves-pldi2007,
author = {Pierre Genevès and Nabil Layaïda and Alan Schmitt},
title = {Efficient Static Analysis of XML Paths and Types},
booktitle = {Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)},
year = {2007},
pages = {342--351},
doi = {10.1145/1250734.1250773}
}
|
Data Science Applications
| Constrained Differentially Private Federated Learning for Low-bandwidth Devices. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence Vol. 161 AUAI Press, 2021 (UAI'21).
|
| Abstract: Federated learning becomes a prominent approach when different entities want to learn collaboratively a common model without sharing their training data. However, Federated learning has two main drawbacks. First, it is quite bandwidth inefficient as it involves a lot of message exchanges between the aggregating server and the participating entities. This bandwidth and corresponding processing costs could be prohibitive if the participating entities are, for example, mobile devices. Furthermore, although federated learning improves privacy by not sharing data, recent attacks have shown that it still leaks information about the training data. This paper presents a novel privacy-preserving federated learning scheme. The proposed scheme provides theoretical privacy guarantees, as it is based on Differential Privacy. Furthermore, it optimizes the model accuracy by constraining the model learning phase on few selected weights. Finally, as shown experimentally, it reduces the upstream and downstream bandwidth by up to 99.9% compared to standard federated learning, making it practical for mobile systems. |
BibTeX:
@inproceedings{geneves-uai2021,
author = {Raouf Kerkouche and Gergely Ács and Claude Castelluccia and Pierre Genevès},
title = {Constrained Differentially Private Federated Learning for Low-bandwidth Devices},
booktitle = {Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence},
publisher = {AUAI Press},
year = {2021},
volume = {161},
pages = {1756--1765}
}
|
| Scalable and Interpretable Predictive Models for Electronic Health Records. In Proceedings of the 5th IEEE International Conference on Data Science and Advanced Analytics, October IEEE, 2018 (DSAA'18). |
| Abstract: We consider the problem of predicting important clinical outcomes such as inpatient mortality, based on EHR data. We develop risk prediction models that leverage the evolution of drugs served during hospital stays. We report on lessons learned through practical experiments with real EHR data from more than one million of patients admitted to US hospitals, which is, to the best of our knowledge, one of the largest such experimental study conducted so far. |
BibTeX:
@inproceedings{geneves-dsaa2018,
author = {Amela Fejza and Pierre Genevès and Nabil Layaïda and Jean-Luc Bosson},
title = {Scalable and Interpretable Predictive Models for Electronic Health Records},
booktitle = {Proceedings of the 5th IEEE International Conference on Data Science and Advanced Analytics},
publisher = {IEEE},
year = {2018},
pages = {341--350},
doi = {10.1109/DSAA.2018.00045}
}
|