Multivariate holonomy, applications in combinatories, and analysis of algorithms. - Archive ouverte HAL Access content directly
Theses Year : 2004

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

Combinatoire analytique et algorithmique des ensembles de données.

(1)
1
Marianne Durand
  • Function : Author

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%.
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 and versions

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

Identifiers

  • HAL Id : pastel-00000810 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More