Ordinary digital search trees (DSTs) stores one word in each of its internal nodes and leaves, but a DST with paging size allows storing words in the leaves, which corresponds to pages in auxiliary storage. In this paper, we analyse the average number of nodes, the average node-wise path length and 2-protected nodes in DSTs with paging size . We utilize recurrence relations, analytical Poissonization and de-Poissonization, the Mellin transform, and complex analysis. We also compare the storage usage in paged DSTs to that in DSTs. For example, for , the approximate average number of nodes in paged DSTs is, respectively, 82%, 67%, 55%, 47%, 41% of the size of DSTs (when ). Thus the results are nontrivial and interesting for computer scientists.
Accepté le :
DOI : 10.1051/ita/2017002
Mots-clés : Random trees, paged digital search trees, singularity analysis
@article{ITA_2017__51_1_7_0,
author = {Javanian, Mehri and Vahidi-asl, Mohammad Q.},
title = {Analysis of digital search trees incorporated with paging},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {7--15},
publisher = {EDP-Sciences},
volume = {51},
number = {1},
year = {2017},
doi = {10.1051/ita/2017002},
mrnumber = {3678026},
zbl = {1369.05033},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2017002/}
}
TY - JOUR AU - Javanian, Mehri AU - Vahidi-asl, Mohammad Q. TI - Analysis of digital search trees incorporated with paging JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2017 SP - 7 EP - 15 VL - 51 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2017002/ DO - 10.1051/ita/2017002 LA - en ID - ITA_2017__51_1_7_0 ER -
%0 Journal Article %A Javanian, Mehri %A Vahidi-asl, Mohammad Q. %T Analysis of digital search trees incorporated with paging %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2017 %P 7-15 %V 51 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2017002/ %R 10.1051/ita/2017002 %G en %F ITA_2017__51_1_7_0
Javanian, Mehri; Vahidi-asl, Mohammad Q. Analysis of digital search trees incorporated with paging. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 7-15. doi : 10.1051/ita/2017002. http://www.numdam.org/articles/10.1051/ita/2017002/
and , Notes on Protected Nodes in Digital Search Trees. Appl. Math. Lett. 25 (2012) 1025–1028. | DOI | MR | Zbl
, and , Mellin Transforms and Asymptotics: Harmonic Sums. Theor. Comput. Sci. 144 (1995) 3–58. | DOI | MR | Zbl
, and , Patterns in Random Binary Search Trees. Random Struct. Algorithms. 11 (1997) 223–244. | DOI | MR | Zbl
and , Generalized Digital Trees and Their Difference-Differential Equations. Random Struct. Algorithms 3 (1992) 305–320. | DOI | MR | Zbl
, and , On 2-Protected Nodes in Random Digital Trees. Theor. Comput. Sci. 622 (2016) 111–122. | DOI | MR | Zbl
and , Page Usage in a Quadtree Index. BIT 32 (1992) 384–402. | DOI | MR | Zbl
, and , Asymptotic Variance of Random Symmetric Digital Search Trees. Discrete Math. Theor. Comput. Sci. 12 (2010) 103–166. | MR | Zbl
and , Analytical De-Poissonization and Its Applications. Theor. Comput. Sci. 201 (1998) 1–62. | DOI | MR | Zbl
D.E. Knuth, The Art of Computer Programming in: Sorting and Searching. Addison Wesley (1998). | MR | Zbl
, and , On the Number of Descendants and Ascendants in Random Search Trees. Electron. J. Combin. 5 (1998) #R20. | DOI | MR | Zbl
J.S. Vitter and P. Flajolet, Average-case analysis of algorithms and data structures. Handb. Theor. Comput. Sci. (1990). | MR | Zbl
Cité par Sources :
