Combinatoire analytique et algorithmique des ensembles de données. - PASTEL - Thèses en ligne de ParisTech Accéder directement au contenu
Thèse Année : 2004

Multivariate holonomy, applications in combinatories, and analysis of algorithms.

Combinatoire analytique et algorithmique des ensembles de données.

Marianne Durand
  • Fonction : Auteur

Résumé

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%.
Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.
Fichier principal
Vignette du fichier
marianneDurand2.pdf (2.72 Mo) Télécharger le fichier

Dates et versions

pastel-00000810 , version 1 (21-07-2010)

Identifiants

  • HAL Id : pastel-00000810 , version 1

Citer

Marianne Durand. Combinatoire analytique et algorithmique des ensembles de données.. Informatique [cs]. Ecole Polytechnique X, 2004. Français. ⟨NNT : ⟩. ⟨pastel-00000810⟩
455 Consultations
595 Téléchargements

Partager

Gmail Facebook X LinkedIn More