In the last decade, significant efforts have been made to reduce the false positive rate of approximate membership checking structures. This has led to the development of new structures such as cuckoo filters and xor filters. Adaptive filters that can react to false positives as they occur to avoid them for future queries to the same elements have also been recently developed. In this paper, we propose a new type of static filters that completely avoid false positives for a given set of negative elements and show how they can be efficiently implemented using xor probing filters. Several constructions of these filters with a false positive free set are proposed that minimize the memory and speed overheads introduced by avoiding false positives. The proposed filters have been extensively evaluated to validate their functionality and show that in many cases both the memory and speed overheads are negligible. We also discuss several use cases to illustrate the potential benefits of the proposed filters in practical applications.
翻译:过去十年来,为降低会员近似检查结构的假正率作出了重大努力,这导致开发了新的结构,如库库过滤器和xor过滤器等。最近还开发了适应性过滤器,这些过滤器可以对假正数作出反应,避免出现假正数,从而避免今后对相同要素进行查询。在本文件中,我们提议了新型静态过滤器,完全避免对特定一组负数进行假正数检查,并表明如何利用xor检验过滤器有效地实施这些过滤器。我们建议用假正数自由设置来尽量减少错误正数过滤器的内存和速度,避免假正数,从而尽量减少内存和速度管理器。已经对拟议的过滤器进行了广泛评估,以验证其功能,并表明在许多情况下,记忆和速度管理器都微不足道。我们还讨论了一些使用案例,以说明拟议过滤器在实际应用中的潜在好处。