גיל אינציגר

Bloom filters and their variants support membership or multiplicity queries with a low probabilistic error. For many networking applications, recent data is more significant than older data, motivating the need for sliding window solutions. In this work, we introduce Sliding Window Approximate Membership Protocol (SWAMP), a simple algorithm for membership and multiplicity queries over sliding windows. SWAMP is the first approximate set membership sliding window algorithm that is memory succinct, i.e., up to a factor of (1 + 0(1)) from the information theoretic lower bound, for constant error probabilities. It also operates in constant time and supports multiplicity queries with no additional overheads. Finally, we evaluate the memory consumption of SWAMP on a wide range of parameters and show a 25-40% reduction compared to the state of the art sliding Bloom filters (that cannot count). In summary, SWAMP improves the memory consumption of its competitors and can also count.