Zip-Tries: Simple Dynamic Data Structures for Strings
David Eppstein, Ofek Gila, Michael T. Goodrich, Ryuto Kitagawa · Society for Industrial and Applied Mathematics eBooks · 2025
In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for k-length strings in 𝕆(κ + log n ) time in the standard RAM model or in 𝕆(κ/α + log n ) time in the word RAM model, where α is the length of the longest string that can fit in a memory word, and n is the number of strings in the trie. Importantly, we show how zip-tries can achieve this while only requiring bits of metadata per node w.h.p., which is an exponential improvement over previous results for long strings. Despite being considerably simpler and more memory efficient, we show how zip- tries perform competitively with state-of-the-art data structures on large datasets of long strings.