3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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. 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Shaun Harker May 14 '11 at 3:53
  • $\begingroup$ Yup, you're right. I'll fix it. $\endgroup$ – jbapple May 14 '11 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.