An Enhanced Marked Cuckoo Filter for Multi-Set Multi-Membership Querying in Distributed System

The issue of multi-set membership query is a fundamental task in the fields of distributed systems and computer networks. It entails identifying which sets, out of n sets <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{0}, S_{1},{\ldots }, S_{n-1}$</tex-math></inline-formula>, in a Multi Set Multi-Membership Querying (MS-MMQ) contain a given element q. To address this problem while minimizing space usage, probabilistic data structures, such as cuckoo filters, are commonly employed. However, existing sketch data structures struggle to effectively balance scalability and query efficiency. To address this challenge, we introduce an enhanced marked cuckoo filter (EMCF), which enhances support for MS-MMQ scenarios by incorporating set markers after the fingerprint field. Additionally, it grants horizontal scalability and collaborative search capabilities at the filter level through the inclusion of global markers. Furthermore, we have developed an optimized variant of the enhanced marked cuckoo filter (EMCF-V) for multi-set scenarios to achieve space optimization. Experimental results using real-world datasets demonstrate that EMCF exceeds CSC-CF by more than 10 times in terms of speed, and EMCF-V exhibits a 33.3% higher query efficiency than CSC-CF methods, particularly in multiset scenarios.