4 ms·

Even with modern computers doing a naive regex search on 1GiB+ of full text would take a while. Memory isn't that fast. The trigrams helps you avoid needing to

Even with modern computers doing a naive regex search on 1GiB+ of full text would take a while. Memory isn't that fast. The trigrams helps you avoid needing to read every document on every search. Even a traditional rdbms will start become slow with datasets in the 10-100GiB range. Note that products like bigquery, snowflake, redshift...etc might be able to support but that is not Cheap or relatively fast

z3t4 8y ago
I think you can expect 1TB/s per machine. With one thousand servers you could search the entire web in 0.05 seconds. Not all data-sets are that big though. You should at least try the most naive method before applying any optimizations. Dividing everything up in words is a smart machine optimization, but it gets silly ... Imagine for example cutting out all words from a bunch of paper articles, then write down the name of the article at the back. Then sort all words and put them in different jars. Now when you want to find an article you pick a piece from a word-jar, then just look at the back-side! But now to the hard problem, what if the jar has thousands of small pieces in it ?
- nerpderp82 8y ago
  The fastest main memory bandwidth supported on modern servers is a dual socket AMD Epyc [0] with a theoretical maximum of 320GB/s. One TB/s is non-sense. That said, I approve of naive brute-force and one should always benchmark their systems against the brute force solution. [0] https://en.wikichip.org/wiki/amd/epyc/7551 https://en.wikichip.org/wiki/amd/epyc/7551
  - z3t4 8y ago
    You also have to take into account the trade-offs! In my paper-clips in a jar example, lets say we want to find the string "var foo = bar" you take one clip from the "var" jar, but almost all files has "var" in it ... and there are also many files that has "foo" and "bar" in it! How do you sort the answers from there !? With a simple text/regex search you wouln't have that problem!

z3t4 8y ago

I think you can expect 1TB/s per machine. With one thousand servers you could search the entire web in 0.05 seconds. Not all data-sets are that big though. You should at least try the most naive method before applying any optimizations. Dividing everything up in words is a smart machine optimization, but it gets silly ... Imagine for example cutting out all words from a bunch of paper articles, then write down the name of the article at the back. Then sort all words and put them in different jars. Now when you want to find an article you pick a piece from a word-jar, then just look at the back-side! But now to the hard problem, what if the jar has thousands of small pieces in it ?

nerpderp82 8y ago
The fastest main memory bandwidth supported on modern servers is a dual socket AMD Epyc [0] with a theoretical maximum of 320GB/s. One TB/s is non-sense. That said, I approve of naive brute-force and one should always benchmark their systems against the brute force solution. [0] https://en.wikichip.org/wiki/amd/epyc/7551 https://en.wikichip.org/wiki/amd/epyc/7551
- z3t4 8y ago
  You also have to take into account the trade-offs! In my paper-clips in a jar example, lets say we want to find the string "var foo = bar" you take one clip from the "var" jar, but almost all files has "var" in it ... and there are also many files that has "foo" and "bar" in it! How do you sort the answers from there !? With a simple text/regex search you wouln't have that problem!