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 :
Theses
Complete list of metadatas

https://pastel.archives-ouvertes.fr/pastel-00000810
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

Identifiers

  • HAL Id : pastel-00000810, version 1

Collections

Citation

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

Share

Metrics

Record views

553

Files downloads

550