Analysis of Tries that Store Prefixing Keys.
MetadataShow full item record
Tries are data structures for representing sets of string keys. Although tries can be readily adapted to represent unrestricted sets of keys, the analysis of tries built from sets that include prefixing keys (which are keys that are prefixes of other keys in the set) appears to have remained untouched until now. The exact expectations of the time and space requirements of the retrieval algorithms of several trie varieties built from unrestricted finite sets of keys are computed in this paper. We present a unified approach to the derivation of these expectations which are computed with respect to a probabilistic model that takes into account sample sets containing prefixing keys.