 |
Discrete Mathematics & Theoretical Computer Science |
Michael Fuchs - The variance for partial match retrievals in $k$-dimensional bucket digital trees
dmtcs:2796 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2796The variance for partial match retrievals in $k$-dimensional bucket digital treesConference paper
Authors: Michael Fuchs 
1
- 1 Department of Applied Mathematics [Hsinchu]
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.
Source: HAL:hal-01185595v1
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [en] $k$-dimensional digital trees, partial match retrieval, variance, JS-admissibility, Mellin transform
Consultation statistics
This page has been seen 297 times.
This article's PDF has been downloaded 265 times.