HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

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

Abstract : 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/hal-01185595
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:33:44 PM
Last modification on : Tuesday, March 7, 2017 - 3:08:08 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:48:05 AM

### File

dmAM0118.pdf
Publisher files allowed on an open archive

### Citation

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⟩

Record views