Disk-based trie?

Question

I'm trying to build a Trie but on a mobile phone which has very limited memory capacity.

I figured that it is probably best that the whole structure be stored on disk, and only loaded as necessary since I can tolerate a few disk reads. But, after a few attempts, it seems like this is a very complicated thing to do.

What are some ways to store a Trie on disk (i.e. only partially loaded) and keep the fast lookup property?
Is this even a good idea to begin with?

Birthwort

I'd reach for a B-tree rather than a trie in this situation, but I'd love to know the answer to this question too. – Sumerian

Tries are structures to support fast look-up. This looks like good use-case for some embedded database engine, like SQLite, or some en.wikipedia.org/wiki/Dbm derivative – Dyann

Answer 1

The paper B-tries for disk-based string management answers your question.

It makes the observation:

To our knowledge, there has yet to be a proposal in literature for a trie-based data structure, such as the burst trie, the can reside efficiently on disk to support common string processing tasks.

Phebe

Link to naskitis.com seems to be down again (or something entirely else), new URL for the paper: people.eng.unimelb.edu.au/jzobel/fulltext/vldbj09.pdf – Wilbanks

Answer 2

I've only glanced at it briefly, but Shang's "Trie methods for text and spatial data on secondary storage" discusses paged trie representations, and might be a useful starting point.

Padnag