Flexible fingerprint cuckoo filter for information retrieval optimization in distributed network

Abstract

In a large-scale distributed network, a naming service is used to achieve location transparency and provide effective content discovery. However, fast and accurate name retrieval in the massive name set is laborious. Approximate set membership data structures, such as Bloom filter and Cuckoo filter, are very popular in distributed information systems. They obtain high query performance and reduce memory requirements through the abstract representation of information, but at the cost of introducing query error rates, which will ultimately affect content service quality. In this paper, in order to obtain higher space utilization and a lower query false positive rate, we propose a flexible fingerprint cuckoo filter (FFCF) for information storage and retrieval, which can change the length and type of fingerprints adaptively. In our scheme, FFCF uses longer fingerprints under low occupancy and has the ability to correct errors by changing the type of stored fingerprints. Moreover, we give a theoretical proof and evaluate the performance of FFCF by experimental simulations with synthetic data sets and real network packets. The results demonstrate that FFCF can improve memory utilization, significantly reduce false positive errors by nearly 90$\%$ at 50$\%$ occupancy and outperform Cuckoo filter in the full range of occupancy.