DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

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

Michael Fuchs

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.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional