(BigData 2020) MCF：Towards Window-based Multiple Cuckoo Filters in Stream Computing

Abstract: In this paper, we present a new stream-oriented filter, named Multiple Cuckoo Filter (MCF), to support concise representation and approximate membership queries for multiple sets with unpredicted cardinality. MCF is composed of a group of standard cuckoo filters with the same set dimension, in which the representation and membership query are decomposed into single set representation and query. MCF allows each cuckoo filter to be configured dynamically with changing sliding windows, and compare the fingerprints for the same key with each other, in order to find out whether a given item exists in multiple sets simultaneously. It is proved that MCF outperforms CF in false positive theoretically. Experiments demonstrate that the query delay of MCF grows linearly with the number of cuckoo filters, decreases gradually with the increments of the window size, and increases with the growth of set cardinality piecewise.

Authors: Ziyue Hu and Menglu Wu (Shenzhen Institutes of Advanced Technology, China); Xiaopeng Fan (Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China); Yang Wang (Shenzhen Institute of Advanced Technology, China); Cheng-Zhong Xu (University of Macau, China)

Email: zy.hu@siat.ac.cn, ml.wu@siat.ac.cn, fanxiaopeng1978@gmail.com, yang.wang1@siat.ac.cn, czxu@um.edu.mo