C-Trie++: A dynamic trie tailored for fast prefix searches

Kazuya Tsuruta, Dominik Koppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)


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 σ + Θ(k lg n) bits of space, supporting all operations in Θ(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.

Original languageEnglish
Title of host publicationProceedings - DCC 2020
Subtitle of host publicationData Compression Conference
EditorsAli Bilgin, Michael W. Marcellin, Joan Serra-Sagrista, James A. Storer
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781728164571
Publication statusPublished - Mar 2020
Event2020 Data Compression Conference, DCC 2020 - Snowbird, United States
Duration: Mar 24 2020Mar 27 2020

Publication series

NameData Compression Conference Proceedings
ISSN (Print)1068-0314


Conference2020 Data Compression Conference, DCC 2020
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


Dive into the research topics of 'C-Trie++: A dynamic trie tailored for fast prefix searches'. Together they form a unique fingerprint.

Cite this