Multidimensional digital searching and some new parameters in tries

Abstract. Multidimensional digital searching ($M$-d tries) is analyzed from the view point of partial match retrieval. Our first result extends the analysis of Flajolet and Puech of the average cost of retrieval under the Bernoulli model to biased probabilities of symbols occurrences in a key. The second main finding concerns the variance of the cost of the retrieval in the unbiased case. This variance is of order $O(N^{1-s/M})$ where $N$ is the number of records stored in a $M$-d trie, and $s$ is the number of specified components in a query of size $M$. For $M=2$ and $s=1$ we present a detailed analysis of the variance, which identifies the constant at $\sqrt{N}$. This analysis, which is the central part of our paper, requires certain series transformation identities which go back to Ramanujan. In the Appendix we provide a Mellin transform approach to these results.

helmut@gauss.cam.wits.ac.za,

Peter.Kirschenhofer@tuwien.ac.at,
spa@cs.purdue.edu (Wojciech Szpankowski),

This paper is available in the Tex, Dvi, and PostScript format.

(Back to List of Papers)