Skip to Main content Skip to Navigation

Combinatoire analytique et algorithmique des ensembles de données.

Marianne Durand 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This thesis is about algorithms on data sets, from the point of view of analytic combinatorics. Its content is based on three main directions: jumplists and bivariate asymptotic, random probing hashing and probabilistic counting. A jumplist is a data structure inspired from skiplists, and close to binary search trees. The study of this structure leads to a bivariate asymptotic problem, with coalescing singularities. Random probing hashing is an algorithm that handles the problem ofcollisions in a hash table. In the context studied here, that is hashing with buckets, we find the average, and all the other moments of the construction cost of the table. The original probabilistic counting algorithms Loglog and super Loglog tell how to estimate the cardinality of a data set using a kilobyte of memory, with a precision of about 3%.
Document type :
Complete list of metadatas
Contributor : Ecole Polytechnique <>
Submitted on : Wednesday, July 21, 2010 - 11:07:16 AM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on: : Friday, October 22, 2010 - 3:38:34 PM


  • HAL Id : pastel-00000810, version 1



Marianne Durand. Combinatoire analytique et algorithmique des ensembles de données.. Informatique [cs]. Ecole Polytechnique X, 2004. Français. ⟨pastel-00000810⟩



Record views


Files downloads