3 ms·
Very nice. You will save some space and allow for some typos if you stem and soundex before insertion. Also you can save space and improve the run time somewhat
by hedgehog 13y ago
Very nice. You will save some space and allow for some typos if you stem and soundex before insertion. Also you can save space and improve the run time somewhat if rather than many separate bloom filters you build one large one where each item is post ID + word. If you do that you can also insert each word bare so you get O(1) empty result sets, helpful if you're updating the results with every keystroke in a search box.
- StavrosK 13y agoHuh, very nice idea! That should, indeed save a ton of space and be much simpler when searching! I'll try that now, thank you. EDIT: Hmm, turns out it's pretty much the same size, which makes sense, I guess: http://nbviewer.ipython.org/gist/skorokithakis/0abbfebced25fd4b2ed3 http://nbviewer.ipython.org/gist/skorokithakis/0abbfebced25f...
- hedgehog 13y agoThe space savings for the same error rate should be small (I think the likelihood of false positives for a given load goes down slightly with size of the filter) but the benefit in lookup time should be significant for multiword searches. Thinking about it more though if you're doing live search you'll already have computed the results for the first word by the time you are given a second so maybe it doesn't matter.