Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
https://hal.inria.fr/hal-01197232
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:54:53 PM
Last modification on : Tuesday, March 7, 2017 - 3:18:52 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:34:07 AM

File

Vignette du document
dmAQ0130.pdf
Publisher files allowed on an open archive

Identifiers

  • 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. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.381-398. ⟨hal-01197232⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

509

Files downloads

560

 

Contact                    Legal Notice                    Personal Data