Documents
Presentation Slides
Presentation Slides
c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
- Citation Author(s):
- Submitted by:
- Dominik Koeppl
- Last updated:
- 31 March 2020 - 1:42am
- Document Type:
- Presentation Slides
- Document Year:
- 2020
- Event:
- Presenters:
- Kazuya Tsuruta and Dominik Köppl
- Categories:
- Keywords:
- Log in to post comments
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.