argusdusty

I did say "requiring quadratic memory from every word." I'm not sure you can really call that linear - it's O(n m^2), where n is the number of words, and m is the average word length. It's not the O(n m) that Ferret achieves.

For even a medium sized dictionary of a few dozen MB, you'll find yourself quickly running out of memory. The 4MB dictionary running on the demo would jump to 328MB. Both a Trie and a binary search tree (both of which I've coded and tested) take significantly more memory, and the binary search tree is somewhat slower (try doing a tree traversal between two points as fast as the same traversal over an array).

EDIT: I'll just reply to your edit here for simplicity and because I really don't want to start another thread as I have to get to sleep. I view m as about as constant as n - adding or subtracting words generally changes them both. Try thinking of m as c/n, where c is the total number of characters in your dictionary. O(n m^2) -> O(c^2 / n), whereas ferret uses O(c). The 1,000,000 most frequent English words might have an m of 6-7, but the 100,000 longest English words might have an m of 12-15, taking more memory in a trie, but less memory in Ferret.

But the point is really irrelevant, tbh. We both know how m and n work, and how much memory the trie and Ferret cost for different dictionaries, which is all that should really matter.

Because a trie works great for prefix searches, but we want substring searches, so we'd have to modify the trie to be more like a suffix tree, in it's simplest form inserting each possible suffix into the trie and doing a prefix search over that. For each word, adding up the length of each suffix gives quadratic memory.

This is a good idea :) I'll probably add in a module for phonetic matching when I get the time.

EC2 medium instances come with 480GB space. Our database currently takes roughly 60GB.

Ferret isn't running on this entire database, though - it's for auto-complete searches over our artist names, roughly 4MB.

EDIT: Since I can't seem to reply to fleitz' below comment, I'll post a response here:

1. Boyer-Moore takes linear time. Ferret takes logarithmic time. Also, it's intended for searching over a single string, so using it on a dictionary would require some sort of hack like a termination character, taking slightly more memory and time.

2. A trie was one of the original iterations of Ferret. The reason it lost out was memory usage, requiring quadratic memory from every word (because this is a suffix search, not just a prefix search).

Thanks for the heads-up. It should be working now.

The $150 per month includes several other servers we run. The server running our core app backend costs under half that, and handles our requirements just fine. Spending another $80 per month to save me development time is a cost we, as a poorly funded startup, simply cannot afford.

Author here: They are unrelated.

We did take the time to examine writing our own full search engine based on Lucene, like the aforementioned search library. The reasons why we didn't are briefly mentioned in the blog post, but simply put, we found Lucene too bloated for our purposes (intended for large-scale data retrievals, among many other things). We just needed a low-cost search over a relatively small dictionary, which could be used in an auto-complete field without stealing resources from other processes, such as our recommendation engine.

Looking over the source code, this doesn't really look secure. A few notes:

1. Any decryption key which is shorter than the length of the encrypted data must be fake. This forces fake decrypted data to be the same length as the real decrypted data, which is impractical for large files.

2. There's no verification on any key, and it's quite trivial to produce fake keys, so should the 'government' want to claim you had illegal data, all they would have to do is produce their own 'fake key' corresponding to said illegal data.

3. Passwords are essentially random data - impossible to memorize. You'll have to keep them on your computer somewhere, and given their unusual nature in relation to other files, it would be pretty easy to do a search for them.

I'd advise sticking to hidden volumes on TrueCrypt for now.