> For example, my blog search engine, which indexes on the order of 500,000+ words across 1,000+ documents, can return results in < 10ms because the indices can be queried incredibly quickly.
This is odd. Let's do a back-of-the-envelope estimation. DDR4 bandwidth is at least 12GB/s. 500k words is around 3MB. So, reading this amount takes 0.25ms, ignoring CPU caches. It sounds reasonable to assume the matching algorithm can run in-between that speed and 40 times slower for the 10ms mark.
This is one example where precomputation is probably not needed: bruteforce if N is small enough.
This is odd. Let's do a back-of-the-envelope estimation. DDR4 bandwidth is at least 12GB/s. 500k words is around 3MB. So, reading this amount takes 0.25ms, ignoring CPU caches. It sounds reasonable to assume the matching algorithm can run in-between that speed and 40 times slower for the 10ms mark.
This is one example where precomputation is probably not needed: bruteforce if N is small enough.