# Prefix Dictionary Problem in External Memory

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?

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.
If the number of strings you plan to store is $o(2^n)$, you might also be interested in the string B-tree. 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.
• 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. May 14 '11 at 3:53