Publications-Periodical Articles

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 Node profiles of symmetric digital search trees: concentration properties
作者 符麥克
Fuchs, Michael
Drmota, Michael
Hwang, Hsien-Kuei
Neininger, Ralph
貢獻者 應數系
日期 2021-05
上傳時間 10-Feb-2022 14:59:28 (UTC+8)
摘要 We give a detailed asymptotic analysis of the profiles of random symmetric digital search trees, which are in close connection with the performance of the search complexity of random queries in such trees. While the expected profiles have been analyzed for several decades, the analysis of the variance turns out to be very difficult and challenging, and requires the combination of several different analytic techniques, including Mellin and Laplace transforms, analytic de‐Poissonization, and Laplace convolutions. Our results imply concentration of the profiles in the range where the mean tends to infinity. Moreover, we also obtain a two‐point concentration for the distributions of the height and the saturation level.
關聯 Random Struc. Algor., Vol.58, No.3, pp.430-467
資料類型 article
DOI https://doi.org/10.1002/rsa.20979
dc.contributor 應數系
dc.creator (作者) 符麥克
dc.creator (作者) Fuchs, Michael
dc.creator (作者) Drmota, Michael
dc.creator (作者) Hwang, Hsien-Kuei
dc.creator (作者) Neininger, Ralph
dc.date (日期) 2021-05
dc.date.accessioned 10-Feb-2022 14:59:28 (UTC+8)-
dc.date.available 10-Feb-2022 14:59:28 (UTC+8)-
dc.date.issued (上傳時間) 10-Feb-2022 14:59:28 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/139046-
dc.description.abstract (摘要) We give a detailed asymptotic analysis of the profiles of random symmetric digital search trees, which are in close connection with the performance of the search complexity of random queries in such trees. While the expected profiles have been analyzed for several decades, the analysis of the variance turns out to be very difficult and challenging, and requires the combination of several different analytic techniques, including Mellin and Laplace transforms, analytic de‐Poissonization, and Laplace convolutions. Our results imply concentration of the profiles in the range where the mean tends to infinity. Moreover, we also obtain a two‐point concentration for the distributions of the height and the saturation level.
dc.format.extent 896029 bytes-
dc.format.mimetype application/pdf-
dc.relation (關聯) Random Struc. Algor., Vol.58, No.3, pp.430-467
dc.title (題名) Node profiles of symmetric digital search trees: concentration properties
dc.type (資料類型) article
dc.identifier.doi (DOI) 10.1002/rsa.20979
dc.doi.uri (DOI) https://doi.org/10.1002/rsa.20979