It says that a query is done on each BF, even on the ones that were added after the initial storage. So suppose we have only 2 iterations. In the first BF, there's k0 hash functions and in the 2nd (iteration) BF, there's now k1 hash functions.
So naturally, an item is stored using the k0 hash functions. But in order to query, I run against k1 hash functions which is a larger set. If any one of the k1-k0 extra hash functions returns 0, won't that be a false negative?
Yes, you are right - you have to query each filter.
To keep the contract of the bloom filter, a "no" can only come if ALL filters return no. So if one of the filters return 0 and the other returns 1, the answer is maybe (i.e. a yes with some false positive probability). If we instead answered no, it would be a false negative as you stated, so we can't do that. This paper doesn't defeat this property of bloom filters.
The cool insight in this paper is that how you choose the new filter size allows for a relatively nice tradeoff of "wasted" size, and a target for the effective false positive ratio, even in the face of growth. We are increasing the probability for false positives, but depending on how you pick the sizes, you can do better than if you simply allocated another bloom of the same size, forever and ever.
(When I say "wasted" size, I mean the extra bits you need to get a certain false positive ratio, when you compare it to a properly sized filter from the get-go. In essence, you're paying some overhead when you get to a certain size. In exchange, you do not need to have guessed the size correctly / allocated all that memory from the get-go.)
It says that a query is done on each BF, even on the ones that were added after the initial storage. So suppose we have only 2 iterations. In the first BF, there's k0 hash functions and in the 2nd (iteration) BF, there's now k1 hash functions.
So naturally, an item is stored using the k0 hash functions. But in order to query, I run against k1 hash functions which is a larger set. If any one of the k1-k0 extra hash functions returns 0, won't that be a false negative?