Pierre Genevès

Research Director, Computer Science

Data-centric programming, data management, data science, analytics

Selected Papers by Topic

Publications

A more complete and searchable list of papers is also available.

Query Evaluation

On the Optimization of Recursive Relational Queries: Application to Graph Queries. Louis Jachiet, Pierre Genevès, Nils Gesbert and Nabil Layaïda. In Proceedings of the ACM SIGMOD International Conference on Management of Data, June, 2020 (SIGMOD'20). new
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-sigmod20,
	  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},
	  pdf =      {http://pierre.geneves.net/papers/mura-sigmod20.pdf},
      url =      {https://hal.inria.fr/hal-01673025v5/document},
      note = {\texttt{\href{https://hal.inria.fr/hal-01673025v5/document}{https://hal.inria.fr/hal-01673025v5/document}}},
      pages     = {681--697},
      publisher = ,
      year      = {2020},
      doi       = {10.1145/3318464.3380567}
	}
	

Tree Logic

Efficiently Deciding Mu-Calculus with Converse over Finite Trees. Pierre Genevès, Nabil Layaïda, Alan Schmitt and Nils Gesbert. ACM Transactions on Computational Logic Vol. 16(2), 2015 (TOCL'15).
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. Pierre Genevès and Alan Schmitt. 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. Hyeonseung Im, Pierre Genevès, Nils Gesbert and Nabil Layaïda. 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. Pierre Genevès and Nils Gesbert. 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. Nils Gesbert, Pierre Genevès and Nabil Layaïda. 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. Pierre Genevès, Nabil Layaïda and Vincent Quint. 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. Pierre Genevès, Nabil Layaïda and Alan Schmitt. 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. Raouf Kerkouche, Gergely Ács, Claude Castelluccia and Pierre Genevès. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2021 (UAI'21). new
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,
    title={Constrained Differentially Private Federated Learning for Low-bandwidth Devices},
    author={Raouf Kerkouche and Gergely \'{A}cs and Claude Castelluccia and Pierre Genev{\`{e}}s},
    year={2021},
    in = {UAI'21},
    booktitle = {Proceedings of the Conference on Uncertainty in Artificial Intelligence},
    pdf = {https://arxiv.org/pdf/2103.00342.pdf}
}
		
Scalable and Interpretable Predictive Models for Electronic Health Records. Amela Fejza, Pierre Genevès, Nabil Layaïda and Jean-Luc Bosson. In Proceedings of the 5th IEEE International Conference on Data Science and Advanced Analytics, October 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},
   year = {2018},
   note = {\href{https://hal.inria.fr/hal-01877742/file/med.pdf}{https://hal.inria.fr/hal-01877742/file/med.pdf}},
   url = {https://hal.inria.fr/hal-01877742/document}
}