18 July 2023, 10:30-11:30. ENS, room Emmy Noether, on level -2 of Aile Rataud. Distinct Elements in Streams: An Algorithm for the (Text) Book Abstract: Given a data stream of m elements, the Distinct Elements problem is to estimate the number of distinct elements in the stream. Distinct Elements has…
Postponed. ENS, S16. On Approximating Total Variation Distance Abstract: Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. we introduce and study the problem of computing the TV distance between two product distributions over the domain {0,1}^n. In particular, we establish the following results. The…
26 May 2023, 10:30-11:30. ENS, S16. Normalisations of Existential Rules: Not so Innocuous! Existential rules are an expressive knowledge representation language mainly developed to query data. In the literature, they are often supposed to be in some normal form that simplifies technical developments. For instance, a common assumption is that…
28 November 2022, 14:00-15:00. ENS, S16. Detection of Anomalies and Identification of their Precursors in Large Data Series Collections Extensive collections of data series are becoming a reality in many scientific and social domains, such as environmental sciences, astrophysics, neurosciences, and engineering. Informally, a data series is an ordered sequence…
4 November 2022, 10:30-11:30. ENS, S16. Datalog: Optimizations and Extensions Modern data analytics requires iteration, yet relational database engines are mostly optimized for non-recursive queries. SQL supports only a limited form of recursion. A better formalism for recursive queries is datalog, which has some elegant properties (recursion always terminates), and…
3 June 2022, 10:30-11:30. ENS, Hauts du DI. Querying inconsistent prioritized data with ORBITS: Algorithms, implementation, and experiments We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases, which consist of a logical theory, a set of facts, and a priority relation between conflicting facts. We consider three…
20 May 2022, 10:30-11:30. ENS S16. Algorithm for consistent query answering under primary key constraints Databases often have constraints. One of the basic constraints is the “primary key constraint” which states there can be at most one tuple for every primary key. However, these days it is common to have…
12 April 2022, 10:30-11:30. ENS, S16 The Semiring-Based Provenance Framework for Graph Databases The growing amount of data collected by sensors or generated by human interaction has led to an increasing use of graph databases, an efficient model for representing intricate data. Techniques to keep track of the history of…
8 April 2022, 10:30-11:30. ENS, S16 Capturing Homomorphism-Closed Decidable Queries with Existential Rules Existential rules are a well studied ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize…
Debabrota Basu, Inria Lille. 11 March 2022, 10:30-11:30. ENS S16. Verifying and Explaining Unfairness of Machine Learning Algorithms In recent years, machine learning (ML) algorithms have been deployed in safety-critical and high-stake decision-making, where the fairness or unbiasedness of algorithms bears significant importance. Fairness in ML centres on detecting bias…
