XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Jacquet P, McVey B, Szpankowski W. Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth. JIRSS. 2004; 3 (2) :139-148
URL: http://jirss.irstat.ir/article-1-108-en.html

Abstract:   (5967 Views)
Suffix trees are the most frequently used data structures in algorithms on words. In this paper, we consider the depth of a compact suffix tree, also known as the PAT tree, under some simple probabilistic assumptions. For a biased memoryless source, we prove that the limiting distribution for the depth in a PAT tree is the same as the limiting distribution for the depth in a PATRICIA trie, even though the PATRICIA trie is constructed from statistically independent strings. As a result, we show that the limiting distribution for the depth in a PAT tree built over n suffixes is normal.
Full-Text [PDF 161 kb]   (1188 Downloads)    
Subject: 60: Probability theory and stochastic processes
Received: 2011/08/26 | Accepted: 2015/09/12

Add your comments about this article : Your username or email:
Write the security code in the box

© 2015 All Rights Reserved | Journal of The Iranian Statistical Society

Designed & Developed by : Yektaweb