{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:16Z","timestamp":1750220536767,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3457319","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:30Z","timestamp":1624036950000},"page":"872-884","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient String Sort with Multi-Character Encoding and Adaptive Sampling"],"prefix":"10.1145","author":[{"given":"Wen","family":"Jin","sequence":"first","affiliation":[{"name":"Independent Researcher, Vancouver, BC, Canada"}]},{"given":"Weining","family":"Qian","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}]},{"given":"Aoying","family":"Zhou","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"AMCE. 2021. github. https:\/\/github.com\/amce2021\/AMCE2021  AMCE. 2021. github. https:\/\/github.com\/amce2021\/AMCE2021"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365721"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297136"},{"volume-title":"Matters Computational","author":"Arndt J\u00f6rg","key":"e_1_3_2_2_4_1","unstructured":"A J\u00f6rg Arndt . 2010. Mixed radix numbers . In Matters Computational . Springer , Berlin, Heidelberg , 217--231. https:\/\/doi.org\/10.1007\/978--3--642--14764--7_9 10.1007\/978--3--642--14764--7_9 AJ\u00f6rg Arndt. 2010. Mixed radix numbers. In Matters Computational. Springer, Berlin, Heidelberg, 217--231. https:\/\/doi.org\/10.1007\/978--3--642--14764--7_9"},{"key":"e_1_3_2_2_5_1","volume-title":"Proceedings of European Symposium on Algorithms (ESA). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik","author":"Axtmann Michael","year":"2017","unstructured":"Michael Axtmann , Sascha Witt , Daniel Ferizovic , and Peter Sanders . 2017 . In-place Parallel Super Scalar Sample sort (IPS4o) . In Proceedings of European Symposium on Algorithms (ESA). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , Dagstuhl, Germany, 9:1--9:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA. 2017.9 10.4230\/LIPIcs.ESA.2017.9 Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. 2017. In-place Parallel Super Scalar Sample sort (IPS4o). In Proceedings of European Symposium on Algorithms (ESA). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 9:1--9:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.9"},{"volume-title":"Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM (Ed.). Society for Industrial and Applied Mathematics","author":"Jon","key":"e_1_3_2_2_6_1","unstructured":"Jon L. Bentley and Robert Sedgewick. 1997. Fast Algorithms for Sorting and Searching Strings . In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM (Ed.). Society for Industrial and Applied Mathematics , Philadelphia, PA, United States, 360--369. https:\/\/dl.acm.org\/doi\/10.5555\/314161.3 10.5555\/314161.314321 14321 Jon L. Bentley and Robert Sedgewick. 1997. Fast Algorithms for Sorting and Searching Strings. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM (Ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, United States, 360--369. https:\/\/dl.acm.org\/doi\/10.5555\/314161.3 10.5555\/314161.314321 14321"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0071-1"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_15"},{"key":"e_1_3_2_2_10_1","volume-title":"Sorting with Asymmetric Read and Write Costs. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '15)","author":"Blelloch Guy E.","year":"2015","unstructured":"Guy E. Blelloch , Jeremy T. Fineman , Phillip B. Gibbons , and Julian Shun Yan Gu . 2015 . Sorting with Asymmetric Read and Write Costs. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '15) . ACM, Portland, Oregon, USA, 1--12. https:\/\/doi.org\/10.1145\/2755573.2755604 10.1145\/2755573.2755604 Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Julian Shun Yan Gu. 2015. Sorting with Asymmetric Read and Write Costs. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '15). ACM, Portland, Oregon, USA, 1--12. https:\/\/doi.org\/10.1145\/2755573.2755604"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824050"},{"key":"e_1_3_2_2_12_1","volume-title":"11th IEEE Conference on Parallel, Distributed and Network-Based Processing (Euro-PDP'03)","author":"Daniel Jim\u00e9nez-Gonz\u00e1lez","year":"2003","unstructured":"Jim\u00e9nez-Gonz\u00e1lez Daniel , Juan J. Navarro , and Luis Larriba-Peyp Josep . 2003 . CC-Radix: a Cache Conscious Sorting Based on Radix Sort . In 11th IEEE Conference on Parallel, Distributed and Network-Based Processing (Euro-PDP'03) . IEEE, Genova, Italy, 101--108. https:\/\/doi.org\/10.1109\/EMPDP. 2003.1183573 10.1109\/EMPDP.2003.1183573 Jim\u00e9nez-Gonz\u00e1lez Daniel, Juan J. Navarro, and Luis Larriba-Peyp Josep. 2003. CC-Radix: a Cache Conscious Sorting Based on Radix Sort. In 11th IEEE Conference on Parallel, Distributed and Network-Based Processing (Euro-PDP'03). IEEE, Genova, Italy, 101--108. https:\/\/doi.org\/10.1109\/EMPDP.2003.1183573"},{"key":"e_1_3_2_2_13_1","unstructured":"Address dataset. 2020. OpenAddresses. https:\/\/data.openaddresses.io\/  Address dataset. 2020. OpenAddresses. https:\/\/data.openaddresses.io\/"},{"key":"e_1_3_2_2_14_1","unstructured":"URL dataset. 2013. panthema. http:\/\/panthema.net\/2013\/parallel-string-sorting\/  URL dataset. 2013. panthema. http:\/\/panthema.net\/2013\/parallel-string-sorting\/"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_19"},{"key":"e_1_3_2_2_16_1","unstructured":"GNU. 2009. C+: STL sort. https:\/\/gcc.gnu.org\/onlinedocs\/libstdc+\/libstdc+-html-USERS-4.4\/a01347.html  GNU. 2009. C+: STL sort. https:\/\/gcc.gnu.org\/onlinedocs\/libstdc+\/libstdc+-html-USERS-4.4\/a01347.html"},{"key":"e_1_3_2_2_17_1","volume-title":"Proceedings of European Symposium on Algorithms (ESA). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik","author":"Gu Yan","year":"2018","unstructured":"Yan Gu , Yihan Sun , and Guy E. Blelloch . 2018. Algorithmic Building Blocks for Asymmetric Memories . In Proceedings of European Symposium on Algorithms (ESA). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik , Helsinki, Finland, 44:1--44:15. https:\/\/doi.org\/10.4230\/LIPIcs.ESA. 2018 .44 10.4230\/LIPIcs.ESA.2018.44 Yan Gu, Yihan Sun, and Guy E. Blelloch. 2018. Algorithmic Building Blocks for Asymmetric Memories. In Proceedings of European Symposium on Algorithms (ESA). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, Helsinki, Finland, 44:1--44:15. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.44"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389752"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89097-3_3"},{"key":"e_1_3_2_2_20_1","first-page":"5","article-title":"Engineering Radix Sort","volume":"6","author":"McIlroy Peter M.","year":"1993","unstructured":"Peter M. McIlroy , Keith Bostic , and M. Douglas McIlroy . 1993 . Engineering Radix Sort . Computing Systems , Vol. 6 , 1 (1993), 5 -- 27 . https:\/\/www.usenix.org\/legacy\/publications\/compsystems\/1993\/win_mcilroy.pdf Peter M. McIlroy, Keith Bostic, and M. Douglas McIlroy. 1993. Engineering Radix Sort. Computing Systems, Vol. 6, 1 (1993), 5--27. https:\/\/www.usenix.org\/legacy\/publications\/compsystems\/1993\/win_mcilroy.pdf","journal-title":"Computing Systems"},{"key":"e_1_3_2_2_21_1","first-page":"8","article-title":"Introspective sorting and selection algorithms. Software","volume":"27","author":"Musser David R","year":"1997","unstructured":"David R Musser . 1997 . Introspective sorting and selection algorithms. Software : Practice and Experience , Vol. 27 , 8 (Aug. 1997), 983--993. http:\/\/oucsace.cs.ohio.edu\/ razvan\/courses\/cs4040\/introsort.pdf David R Musser. 1997. Introspective sorting and selection algorithms. Software: Practice and Experience, Vol. 27, 8 (Aug. 1997), 983--993. http:\/\/oucsace.cs.ohio.edu\/ razvan\/courses\/cs4040\/introsort.pdf","journal-title":"Practice and Experience"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/ietfec\/e90-a.2.457"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjdc.4.69"},{"key":"e_1_3_2_2_24_1","volume-title":"Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '19)","author":"Obeya Omar","year":"2019","unstructured":"Omar Obeya , Endrias Kahssay , Edward Fan , and Julian Shun . 2019 . Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '19) . ACM, Phoenix, AZ, USA, 213--224. https:\/\/dl.acm.org\/doi\/10.1145\/3323165.3323198 Omar Obeya, Endrias Kahssay, Edward Fan, and Julian Shun. 2019. Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '19). ACM, Phoenix, AZ, USA, 213--224. https:\/\/dl.acm.org\/doi\/10.1145\/3323165.3323198"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"e_1_3_2_2_26_1","unstructured":"Mixed radix. 2019. Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Mixed_radix  Mixed radix. 2019. Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Mixed_radix"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945401"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_69"},{"key":"e_1_3_2_2_29_1","first-page":"1","article-title":"Engineering Burstsort: Toward Fast In-Place String Sorting","volume":"15","author":"Sinha Ranjan","year":"2010","unstructured":"Ranjan Sinha and Anthony Wirth . 2010 . Engineering Burstsort: Toward Fast In-Place String Sorting . ACM Journal of Experimental Algorithmics (JEA) , Vol. 15 (2010), 1 -- 24 . https:\/\/doi.org\/10.1145\/1671970.1671978 10.1145\/1671970.1671978 Ranjan Sinha and Anthony Wirth. 2010. Engineering Burstsort: Toward Fast In-Place String Sorting. ACM Journal of Experimental Algorithmics (JEA), Vol. 15 (2010), 1--24. https:\/\/doi.org\/10.1145\/1671970.1671978","journal-title":"ACM Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_3_2_2_30_1","volume-title":"Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries. In 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM","author":"Sinha Ranjan","year":"2003","unstructured":"Ranjan Sinha and Justin Zobel . 2003 a . Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries. In 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM , Baltimore, MD, US, 93--105. https:\/\/archive.siam.org\/meetings\/alenex03\/Abstracts\/rsinha.pdf Ranjan Sinha and Justin Zobel. 2003 a. Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries. In 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, Baltimore, MD, US, 93--105. https:\/\/archive.siam.org\/meetings\/alenex03\/Abstracts\/rsinha.pdf"},{"key":"e_1_3_2_2_31_1","volume-title":"Proceedings of the 26th Australasian Computer Science Conference (ACSC). Australian Computer Society, Darlinghurst, NSW, Australia, 11--18","author":"Sinha Ranjan","year":"2003","unstructured":"Ranjan Sinha and Justin Zobel . 2003 b. Efficient Trie-based Sorting of Large Sets of Strings . In Proceedings of the 26th Australasian Computer Science Conference (ACSC). Australian Computer Society, Darlinghurst, NSW, Australia, 11--18 . https:\/\/dl.acm.org\/doi\/10.5555\/783106.783108 Ranjan Sinha and Justin Zobel. 2003 b. Efficient Trie-based Sorting of Large Sets of Strings. In Proceedings of the 26th Australasian Computer Science Conference (ACSC). Australian Computer Society, Darlinghurst, NSW, Australia, 11--18. https:\/\/dl.acm.org\/doi\/10.5555\/783106.783108"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24838-5_39"},{"key":"e_1_3_2_2_33_1","volume-title":"I Wrote a Faster Sorting Algorithm. https:\/\/probablydance.com\/2016\/12\/27\/i-wrote-a-faster-sorting-algorithm\/ Retrieved","author":"Skarupke Malte","year":"2021","unstructured":"Malte Skarupke . 2016. I Wrote a Faster Sorting Algorithm. https:\/\/probablydance.com\/2016\/12\/27\/i-wrote-a-faster-sorting-algorithm\/ Retrieved Jan , 2021 from Malte Skarupke. 2016. I Wrote a Faster Sorting Algorithm. https:\/\/probablydance.com\/2016\/12\/27\/i-wrote-a-faster-sorting-algorithm\/ Retrieved Jan, 2021 from"},{"key":"e_1_3_2_2_34_1","unstructured":"Radix sort. 2021. Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Radix_sort  Radix sort. 2021. Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Radix_sort"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SUPERC.1992.236714"},{"key":"e_1_3_2_2_36_1","unstructured":"Words (Unix). 2021. Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Words_(Unix)  Words (Unix). 2021. Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Words_(Unix)"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23397-5_16"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Virtual Event China","acronym":"SIGMOD\/PODS '21"},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457319","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3457319","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:04Z","timestamp":1750195504000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":36,"alternative-id":["10.1145\/3448016.3457319","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3457319","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}