Memory efficient data structure for preffix-based search

Revision en1, by caioaao, 2015-09-03 23:55:29

I'm now facing a problem in real life involving efficient data structures (yay!): I need a data structure for storing key-value data and supports prefix-based searching and, considering N the amount of keys and M a key length, inserting and deleting in O(M). The data structure will be used in an embedded software, so it must be memory efficient.

My current solution is using a trie, but the memory overhead is too big for the application. It's an straight-forward trie implementation, but splitting strings in nibbles instead of bytes. Tips on improving the memory usage for the trie are welcome.

Any thoughts?

Tags trie, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English caioaao 2015-09-03 23:55:29 674 Initial revision (published)