RECORDINALITY: les grands flux de données vus comme des permutations aléatoires
Talk that introduces a novel, implementable data streaming algorithm for cardinality estimation, that uses
Dirichlet Random Samplers for Multiplicative Structures
Talk that introduces novel combinatorial object samplers, for objects in which the size is multiplicative rather than additive (such as for certain kinds of tilings, factorizations, and trees). With Olivier Bodini.
An Optimal Cardinality Estimation Algorithm Based on Order Statistics and Its Full Analysis
Talk that introduced a novel, practically useful cardinality estimation, which is both optimal and fully analyzed, engineered with low cardinality distortion fixes, with its limit distribution (see sequence of plots): A full characterization of the probability distribution — a gamma distribution — of the algorithm’s output.
Optimal Partial Tiling of Manhattan Polyominoes
Talk that introduced a novel (greedy) algorithm for the partial tiling of Manhattan polyominoes, linear in the number of columns, with a correctness proof that uses max-flow graphs. With Olivier Bodini.