Sorry, you need to enable JavaScript to visit this website.

c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches

Citation Author(s):
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Submitted by:
Dominik Koeppl
Last updated:
31 March 2020 - 1:42am
Document Type:
Presentation Slides
Document Year:
Kazuya Tsuruta and Dominik Köppl

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 locate, prefix search, and update operations on K. Under the assumption that α = w / lg σ characters fit into a single machine word w, we propose a keyword dictionary that represents K in n lg σ + O(k lg n) bits of space, supporting all operations in O(m / α + lg α) expected time on an input string of length m in the word RAM model. This data structure is underlined with an exhaustive practical evaluation, highlighting the practical usefulness of the proposed data structure, especially for prefix searches - one of the most elementary keyword dictionary operations.

0 users have voted: