EE Seminar: Class Filter - a Fast, Efficient, and Concurrent Dynamic Filter
Electrical Engineering Systems Seminar
Speaker: Hagay Halperin
M.Sc. student under the supervision of Prof. Guy Even
Monday, 12th May 2025, at 15:00
Room 011, Kitot Building, Faculty of Engineering
Class Filter - a Fast, Efficient, and Concurrent Dynamic Filter
Abstract
Filters, such as the Bloom filter, are widely used approximate membership query (AMQ) data structures. Filters are fast, compact, and have a wide range of applications. Dynamic filters, which support insertions, queries, and deletions, often have a trade-off between space efficiency and performance and are often not scalable for a concurrent use case.
In this thesis, we introduce the class filter - a dynamic filter that is space efficient, fast, robust, supports full concurrency and has scalable concurrent performance compared to other filters. The class filter’s architectures strive to minimize the mean memory access count and prioritize false query performance. We introduce the pipeline technique to increase operation performance, which may be used in other filters and dictionaries. Additionally, we obtain a space lower bound for dynamic filters with a dual-pool structure, showing that asymmetry between the pools benefits the total filter’s space efficiency. Our simulations show that the class filter structure benefits from this asymmetry.
We evaluated our implementation against many reference dynamic filters in many scenarios. Our benchmarks focus on both single-threaded and multithreaded scenarios. We also explore the ”Fixed-DB” case, where concurrent queries are executed on an instance of an immutable filter. Our implementation shows competitive performance gains in all scenarios.
הרישום לסמינר יבוצע באמצעות סריקת הברקוד למודל
Registration to the seminar will be done by scanning the barcode for the Moodle
