{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:51:01Z","timestamp":1759683061251},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p> We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with [Formula: see text] nodes with an alphabet of size [Formula: see text], the information-theoretic space lower bound is [Formula: see text] bits. The Bonsai data structure is a compact trie proposed by Darragh et al. (Softw. Pract. Exper. 23(3) (1993) 277\u2013291). Its disadvantages include the user having to specify an upper bound [Formula: see text] on the trie size in advance (which cannot be changed easily after initalization), a space usage of [Formula: see text] (which is asymptotically non-optimal for smaller [Formula: see text] or if [Formula: see text]) and a lack of support for deletions. It supports traversal and update operations in [Formula: see text] expected time (based on assumptions about the behaviour of hash functions), where [Formula: see text] and has excellent speed performance in practice. We propose an alternative, m-Bonsai, that addresses the above problems, obtaining a trie that uses [Formula: see text] bits in expectation, and supports traversal and update operations in [Formula: see text] expected time and [Formula: see text] amortized expected time, for any user-specified parameter [Formula: see text] (again based on assumptions about the behaviour of hash functions). We give an implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai. <\/jats:p>","DOI":"10.1142\/s0129054118430025","type":"journal-article","created":{"date-parts":[[2018,12,27]],"date-time":"2018-12-27T02:58:46Z","timestamp":1545879526000},"page":"1257-1278","source":"Crossref","is-referenced-by-count":7,"title":["m-Bonsai: A Practical Compact Dynamic Trie"],"prefix":"10.1142","volume":"29","author":[{"given":"Andreas","family":"Poyias","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Leicester, University Road, Leicester, LE1 7RH, United Kingdom"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Helsinki Institute of Information Technology, Department of Computer Science, University of Helsinki, P. O. Box 68, FI-00014, Finland"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Leicester, University Road, Leicester, LE1 7RH, United Kingdom"}]}],"member":"219","published-online":{"date-parts":[[2018,12,26]]},"reference":[{"key":"S0129054118430025BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/32.31365"},{"key":"S0129054118430025BIB002","first-page":"1","volume":"74","author":"Arroyuelo D.","year":"2015","journal-title":"Algorithmica"},{"key":"S0129054118430025BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1146-6"},{"key":"S0129054118430025BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"S0129054118430025BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"S0129054118430025BIB007","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230305"},{"key":"S0129054118430025BIB010","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"S0129054118430025BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9664-0"},{"key":"S0129054118430025BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"S0129054118430025BIB016","volume-title":"Algorithm Design and Applications","author":"Goodrich M. T.","year":"2015"},{"key":"S0129054118430025BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9836-6"},{"key":"S0129054118430025BIB021","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth D. E.","year":"1998","edition":"2"},{"key":"S0129054118430025BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0102-y"},{"key":"S0129054118430025BIB024","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118430025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:58:36Z","timestamp":1565110716000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118430025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":14,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2018,12,26]]},"published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1142\/S0129054118430025"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118430025","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12]]}}}