Jan Vladimir Mostert

Idea Incubator

Oct 23, 2015

I've done it before using a SQL database (as well as on Google's Datastore), but the concept can be applied to Redis as well, it's just not very efficient in terms of storage, but very fast (if you want storage efficiency, use SQL and use the Like keyword, it's a lot slower, but you will only store a key per word)

Take the word petrol, now you store keywords for each letter p, e, t, r, o, l, now run through the word again using pairs of two, pe, et, tr, ro, ol, now run through the word again using pairs of three, pet, etr, tro, rol, now in pairs of four, petr, etro, trol, pairs of five, petro, etrol and finally the whole word, petrol

Now you can split it up into separate "tables" if you want to further speedup the lookups, create a table for single-character lookups, one for double-character lookups etc. If you see only small fraction of the words are more than 7 characters, you can throw all of them into the same "table".

And that should give you very fast lookups at the cost of storing n(n+1)/2 keys where n is the length of the word you're storing.

In terms of BigO notation, you'd get lookups with order complexity of O(1) and space complexity of O(n^2), that's as fast as you can get.

Jan Vladimir Mostert

It depends on how many words you are looking to autocomplete on, if it's going to be millions and millions of words, caching all of those words in Redis might cause Redis to take strain (depends on how much RAM you have available) in which case I'd rather keep them on disk (MongoDB) and then simply cache frequently searched snippets.

Example, if you frequently get a search for ab (somebody busy typing about), cache the lookup results of ab. A great way to do this would be to keep a list of 10000 last searched snippets in Redis, the list could look something like: ab, cad, e, ... then every time that snippet is searched for again, move it up by one in the list, that means snippets which are frequently searched will bubble to the top and those that are not will disappear when they are pushed down the list by the top searched snippets - this way frequently searched snippets' results will be in cache (which means those short search terms like single/double character lookups will bring back results faster) whereas less frequently searched snippets will need a lookup from MongoDB.

Search Hashnode