Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/33033
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPoyias, Andreas-
dc.contributor.authorRaman, Rajeev-
dc.date.accessioned2015-09-10T08:36:15Z-
dc.date.available2016-09-05T01:45:10Z-
dc.date.issued2015-09-05-
dc.identifier.citationLecture Notes in Computer Science, 2015, 9309, pp. 324-336 (13)en
dc.identifier.isbn978-3-319-23825-8-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://link.springer.com/chapter/10.1007%2F978-3-319-23826-5_31en
dc.identifier.urihttp://hdl.handle.net/2381/33033-
dc.description.abstractWe consider the problem of implementing a dynamic trie with an emphasis on good practical performance. For a trie with n nodes with an alphabet of size σ, the information-theoretic lower bound is nlogσ+O(n) bits. The Bonsai data structure [1] supports trie operations in O(1) expected time (based on assumptions about the behaviour of hash functions). While its practical speed performance is excellent, its space usage of (1+ϵ)n(logσ+O(loglogn)) bits, where ϵ is any constant >0, is not asymptotically optimal. We propose an alternative, m-Bonsai, that uses (1+ϵ)n(logσ+O(1)) bits in expectation, and supports operations in O(1) expected time (again based on assumptions about the behaviour of hash functions). We give a heuristic implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.ispartofseriesTheoretical Computer Science and General Issues-
dc.rightsCopyright © 2015, Springer International Publishing Switzerland. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-23826-5_31en
dc.titleImproved Practical Compact Dynamic Triesen
dc.typeConference Paperen
dc.identifier.doi10.1007/978-3-319-23826-5_31-
dc.description.statusPeer-revieweden
dc.description.versionPost-printen
dc.description.presented22nd International Symposium on String Processing and Information Retrievalen
pubs.organisational-group/Organisationen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
dc.identifier.eisbn978-3-319-23826-5-
dc.dateaccepted2015-06-29-
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
spire_paper_102_final.pdfPost-review (final submitted)311.52 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.