HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

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

Identifiers

Collections

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⟩

Share

Metrics

Record views

30

Files downloads

317