What is it about?
Filter data structures have been used ubiquitously since the 1970s to answer approximate set-membership queries in various areas of computer science including architecture, networks, operating systems, and databases. Such filters need to be allocated with a given capacity in advance to provide a guarantee over their performance and false positive rate. In many applications, however, the data size is not known in advance, requiring filters to dynamically expand. This paper shows how to expand filter data structures practically and efficiently.
Featured Image
Photo by Devin Avery on Unsplash
Perspectives
Filter data structures are not only important but also interesting and fun! This paper would be a good read for anyone who enjoys data structures.
Niv Dayan
University of Toronto
Read the Original
This page is a summary of: InfiniFilter: Expanding Filters to Infinity and Beyond, Proceedings of the ACM on Management of Data, June 2023, ACM (Association for Computing Machinery),
DOI: 10.1145/3589285.
You can read the full text:
Contributors
The following have contributed to this page
