Tries seem to be good at storing and querying small strings, like keys to a dictionary.

What I would like to know is if there is anything better for storing large strings such as a 1,000 page document of text. I have heard of Inverted Indexes, which seem to just add a layer of nesting to the tries: instead of building a character trie, you build a word-trie. I am not sure if this is the technique you should follow: for larger strings just build a layer of nesting/abstraction and do a trie at that level. So you could have perhaps a character-level trie for words, a word-level trie for documents, and a concept-level trie or some semantic-like trie for document collections. Something like that.

Or if not that, I would like to know what is the general approach for storing things like an arbitrary collection of BigInts ranging from like $-10^{50}$ to $10^{50}$, or an arbitrary collection of documents from a tweet to 10,000 pages of text. So that it is searchable by keyword, or by min/max, or other common queries. Wondering what the general approach is to solve a wide range of query problems like these, and if Tries can handle it well or not. If not, what some good data structures are to look into.

Another example I was thinking of is say you wanted to query by ID. Usually you would just have a 32-bit ID or something like that, with O(1) lookup from a hashtable. But say you had the ID be 10,000 32-bit segments, essentially the ID was a complete document. Then I can't see what you would do. If you had one ID be 2 32-bit chunks, and another ID be 10,000 32-bit chunks, and if the trie was a binary trie, then one would have 64-nodes, the other would have tens of thousands of nodes which is inefficient. I don't see how to simplify this sort of situation.

  • $\begingroup$ Please pick one problem statement. Right now I see three: (1) storing strings, (2) storing arbitrary collection of bigints, (3) storing something with IDs. Then edit your question to focus on that one situation. Also, do you want to store a single string or a collection of strings? What operations do you want to be able to perform on the string or on the collection? Please edit the question to specify that. $\endgroup$ – D.W. Feb 7 at 3:57

Your Answer

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

Browse other questions tagged or ask your own question.