The variance for partial match retrievals in $k$-dimensional bucket digital trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2010

The variance for partial match retrievals in $k$-dimensional bucket digital trees

Résumé

The variance of partial match queries in $k$-dimensional tries was investigated in a couple of papers in the mid-nineties, the resulting analysis being long and complicated. In this paper, we are going to re-derive these results with a much easier approach. Moreover, our approach works for $k$-dimensional PATRICIA tries, $k$-dimensional digital search trees and bucket versions as well.
Fichier principal
Vignette du fichier
dmAM0118.pdf (296.12 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01185595 , version 1 (20-08-2015)

Identifiants

Citer

Michael Fuchs. The variance for partial match retrievals in $k$-dimensional bucket digital trees. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.261-276, ⟨10.46298/dmtcs.2796⟩. ⟨hal-01185595⟩

Collections

TDS-MACS
30 Consultations
447 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More