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