On the Number of 2-Protected Nodes in Tries and Suffix Trees

Jeffrey Gaither 1 Yushi Homma 1 Mark Sellke 1 Mark Daniel Ward 2
1 Department of mathematics Purdue University
2 Purdue University - Department of Statistics
Abstract : We use probabilistic and combinatorial tools on strings to discover the average number of 2-protected nodes in tries and in suffix trees. Our analysis covers both the uniform and non-uniform cases. For instance, in a uniform trie with $n$ leaves, the number of 2-protected nodes is approximately 0.803$n$, plus small first-order fluctuations. The 2-protected nodes are an emerging way to distinguish the interior of a tree from the fringe.
Keywords : retrieval trees suffix trees Poissonization Mellin transforms pattern matching
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.381-398, 2012, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01197232
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:53
Dernière modification le : mardi 7 mars 2017 - 15:18:52
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:34:07

Fichier

dmAQ0130.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01197232, version 1

Collections

INSMI | TDS-MACS

Citation

Jeffrey Gaither, Yushi Homma, Mark Sellke, Mark Daniel Ward. On the Number of 2-Protected Nodes in Tries and Suffix Trees. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.381-398, 2012, DMTCS Proceedings. 〈hal-01197232〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

351

Téléchargements de fichiers

177

Contact


archive-ouverte@inria.fr