My nitpicking was more about how they were presented. If you are simply using a bloom filter to avoid random disk access on the database, then no, you haven't lost accuracy in your system-as-a-whole.

Also, and I guess this is more fuzzy, my perception is that set-membership algorithms, for very large sets, are largely used in search and recommendation. These problems have unique properties: if you get the top N right, the ordering of the rest hardly matters. Contrast this with regression or classification, where you are looking for a global result.

Also, I agree that it is generally a bad idea to use linear data structures in streaming algorithms, but they are not automatically out in practice (as opposed to the CS literature). If you can keep the constant factor small.