<p>You might store $\Theta(B)$ children in every node of a trie with alphabet size $\Theta(B)$ by treating your binary sequences as strings over an alphabet each letter of which takes $\Theta(\lg B)$ bits. This will waste space if your string set is sparse, but I think inserts and prefix searches require $(n/\lg B)$ I/Os in the worst case where $n$ is the length of the longest unique prefix (in the case of insert) or the length of the prefix searched for. </p>

<p>To find the longest sequence with a certain prefix, store with each child pointer the length of the longest descendant string.</p>

<p>If the number of strings you plan to store is $o(2^n)$, you might also be interested in the <a href="http://www.cib.espol.edu.ec/Digipath/D_Papers/41662.pdf" rel="nofollow">string B-tree</a>. Insert takes $O(n/B + \log_B k)$ I/Os in the worst-case for a string of length $n$ in a tree containing $k$ strings. Prefix search takes $O((p + occ)/B + \log_B k)$ I/Os in the worst-case, where $p$ is the length of the prefix to search and $occ$ is the number of results of the search. These are both larger than your requested bound ($O(p/B)$ or $O(n/B)$ in this notation), and prefix search isn't exactly what you're looking for, it sounds like, but I think storing the longest descendant length will work in this case.</p>

CC BY-SA 3.0
2011-05-14T03:53:53.887Z
I think I'm confused about the trie strategy. For a simple trie with letters of length $\log B$ bits, I'm figuring $n / \log B$ I/O's. But I could see how if you might do better if you take $k$ into account, and assume you don't have exponentially many strings.
Shaun Harker
CC BY-SA 3.0
2011-05-14T05:12:50.037Z
Yup, you're right. I'll fix it.
jbapple
CC BY-SA 3.0
2011-05-13T15:16:23.987Z
2011-05-14T05:16:59.737Z
2011-05-14T05:16:59.737Z
jbapple
<p>I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the longest sequence previously inserted which is a prefix of the query sequence, provided one exists.</p>

<p>In particular, do we need $O(n)$ I/O's for an operation with a sequence of length $n$? (Say, by directly implementing a radix tree in external memory.) Or is there something nice, where we can get $O(n/B)$ I/O's?</p>

<ds.data-structures><machine-models>
Prefix Dictionary Problem in External Memory
Shaun Harker
# Prefix Dictionary Problem in External Memory

(Asked by: username_0 on 2011-05-13)

I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the longest sequence previously inserted which is a prefix of the query sequence, provided one exists.

In particular, do we need $O(n)$ I/O's for an operation with a sequence of length $n$? (Say, by directly implementing a radix tree in external memory.) Or is there something nice, where we can get $O(n/B)$ I/O's?

**Tags:** ds.data-structures, machine-models

---

## 1 answers

### Answer by username_1 on 2011-05-13. Score: 3 | Accepted answer

You might store $\Theta(B)$ children in every node of a trie with alphabet size $\Theta(B)$ by treating your binary sequences as strings over an alphabet each letter of which takes $\Theta(\lg B)$ bits. This will waste space if your string set is sparse, but I think inserts and prefix searches require $(n/\lg B)$ I/Os in the worst case where $n$ is the length of the longest unique prefix (in the case of insert) or the length of the prefix searched for.

To find the longest sequence with a certain prefix, store with each child pointer the length of the longest descendant string.

If the number of strings you plan to store is $o(2^n)$, you might also be interested in the [string B-tree](http://www.cib.espol.edu.ec/Digipath/D_Papers/41662.pdf). Insert takes $O(n/B + \log\_B k)$ I/Os in the worst-case for a string of length $n$ in a tree containing $k$ strings. Prefix search takes $O((p + occ)/B + \log\_B k)$ I/Os in the worst-case, where $p$ is the length of the prefix to search and $occ$ is the number of results of the search. These are both larger than your requested bound ($O(p/B)$ or $O(n/B)$ in this notation), and prefix search isn't exactly what you're looking for, it sounds like, but I think storing the longest descendant length will work in this case.

> **Comments:**
> **username_0**: I think I'm confused about the trie strategy. For a simple trie with letters of length $\log B$ bits, I'm figuring $n / \log B$ I/O's. But I could see how if you might do better if you take $k$ into account, and assume you don't have exponentially many strings.  
> **username_1**: Yup, you're right. I'll fix it.  

---

