Zip-Tries: Simple Dynamic Data Structures for Strings

David Eppstein, Ofek Gila, Michael T. Goodrich, Ryuto Kitagawa · 2025

Read Zip-Tries: Simple Dynamic Data Structures for Strings by David Eppstein, Ofek Gila, Michael T. Goodrich, Ryuto Kitagawa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04953.txt.

Introduction

David Eppstein, Ofek Gila, Michael T Goodrich, and Ryuto Kitagawa build lean string stores in a 2025 paper. Their store holds strings in a trie that can grow and shrink on the fly. Search and change each run in time tied to string length plus a log term.

Each node needs a sliver of side data, a vast cut on past stores for long strings. That thrift comes from a zip trick in the node's rank marks. Tests on big sets of long strings show the store ties top rivals in speed.

Catalog record

CREATORDavid Eppstein, Ofek Gila, Michael T. Goodrich, Ryuto Kitagawa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-04953

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Zip-Tries: Simple Dynamic Data Structures for Strings David Eppstein, Ofek Gila, Michael T. Goodrich, Ryuto Kitagawa Abstract 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 k -length strings in 𝒪 ⁡ ( k + log ⁡ n ) \mathcal{O}(k+\log n) time in the standard RAM model or in 𝒪 ⁡ ( k / α + log ⁡ n ) \mathcal{O}(k/\alpha+\log n) time in the word RAM model, where α \alpha is the length of the longest string that can fit in a memory word, and n n is the number of strings in the trie. Importantly, we show how zip-tries can achieve this while only requiring 𝒪 ⁡ ( log ⁡ log ⁡ n + log ⁡ log ⁡ k α ) \mathcal{O}(\log{\log{n}}+\log{\log{\frac{k}{\alpha}}}) 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. Furthermore, we provide a simple, general framework for parallelizing string comparison operations in linked data structures, which we apply to zip-tries to obtain parallel zip-tries . Parallel zip-tries are able to achieve good search and update performance in parallel, performing such operations in 𝒪 ⁡ ( log ⁡ n ) \mathcal{O}(\log{n}) span. We also apply our techniques to an existing external-memory string data structure, the string B-tree , obtaining a parallel string B-tree which performs search operations using 𝒪 ⁡ ( log B ⁡ n ) \mathcal{O}(\log_{B}{n}) I/O span and 𝒪 ⁡ ( k α ​ B + log B ⁡ n ) \mathcal{O}(\frac{k}{\alpha B}+\log_{B}{n}) I/O work in the parallel external memory (PEM) model. The parallel string B-tree can perform prefix searches using only 𝒪 ⁡ ( log ⁡ n log ⁡ log ⁡ n ) \mathcal{O}(\frac{\log{n}}{\log{\log{n}}}) span under the practical PRAM model. For the case of long strings that share short common prefixes, we provide LCP-aware variants of all our algorithms that should be quite efficient in practice, which we justify empirically. 1 Introduction A trie , or digital tree , is a classical tree structure designed for storing and performing operations on a collection of character strings, known as a “dictionary.” Each string is represented as a path from the root to a leaf, with each edge representing a character in the string. There are numerous trie variants, including the well-known Patricia trie [ 33 ] , where every non-branching path is compressed into a single edge. Tries are simple structures used extensively in practice [ 22 , 7 , 47 , 27 ] , but they are neither well-suited for large data sets with long strings in external memory nor for use in parallel algorithms. Thus, it would be of interest to have a string data structure that is simple and practical while also being adaptable to external-memory and parallel settings. While strings may be long and string dictionaries can be large, the size of the alphabet, \sigma, is often small, with ASCII containing only 128 characters and DNA sequences containing only 4; hence we assume \sigma is a fixed constant. The word RAM and practical RAM models [ 32 ] take advantage of this by packing \alpha=\bigl\lfloor w/\lceil\log_{2}{\sigma}\rceil\bigr\rfloor characters into a machine word, where w is the word size in bits. The word RAM allows AC 0 operations to be performed on machine words in \mathcal{O}(1) time, and the practical RAM model allows constant-time operations that are common in modern CPU machine languages, such as bitwise-AND, bitwise-OR, and most significant bit (MSB), e.g., see [ 45 ] . Both models allow comparisons between two strings of length k to be performed in \mathcal{O}(k/\alpha) time. While traditional trie variants such as the Patricia trie do not take advantage of this, more recent variants do [ 4 , 43 , 46 ] , by having each node represent machine words rather than individual characters, and incorporating hash tables or dynamic predecessor/successor data structures, such as z-fast tries [ 4 ] , to each node. Although these structures achieve good theoretical bounds, they are difficult to implement and, due to their sequential nature, are not easily parallelizable. Another well-known data structure, typically designed for numerical keys or keys that are fixed-length numerical tuples, is the skip list, which stores a sorted collection of items to support efficient search, insertion, and deletion operations. One of the key benefits of skip lists over similar data structures is its inherent simplicity [ 39 , 34 ] , leading to their wide use in practice. Unfortunately, skip lists are inefficient for strings, since comparisons between strings of length k takes time \mathcal{O}(k) , or \mathcal{O}(k/\alpha) in the word RAM model. Search and update operations on a skip list perform \mathcal{O}(\log{n}) comparisons (w.h.p. in randomized versions) [ 39 , 34 ] , leading to a total time complexity of \mathcal{O}((k/\alpha)\log{n}) when applied “off the shelf” to string keys. The logarithmic factor in this bound negates the advantages of the word RAM model for long strings under realistic values of \alpha . There has been some work adapting skip lists for strings in the external memory model—where the goal is to minimize I/O operations when the data structure exceeds main memory—notably with the self-adjusting skip list (SASL) by Ciriani et al. [ 8 ] . A similar external memory adaptation was developed on the B-tree data structure with the string B-tree of Ferragina and Grossi [ 15 ] . Both data structures support common trie operations such as prefix search, predecessor/successor queries, insertions, and deletions in \mathcal{O}(k/B+\log_{B}{n}) I/Os, where B is the block size. Furthermore, Grossi and Italiano provide a framework for adapting one-dimensional linked data structures to maintain multidimensional data by storing two additional pointers and corresponding longest common prefix (LCP) lengths to each node in order to generally achieve search, insert, and delete operations in \mathcal{O}(k+\log{n}) time 1 1 1 The exact time complexity may vary depending on the underlying data structure. [ 23 ] . In 2003, Crescenzi, Grossi, and Italiano showed that these techniques, when applied to unbalanced binary search trees and AVL trees, were experimentally competitive with existing string data structures [ 9 ] . Recently there have been exciting developments in the area of randomized binary search trees, with the introduction of the zip-tree data structure by Tarjan, Levy, and Timmel [ 44 ] , which is a simple, practical, and efficient binary search tree algorithm that only requires \mathcal{O}(\log{\log{n}}) bits of metadata per node w.h.p. Several simple variants called zip-zip trees were introduced in 2023 showing how to improve its depth while maintaining a low metadata cost, supporting strong history independence, biased keys, and/or partially persistent [ 21 ] . The zip-tree and its variants are notably incompatible with the existing techniques for adapting one-dimensional data structures to support strings, since they use at most \mathcal{O}(\log{\log{n}}) bits of metadata per node which would be overshadowed by the \mathcal{O}(\log{k}) bits required to store LCP length metadata for strings of moderate lengths, and since they rely on efficient and simple ‘zip’ and ‘unzip’ procedures for update operations as opposed to

Read the complete text