Seesaw Counting Filter: A Dynamic Filtering Framework for Vulnerable Negative Keys
Lists
Only you see this
Abstract
Bloom filter is an efficient data structure for filtering negative keys (keys not in a given set) with substantially small space. However, in real-world applications, there widely exist vulnerable negative keys, which will bring high costs if not being properly filtered, especially when positive keys are added/deleted dynamically. Such problem gets more severe when keys within one set are dynamically added or deleted. Recently, there are works focusing on handling such (vulnerable) negative keys by incorporating learning techniques. These learning-based filters fail to work as the learning techniques can hardly handle incremental insertions or deletions. To address the problem, we propose <u>S</u> ee <u>S</u> aw <u>C</u> ounting <u>F</u> ilter (SSCF), which is innovated with encapsulating the vulnerable negative keys into a unified counter array named seesaw counter array, and dynamically modulating (or varying) the applied hash functions to guard the encapsulated keys from being misidentified. Moreover, we design ada-SSCF to handle the scenarios where the vulnerable negative keys cannot be obtained in advance. We extensively evaluate our SSCF, which shows that SSCF outperforms the cutting-edge filters by <inline-formula><tex-math notation="LaTeX">$3\times$</tex-math></inline-formula> on averages regarding accuracy while ensuring a low operation latency. All source codes are in (SSCF-authors).
BibTeX
@article{li2023seesaw,
author = {Meng Li and Deyi Chen and Haipeng Dai and Rongbiao Xie and Siqiang Luo and Rong Gu and Tong Yang and Guihai Chen},
title = {{Seesaw Counting Filter: A Dynamic Filtering Framework for Vulnerable Negative Keys}},
journal = {IEEE Trans. Knowl. Data Eng.},
year = {2023},
url = {https://openreview.net/forum?id=Wvc1UiNE4w},
}Loading related content...