{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T10:10:25Z","timestamp":1764843025690,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75242-2_8","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"116-129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Upper Tail Analysis of Bucket Sort and Random Tries"],"prefix":"10.1007","author":[{"given":"Ioana O.","family":"Bercea","sequence":"first","affiliation":[]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"8_CR1","unstructured":"Bercea, I.O., Even, G.: Upper tail analysis of bucket sort and random tries. CoRR abs\/2002.10499 (2020). https:\/\/arxiv.org\/abs\/2002.10499"},{"issue":"1\u20132","key":"8_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02679623","volume":"29","author":"J Cl\u00e9ment","year":"2001","unstructured":"Cl\u00e9ment, J., Flajolet, P., Vall\u00e9e, B.: Dynamical sources in information theory: a general analysis of trie structures. Algorithmica 29(1\u20132), 307\u2013369 (2001)","journal-title":"Algorithmica"},{"key":"8_CR3","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Devroye, L.: Lecture Notes on Bucket Algorithms, vol. 12. Birkh\u00e4user Boston (1986)","DOI":"10.1007\/978-1-4899-3531-1"},{"key":"8_CR5","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. CoRR abs\/1801.06733 (2018). http:\/\/arxiv.org\/abs\/1801.06733"},{"key":"8_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/S0196-6774(02)00216-X","volume":"44","author":"JA Fill","year":"2002","unstructured":"Fill, J.A., Janson, S.: Quicksort asymptotics. J. Algorithms 44(1), 4\u201328 (2002)","journal-title":"J. Algorithms"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $$o(1)$$ worst case access time. In: 23rd Annual Symposium on Foundations of Computer Science, pp. 165\u2013169. IEEE (1982)","DOI":"10.1109\/SFCS.1982.39"},{"key":"8_CR9","unstructured":"Jacquet, P., Regnier, M.: Normal limiting distribution for the size and the external path length of tries (1988)"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Janson, S.: On the tails of the limiting quicksort distribution. Electron. Commun. Prob. 20 (2015)","DOI":"10.1214\/ECP.v20-4525"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.spl.2017.11.017","volume":"135","author":"S Janson","year":"2018","unstructured":"Janson, S.: Tail bounds for sums of geometric and exponential variables. Stat. Prob. Lett. 135, 1\u20136 (2018)","journal-title":"Stat. Prob. Lett."},{"issue":"1\u20132","key":"8_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0166-218X(89)90050-4","volume":"25","author":"P Kirschenhofer","year":"1989","unstructured":"Kirschenhofer, P., Prodinger, H., Szpankowski, W.: On the variance of the external path length in a symmetric digital trie. Discrete Appl. Math. 25(1\u20132), 129\u2013143 (1989)","journal-title":"Discrete Appl. Math."},{"key":"8_CR13","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. III, 2nd edn. Addison-Wesley, Boston (1998)","edition":"2"},{"issue":"9\u201310","key":"8_CR14","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/s002360050173","volume":"36","author":"H Mahmoud","year":"2000","unstructured":"Mahmoud, H., Flajolet, P., Jacquet, P., R\u00e9gnier, M.: Analytic variations on bucket selection and sorting. Acta Informatica 36(9\u201310), 735\u2013760 (2000)","journal-title":"Acta Informatica"},{"key":"8_CR15","volume-title":"Evolution of Random Search Trees","author":"HM Mahmoud","year":"1992","unstructured":"Mahmoud, H.M., Lueker, G.S.: Evolution of Random Search Trees, vol. 200. Wiley, New York (1992)"},{"issue":"3","key":"8_CR16","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1006\/jagm.1996.0055","volume":"21","author":"C McDiarmid","year":"1996","unstructured":"McDiarmid, C., Hayward, R.: Large deviations for quicksort. J. Algorithms 21(3), 476\u2013507 (1996). https:\/\/doi.org\/10.1006\/jagm.1996.0055","journal-title":"J. Algorithms"},{"key":"8_CR17","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, Cambridge (2017)"},{"issue":"3","key":"8_CR18","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1051\/ita\/1989230303351","volume":"23","author":"M R\u00e9gnier","year":"1989","unstructured":"R\u00e9gnier, M.: A limiting distribution for quicksort. RAIRO-Theoretical Inform. Appl.-Informatique Th\u00e9orique et Appl. 23(3), 335\u2013343 (1989)","journal-title":"RAIRO-Theoretical Inform. Appl.-Informatique Th\u00e9orique et Appl."},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-030-25209-0_5","volume-title":"Sequential and Parallel Algorithms and Data Structures","author":"P Sanders","year":"2019","unstructured":"Sanders, P., Mehlhorn, K., Dietzfelbinger, M., Dementiev, R.: Sorting and selection. In: Sequential and Parallel Algorithms and Data Structures, pp. 153\u2013210. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-25209-0_5"},{"key":"8_CR20","volume-title":"An Introduction to the Analysis of Algorithms","author":"R Sedgewick","year":"2013","unstructured":"Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Pearson Education India, Chennai (2013)"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Seidel, R.: Data-specific analysis of string sorting. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1278\u20131286. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.102"},{"key":"8_CR22","volume-title":"Average Case Analysis of Algorithms on Sequences","author":"W Szpankowski","year":"2011","unstructured":"Szpankowski, W.: Average Case Analysis of Algorithms on Sequences, vol. 50. John Wiley & Sons, New York (2011)"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Vitter, J.S., Flajolet, P.: Average-case analysis of algorithms and data structures. In: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pp. 431\u2013524 (1990)","DOI":"10.1016\/B978-0-444-88071-0.50014-X"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T22:04:16Z","timestamp":1620165856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic the conference was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}