[caust1c]

This is somewhat a faulty analysis. One could easily use a high accuracy bloom filter to store whether a search has definitely not been seen before, and that would be an estimate on the lower bound of the error margin.

[inlined]

Yup. This was actually an interview question I got from a former Google search engineer.