Filter data structures can approximately determine whether an element exists in a given set.Typical filter data struc-tures,such as Bloom filters,cuckoo filters,and quotient filters,sacrifice query accuracy for lower memory space consumption and lower query time overhead.Due to their spatial and temporal efficiency,filter data structures are now widely used in approximate membership query operations in computer networks,the Internet of Things,database systems,file systems,bioinformatics,ma-chine learning,and other fields.Since the 1970s,filters have been extensively studied.Their research ideas are constantly chan-ging.This paper compiles the classic studies on filter data structures in the past fifty years,summarizes existing studies based on the mechanism of filter data structures and analyze the relationship between different studies.Finally,future research directions in filter data structures are discussed.
FilterApproximate membership queryProbabilistic data structureBloom filterCuckoo filterQuotient filter
NETL
NSTL
万方数据
