Extending the Flajolet-Regnier-Sotteau Method of Trie Analysis to the Prefix Model.

Abstract

Recent work of Flajolet, Regnier and Sotteau has presented a systematic approach to the analysis of tries through generating functions. We extend their approach to a probabilitic model that, unlike other models used for the analysis of tries, takes into account sample sets containing keys that are prefixes of other keys in the set. As the main application of this extension, we find the exact average running time of two algorithms for computing set intersections. These algorithms are based on the representation of a set of binary string keys as a full endmarker trie and also as a compact endmarker trie.