Geodesic
The variance for partial match retrievals in $k$-dimensional bucket digital trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2010_special_258_a32,
     author = {Fuchs, Michael},
     title = {The variance for partial match retrievals in $k$-dimensional bucket digital trees},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2796},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2796/}
}
TY  - JOUR
AU  - Fuchs, Michael
TI  - The variance for partial match retrievals in $k$-dimensional bucket digital trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2796/
DO  - 10.46298/dmtcs.2796
LA  - en
ID  - DMTCS_2010_special_258_a32
ER  - 
%0 Journal Article
%A Fuchs, Michael
%T The variance for partial match retrievals in $k$-dimensional bucket digital trees
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2796/
%R 10.46298/dmtcs.2796
%G en
%F DMTCS_2010_special_258_a32
Fuchs, Michael. The variance for partial match retrievals in $k$-dimensional bucket digital trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2796. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2796/

Cité par Sources :