Paper Info
Title
c-trie++: A dynamic trie tailored for fast prefix searches
Abstract
Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ, a keyword dictionary is a data structure built on K that provides lookup, prefix search, and update operations on K. Under the assumption that α=w/lg⁡σ characters fit into a single machine word of w bits, we propose a keyword dictionary that represents K in either nlg⁡σ+Θ(klg⁡n) or |T|lg⁡σ+Θ(kw) bits of space, where |T| is the number of nodes of a trie representing K. It supports all operations in O(m/α+lg⁡α) expected time on an input string of length m in the word RAM model. An evaluation of our implementation highlights the practical usefulness of the proposed data structure, especially for prefix searches — one of the most essential keyword dictionary operations.
Year
DOI
Venue
2022
10.1016/j.ic.2021.104794
Information and Computation
Keywords
DocType
Volume
String dictionary,Compact trie,Hashing,Word-packing,Prefix searches
Journal
285
ISSN
Citations 
PageRank 
0890-5401
0
0.34
References 
Authors
2
7
Name
Order
Citations
PageRank
Kazuya Tsuruta100.34
Dominik Köppl200.34
Shunsuke Kanda301.69
Yuto Nakashima45719.52
Shunsuke Inenaga559579.02
Hideo Bannai662079.87
Masayuki Takeda7913.78