Access Restriction

Author Szpankowski, Wojciech
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1990
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The Patricia trie is a simple modification of a regular trie. By eliminating unary branching nodes, the Patricia achieves better performance than regular tries. However, the question is: how much on the average is the Patricia better? This paper offers a thorough answer to this question by considering some statistics of the number of nodes examined in a successful search and an unsuccessful search in the Patricia tries. It is shown that for the Patricia containing $\textit{n}$ records the average of the successful search length $\textit{Sn}$ asymptotically becomes $1/\textit{h}1$ · ln $\textit{n}$ + $\textit{O}(1),$ and the variance of $\textit{Sn}$ is either var $\textit{Sn}$ = $\textit{c}$ · ln $\textit{n}$ + $\textit{0}(1)$ for an asymmetric Patricia or var $\textit{Sn}$ = $\textit{0}(1)$ for a symmetric Patricia, where $\textit{h}1$ is the entropy of the alphabet over which the Patricia is built and $\textit{c}$ is an explicit constant. Higher moments of $\textit{Sn}$ are also assessed. The number of nodes examined in an unsuccessful search $\textit{Un}$ is studied only for binary symmetric Patricia tries. We prove that the $\textit{m}th$ moment of the unsuccessful search length $\textit{EUmn}$ satisfies $lim\textit{n}→∞$ $\textit{EUmn}/log\textit{m}2\textit{n}$ = 1, and the variance of $\textit{Un}$ is var $\textit{Un}$ = 0.87907. These results suggest that Patricia tries are very well balanced trees in the sense that a random shape of Patriciatries resembles the shape of complete trees that are ultimately balanced trees.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1990-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 37
Issue Number 4
Page Count 21
Starting Page 691
Ending Page 711

Open content in new tab

   Open content in new tab
Source: ACM Digital Library