An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms Original Research Article

The trie, or digital tree, is a standard data structure for representing sets of strings over a given finite alphabet. Since , these data structures have been extensively studied and analyzed. In this paper, we present an algebraic approach to the analysis of average storage and average time required by the retrieval algorithms of trie structures under the prefix model. This approach extends the work of Flajolet et al. for other models which, unlike the prefix model, assume that no key in a sample set is the prefix of another. As the main application, we analyze the average running time of two algorithms for computing set intersections. Résumé Le trie, ou trie numérique, est une structure de données standard pour représenter des ensembles de mots sur un alphabet fini donné. Depuis le travail original de , ces structures de données ont été intensivement étudiées et analysées. Dans cet article, nous présentons une approche algébrique de lʹanalyse de lʹespace moyen et du temps moyen requis par les algorithmes de recherche dans les structures de trie utilisant le modèle préfixe. Cette approche étend le travail de Flajolet et al. à dʹautres modèles, qui, contrairement au modèle préfixe, supposent quʹaucune clef dans un échantillon nʹest le préfixe dʹune autre. Comme principale application, nous analysons le temps dʹéxćution moyen de deux algorithmes pour le calcul dʹintersections dʹensembles.