{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T17:03:59Z","timestamp":1703091839579},"reference-count":32,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T00:00:00Z","timestamp":1606176000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["F50\u201002"],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007225","name":"Ministry of Science and Technology","doi-asserted-by":"publisher","award":["MOST\u2010104\u20102923\u2010M\u2010009\u2010006\u2010MY3","MOST\u2010109\u20102115\u2010M\u2010004\u2010003\u2010MY2"],"id":[{"id":"10.13039\/100007225","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>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\u2010Poissonization, 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\u2010point concentration for the distributions of the height and the saturation level.<\/jats:p>","DOI":"10.1002\/rsa.20979","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T06:56:30Z","timestamp":1606287390000},"page":"430-467","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Node profiles of symmetric digital search trees: Concentration properties"],"prefix":"10.1002","volume":"58","author":[{"given":"Michael","family":"Drmota","sequence":"first","affiliation":[{"name":"Institute for Discrete Mathematics and Geometry Vienna University of Technology Vienna Austria"}]},{"given":"Michael","family":"Fuchs","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences National Chengchi University Taipei Taiwan"}]},{"given":"Hsien\u2010Kuei","family":"Hwang","sequence":"additional","affiliation":[{"name":"Institute of Statistical Science Academia Sinica Taipei Taiwan"}]},{"given":"Ralph","family":"Neininger","sequence":"additional","affiliation":[{"name":"Institute for Mathematics Goethe University Frankfurt a.M. Germany"}]}],"member":"311","published-online":{"date-parts":[[2020,11,24]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00318784"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212152"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1043862420"},{"key":"e_1_2_7_5_1","volume-title":"The theory of partitions","author":"Andrews G. E.","year":"1998"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362693"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283954"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1137-7"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.04.001"},{"key":"e_1_2_7_11_1","article-title":"Asymmetric R\u00e9nyi problem","volume":"28","author":"Drmota M.","year":"2018","journal-title":"Combin. Probab. Comput."},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264279"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00002-E"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.01.024"},{"key":"e_1_2_7_16_1","first-page":"103","article-title":"Asymptotic variance of random symmetric digital search trees","volume":"12","author":"Hwang H.\u2010K.","year":"2010","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00167-9"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511843204"},{"key":"e_1_2_7_19_1","first-page":"21","article-title":"The variance of the profile in digital search trees","volume":"13","author":"Kazemi R.","year":"2011","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799356812"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00212-2"},{"key":"e_1_2_7_22_1","first-page":"14","article-title":"On the average profile of symmetric digital search trees","volume":"4","author":"Knessl C.","year":"2009","journal-title":"Online J. Anal. Comb."},{"key":"e_1_2_7_23_1","unstructured":"D. E.Knuth(1998).The art of computer programming 3:Sorting and searching 2nd ed. Addison\u2010Wesley Reading MA."},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90114-3"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1987210404791"},{"key":"e_1_2_7_26_1","first-page":"935","article-title":"Average profile of the generalized digital search trees and the generalized Lempel\u2010Ziv Algorithm","volume":"28","author":"Louchard G.","year":"1999","journal-title":"SIAM J. Comp."},{"issue":"2018","key":"e_1_2_7_27_1","first-page":"331","article-title":"Profile of PATRICIA tries","volume":"80","author":"Magner A.","year":"2017","journal-title":"Algorithmica"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973204.2"},{"key":"e_1_2_7_29_1","volume-title":"Evolution of Random Search Trees","author":"Mahmoud H. M.","year":"1992"},{"key":"e_1_2_7_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1075828056"},{"key":"e_1_2_7_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685531"},{"key":"e_1_2_7_32_1","first-page":"112","article-title":"Digital search trees and basic hypergeometric functions","volume":"56","author":"Prodinger H.","year":"1995","journal-title":"Bull. EATCS"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032770"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20979","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.20979","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T17:51:11Z","timestamp":1693677071000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,24]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.1002\/rsa.20979"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20979","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,24]]},"assertion":[{"value":"2017-11-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}