c-trie++: a dynamic trie tailored for fast prefix searches

DOI10.1016/j.ic.2021.104794zbMath1487.68087arXiv1904.07467OpenAlexW3197753456MaRDI QIDQ2672225

Hideo Bannai, Dominik Köppl, Masayuki Takeda, Shunsuke Kanda, Shunsuke Inenaga, Yuto Nakashima, Kazuya Tsuruta

Publication date: 8 June 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.07467

zbMATH Keywords

hashingword-packingstring dictionarycompact trieprefix searches

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lempel-Ziv-78 compressed string dictionaries
• Optimal bounds for the predecessor problem and related problems
• On-line construction of suffix trees
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Balanced allocation and dictionaries with tightly packed constant size bins
• Fast Compressed Tries through Path Decompositions
• Tight(er) worst-case bounds on dynamic searching and priority queues
• Compact Hash Tables Using Bidirectional Linear Probing
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Cuckoo hashing
• Deterministic Indexing for Packed Strings
• Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
• Top Tree Compression of Tries.
• Dynamic Path-decomposed Tries

This page was built for publication: c-trie++: a dynamic trie tailored for fast prefix searches