Such a search sounds like a perfect use case for the trie data structure. It would be interesting to see a comparison. An example implementation of tries in Erlang can be found here.