Zip-Tries: Simple Dynamic Data Structures for Strings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913998438400000 |
|---|---|
| author | Eppstein, David Gila, Ofek Goodrich, Michael T. Kitagawa, Ryuto |
| author_facet | Eppstein, David Gila, Ofek Goodrich, Michael T. Kitagawa, Ryuto |
| contents | 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 $\mathcal{O}(k+\log n)$ time in the standard RAM model or in $\mathcal{O}(k/α+\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 $\mathcal{O}(\log{\log{n}} + \log{\log{\frac{k}α}})$ 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 $\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 $\mathcal{O}(\log_B{n})$ I/O span and $\mathcal{O}(\frac{k}{α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 $\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04953 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Zip-Tries: Simple Dynamic Data Structures for Strings Eppstein, David Gila, Ofek Goodrich, Michael T. Kitagawa, Ryuto Data Structures and Algorithms 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 $\mathcal{O}(k+\log n)$ time in the standard RAM model or in $\mathcal{O}(k/α+\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 $\mathcal{O}(\log{\log{n}} + \log{\log{\frac{k}α}})$ 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 $\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 $\mathcal{O}(\log_B{n})$ I/O span and $\mathcal{O}(\frac{k}{α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 $\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. |
| title | Zip-Tries: Simple Dynamic Data Structures for Strings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.04953 |