National University of Defense Technology

Shangsen Li

Deke Guo

Lailong Luo

Long Zheng

Yahui Wu

Pengtao Fu

Yi Wang

Yiting Chen

A method and an apparatus for data filtering are provided in this disclosure. The method is applied to a filtering system, including m buckets, each bucket including b storage slots, and each storage slot including a first domain and a second domain. The first domain is configured for recording fingerprint information of an element fingerprint of a data element, and the second domain is configured for matching and recording identifiers corresponding to the fingerprint information stored in the first domain. The method includes: determining an element fingerprint of a data element to be processed in response to an obtained target instruction; and performing a target operation on the data element based on at least the element fingerprint and stored information of the first domain and the second domain in each storage slot. The target operation at least includes one or more of inserting, querying and deleting operations.

Method and apparatus for data filtering

A method for updating a stable cuckoo filter used for membership testing of data streams, executed by a processor, is described. The method includes the steps of: performing a first hash on a first element to be inserted into the stable cuckoo filter to determine a first candidate bucket; performing a second hash on a fingerprint of the first element to determine a second candidate bucket; selecting a target candidate bucket from a group consisting of the first candidate bucket and the second candidate bucket; inserting the first element into the target candidate bucket; updating the stable cuckoo filter according to one or more of a random update strategy, an insertion failure update strategy, a scanning strategy, a skip scanning update strategy, a blocked design strategy and a local time-sensitive update strategy; and obtaining an updated stable cuckoo filter.

Stable cuckoo filter for data streams

Growing community of inventors

Hunan, China

Shangsen Li