2026-04-17T02:52:21Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/195212026-02-04T07:34:28Zcom_2072_1033col_2072_452950

00925njm 22002777a 4500 dc Sanjuàs Cuxart, Josep author Barlet Ros, Pere author Solé Pareta, Josep author Andriuzzi, Gabriella author 2012 The problem of testing whether a packet belongs to a set of filtered addresses has been traditionally addressed using Bloom filters. They have a small memory footprint and require few memory accesses per query and insertion, while presenting a small probability of false positive. The problem of automatic eviction of filtered addresses after a pre-configured time window is more challenging, since it requires tracking insertion times for later removal. This has been achieved in the literature by replacing the Bloom filter's vector of bits for a vector of timestamps. This approach precisely expires old items from the filter, but has a large memory footprint. We present a novel Bloom filter based data structure that features approximate information expiration. This small extra source of error allows for a more compact filter representation, thus becoming more suitable to fit in more expensive, faster memory. Additionally, our data structure is more flexible in that it allows for balancing the trade-off between filtering and expiration accuracy. Our experiments show that this method can obtain up to orders of magnitude higher overall accuracy than the time-stamp approach using the same amount of memory. Peer Reviewed Postprint (published version) Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors::Xarxes de banda ampla Computer networks -- Management Broadband communication systems Accuracy Data structures Maintenance engineering Memory management Monitoring Radiation detectors Time measurement Xarxes de comunicacions -- Gestió Telecomunicació de banda ampla, Sistemes de A lightweight algorithm for traffic filtering over sliding windows