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.