WO2024255927A1 - Cuckoo filter, data insertion method, data query method and data deletion method - Google Patents

Abstract

The present invention relates to the technical field of computer information representation and retrieval. Provided are a cuckoo filter, a data insertion method, a data query method and a data deletion method. The cuckoo filter is composed of a fingerprint record table and a position flag table. The fingerprint record table is composed of m buckets and is used for storing inserted data fingerprints, each bucket having b slots for storing the data fingerprints. The position flag table is composed of m vectors, with one vector being created for each bucket, and the position flag table is used for recording insertion position information of the data fingerprints in the fingerprint record table. Each data fingerprint corresponds to two candidate buckets, one slot of one bucket is selected from the two candidate buckets to store the data fingerprint, and when and only when the data fingerprint is finally stored in a second candidate bucket, a position subscript value of the slot is recorded in a vector corresponding to the second candidate bucket. The present invention has a higher data fingerprint calculation efficiency and a lower data query false positive rate, and solves the technical problem of query false positives occurring in a cuckoo filter.

Description

A cuckoo filter and data insertion, query and deletion method

CROSS-REFERENCE TO RELATED APPLICATIONS

The invention claims priority to the Chinese patent application filed with the State Intellectual Property Office of China on June 15, 2023, with application number 202310712462.5 and invention name “A Cuckoo Filter and Data Insertion, Query and Deletion Method”, the entire contents of which are incorporated by reference into the present invention and constitute a part of the present invention for all purposes.

Technical Field

The invention belongs to the technical field of computer information representation and retrieval, and in particular relates to a cuckoo filter and a data inserting, querying and deleting method.

Background Art

The statements in this section merely provide background information related to the present invention and do not necessarily constitute prior art.

The approximate membership query data structure (AMQ) stores the probabilistic representation of a key set S on a data domain U in a compact format, and supports data insertion and query operations. Some AMQs support data deletion operations. For queries on existing elements in a set, it can efficiently complete set membership queries. For queries on elements outside the set, it has a controllable false alarm probability (hereinafter referred to as the false positive rate), that is, when querying an element that does not exist in the set, there is a certain probability that the element is returned to the set. The biggest feature of AMQ is its high space efficiency. Under an acceptable false positive rate, AMQ can work on devices with limited memory resources such as network routers, switches or loT devices.

Bloom Filter (BF) is a typical example of AMQ, which supports insert and query operations on a set S of keys. If the query is for a key that exists in set S, the Bloom filter can quickly complete the query; for keys outside set S, since it is a probabilistic structure, the probability of returning "not present" is at least 1-ε, where n is the number of elements that have been added, k is The number of hash functions is used, and m represents the length of the Bloom filter, which indicates that BF provides a controllable false positive rate ε. It provides a trade-off mechanism between space efficiency and query accuracy, that is, the length of the Bloom filter directly affects the false positive rate. The longer the Bloom filter, the greater its false positive rate. In addition, the number of hash functions also needs to be weighed. The more the number, the lower the efficiency of the Bloom filter, but if there are too few, the false positive rate will become higher. In recent years, BF has been widely used in packet classification, payload inspection of deep packet inspection (DPI), reducing disk I/O, avoiding database cache penetration, and data services on mobile terminals and IoT devices - distributed connections and semi-connections, indexing, auxiliary metadata and query processing problems. The main advantage of its application is that a large number of classification rules can be stored and accessed in a very compact form in dedicated hardware such as FPGA under the premise of limited space. In the past decade, Bloom filters have been a common solution when hardware storage space is limited or frequent access to external memory leads to high latency.

Compared with ordinary hash tables or binary trees, the main advantages of BF are fixed size and constant query and insertion efficiency independent of the number of elements in the structure; the main disadvantage of BF is that it does not support data deletion operations. Counting Bloom Filter (CBF) solves the problem that BF does not support data deletion, but it requires three to four times more space than BF to maintain the same false positive rate as BF, and once the required storage space is larger than RAM, the filter performance will drop significantly, because BF uses random read and write and cannot be effectively expanded to external memory, such as flash memory; secondly, the false positive rate of the filter has been reduced to a very low level, but there is still a certain probability of false query alarms.

Recently, some scholars proposed BF with False Positive Free Zone (FPFZ). By using the mapping of elements to positions with special properties in the filter, they achieved that when the number of elements inserted in the filter is less than a given threshold, the false positive rate in a given domain will be completely eliminated; however, in all cases, FPFZ is very small, and the supported domains and data amounts are also limited, which greatly limits the scope of application of this technology.

Compared with BF, Cuckoo Filter (CF) supports dynamic deletion of data. In terms of space efficiency, CF uses a hash function to calculate and save the fingerprint of the original set data instead of the original data, which ensures a low false positive rate and occupies less space. In terms of time efficiency, CF uses cuckoo hash to calculate the element insertion position, but in the process of element insertion, due to the existence of hash collision, There is a certain probability that data relocation is needed; a large amount of research work has further optimized the insertion performance and query performance of the cuckoo filter, reducing the probability of relocation during element insertion and the memory usage of the filter itself; the cuckoo filter structure determines that there is a contradictory relationship between the false positive rate and space efficiency, and the two are mutually exclusive. Therefore, the optimization of the cuckoo filter needs to comprehensively consider the false positive rate of its structure and the required memory space.

At present, many experts and scholars have made structural and algorithmic improvements to CF for different application scenarios. In terms of balancing the storage space and false positive rate of the cuckoo filter, it is understood that no work has eliminated the false positive rate of the cuckoo filter, and the cuckoo filter variants proposed in most works have serious efficiency problems. Therefore, further research and optimization of the structure of CF is still needed.

Summary of the invention

In order to overcome the deficiencies of the above-mentioned prior art, the present invention provides a cuckoo filter and a method for inserting, querying and deleting data. The constructed cuckoo filter consists of a fingerprint record table (Fingerprint Record Table, FRT) and a position flag table (Position Flag Table, PFT). FCT is used to save the fingerprint of the inserted data, and PFT is used to record the insertion position information of the fingerprint of the data in the fingerprint table, so as to solve the technical problem of false positive query in the cuckoo filter.

To achieve the above objectives, one or more embodiments of the present invention provide the following technical solutions:

A first aspect of the present invention provides a cuckoo filter.

A cuckoo filter, consisting of a fingerprint record table and a position mark table;

The fingerprint record table is composed of m buckets for storing inserted data fingerprints, wherein each bucket has b slots for storing data fingerprints;

The position mark table is composed of m vectors, and a vector is created for each bucket to record the insertion position information of the data fingerprint in the fingerprint record table;

Among them, each data fingerprint corresponds to two candidate buckets, and a slot of one bucket is selected to save the data fingerprint. If and only if it is finally saved in the second candidate bucket, the position subscript value of the slot is recorded in the vector corresponding to the second candidate bucket.

Furthermore, the number m of the buckets is an exponential power of 2.

Furthermore, the data fingerprint is calculated as follows:

Get the data to be inserted;

The data summary of the data to be inserted is calculated through the hash function and modulus operation:
dig _x = _ha (x) ^mod2n

Where n is the length of the data summary, and _ha (·) represents a hash function with a fixed-length output;

Based on the data to be inserted and the data summary, the low-order part of the data summary is directly used as the data fingerprint of the data to be inserted.

Furthermore, the two candidate buckets are calculated as follows:

in, represents the first candidate bucket, represents the second candidate bucket, x represents the data to be inserted, dig _x represents the data summary, f _x represents the data fingerprint, l is the fingerprint length, h _b (·) represents the hash function with fixed-length output, and m represents the number of buckets.

A second aspect of the present invention provides a data inserting method.

A data insertion method, based on a cuckoo filter provided in the first aspect, when inserting a data x, firstly calculates the data summary dig _x corresponding to x, the data fingerprint f _x and two candidate buckets Then insert, the insertion process is:

Select an empty slot e _j from the two candidate buckets to save the data fingerprint. If there are no empty slots in the two candidate buckets, select a slot e _j , evict the original data fingerprint f _x' in the slot e _j through the eviction process, and save the data fingerprint f _x to the empty slot e _j ;

If the data fingerprint f _x is finally saved in the second candidate bucket, the position index value j of slot e _j is stored in the bucket The corresponding vector.

Furthermore, the process of selecting an empty slot _ej of one bucket from two candidate buckets to store the data fingerprint is divided into two cases:

(1) If both candidate buckets have empty slots, a bucket is randomly selected and the data fingerprint is stored in any empty slot e _j , j∈[0,b), where j is the position index value of slot e _j ;

(2) If only one of the two candidate buckets has an empty slot, the data fingerprint is stored in any empty slot e _j of the bucket, j ∈ [0, b), where j is the position index value of slot e _j .

Furthermore, if there are no empty slots in the two candidate buckets, the eviction process is as follows:

Randomly select a bucket from the two candidate buckets, randomly evict the data fingerprint f _x' in any slot e _j , j∈[0,b) in the bucket, and store f _x in e _j , and update the bucket Corresponding vector The position subscript value of ;

The evicted element f _x' calculates the dual position of the current insertion position. If there is an empty slot in the bucket, f _x' is inserted into the empty slot and the position subscript value of the corresponding vector is updated. If there is no empty slot, the eviction process is repeated until all items are stored in the filter.

A third aspect of the present invention provides a data search method.

A data search method, based on a cuckoo filter provided in the first aspect, when searching for a data y, firstly calculates the data summary dig _x corresponding to y, the data fingerprint f _y and two candidate buckets Then match the data fingerprint f _y with all the fingerprints in the two buckets:

If the first candidate bucket If the fingerprint stored in slot e _j ,j∈[0,b) matches f _y , then Search for j in the search, if it does not exist, return a successful search, otherwise return a failed search;

If the second candidate bucket If the fingerprint stored in slot e _k ,k∈[0,b) matches f _y , then Search for k in , if it exists, return a success, otherwise return a failure.

A fourth aspect of the present invention provides a data deletion method.

A data deletion method, based on a cuckoo filter provided in the first aspect, when deleting a data z, searching for the data fingerprint of the deleted data z, and performing subsequent operations in two cases:

If the search is successful, the data fingerprint is deleted from the corresponding position in the fingerprint record table, and the position mark in the corresponding vector is deleted, and a deletion success is returned;

If the search fails, it means that the element does not exist in the filter and the deletion fails.

Furthermore, the deletion operation when the search is successful is specifically as follows:

If the data fingerprint to be deleted is in the first candidate bucket, delete the data fingerprint from the first candidate bucket;

If the data fingerprint to be deleted is in the second candidate bucket, remove the data fingerprint from the second candidate bucket. , and delete the position mark in the vector corresponding to the second candidate bucket.

One or more of the above technical solutions have the following beneficial effects:

The present invention has higher data fingerprint calculation efficiency: in the data insertion stage, the low-order part of the data summary is directly used when obtaining the data fingerprint, which reduces a hash operation and reduces the data insertion delay.

The present invention has a lower false positive rate of data query: by only recording the position subscript value stored in the second candidate bucket, the array subscript is cleverly integrated into the data fingerprint, and the fingerprint comparison length is significantly increased without increasing the fingerprint length, and the false positive rate of the cuckoo filter is reduced by m times (m is the number of buckets in the fingerprint record table), and when the fingerprint length is 8 bits, in actual operation, there is an average of 93.1% probability that the false positive rate is 0; when the fingerprint length is 12 bits, compared with 0.04% of CF, the filter has a 99.3% probability that the false positive rate is 0.

The present invention has a smaller space cost under the same false positive rate: under the premise of a false positive rate of 0, the fingerprint length required by the filter is only 8.76993 bits, while CF requires 34.3597 bits.

Advantages of additional aspects of the present invention will be given in part in the following description, and in part will become obvious from the following description, or will be learned through practice of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings in the specification, which constitute a part of the present invention, are used to provide a further understanding of the present invention. The exemplary embodiments of the present invention and their descriptions are used to explain the present invention and do not constitute improper limitations on the present invention.

FIG. 1 is a schematic structural diagram of a cuckoo filter according to a first embodiment.

FIG. 2 is a schematic diagram of the structure of the fingerprint record table of the first embodiment.

3 is a diagram showing the proportion of 1 in all elements of the matrix F when the number of slots b=2, 4, 8 and the number of buckets m=2 ¹⁵ , 2 ²⁰ , 2 ²⁵ in the first embodiment.

FIG. 4 is a schematic diagram of the structure of the position mark table of the first embodiment.

FIG5 is a flow chart of a method according to the second embodiment.

FIG6 is a flow chart of a method according to the third embodiment.

FIG. 7 is a flow chart of a method according to a fourth embodiment.

DETAILED DESCRIPTION

It should be noted that the following detailed descriptions are illustrative and are intended to provide further explanation of the present application. Unless otherwise specified, all technical and scientific terms used in the present invention have the same meanings as those commonly understood by those skilled in the art to which the present application belongs.

It should be noted that the terms used herein are only for describing specific embodiments and are not intended to limit the exemplary embodiments according to the present application. As used herein, unless the context clearly indicates otherwise, the singular form is also intended to include the plural form. In addition, it should be understood that when the terms "comprise" and/or "include" are used in this specification, it indicates the presence of features, steps, operations, devices, components and/or combinations thereof.

Embodiment 1

In one or more embodiments, a cuckoo filter based on data fingerprint position marking is disclosed. FIG1 is a schematic diagram of the structure of the cuckoo filter. As shown in FIG1 , the filter is composed of a fingerprint record table (Fingerprint Record Table, FRT) and a position flag table (Position Flag Table, PFT). The fingerprint record table FCT is used to store the fingerprint of the inserted data, and the position flag table PFT is used to record the insertion position information of the data fingerprint in the fingerprint table.

(1) Fingerprint Record Form

FIG2 is a schematic diagram of the structure of the fingerprint record table. As shown in FIG2 , the fingerprint record table FCT is composed of m arrays (hereinafter referred to as buckets), where m must be an exponential power of 2. The benefit of this requirement is that when performing an XOR operation, it can be guaranteed that the calculated index must fall within the array; each bucket has b storage units e (hereinafter referred to as slots) that can store data fingerprints f.

Before inserting, searching or deleting data in the cuckoo filter, the data summary, data fingerprint and two candidate buckets corresponding to the data must be calculated. Taking the data x to be inserted as an example, first, the data summary of the data x to be inserted is calculated:
dig _x = _ha (x) mod 2 ⁿ (1)

Where n is the length of the data summary, and _ha (x) is a hash function that outputs a binary string of a specific length.

Then, based on the data to be inserted and the data digest, the low-order part of the data digest is directly used as the The data fingerprint of the input data is expressed as follows:
f _x = dig _x mod 2 ^l (2)

Where l is the fingerprint length; directly taking the low-order part of the data summary as the data fingerprint of the data to be inserted reduces one hash operation, reduces the data insertion delay, and has higher data fingerprint calculation efficiency.

Finally, determine the two different candidate bucket locations for inserting data x:

Wherein, h _b (x) is a hash function with fixed-length output.

(2) Position marker table PFT

The position marking table PFT in this embodiment does not use the conventional matrix Fm _×b composed of 0 and 1 to record the storage position information of the data fingerprint in the fingerprint recording table FCT, but only records the position subscript value stored in the second candidate bucket. Under the premise of not increasing the fingerprint length, the fingerprint comparison length is significantly increased, thereby reducing the false positive rate of data query.

In the conventional way of thinking, 1 bit is used to indicate the position of the bucket where each data fingerprint is inserted, 0 and 1 respectively indicate the _p1 position and _p2 position, and the position marker table PFT is a matrix _Fm×b composed of 0 and 1, each row occupies b bits, and the memory space required to store the position marker table PFT is mb bits. Due to the collision of the hash function, the load of the filter cannot reach 100%, so there are many empty slots in the fingerprint record table FRT, and F is a zero matrix when initialized, so bit 0 also indicates that the corresponding position of the fingerprint record table FRT is empty, which means that a lot of invalid position information is stored in F.

By observing and analyzing the characteristics of data insertion in the existing cuckoo filter, it is found that most data fingerprints will be inserted into their p ₁ position. Figure 3 shows the proportion of 1 in all elements of the matrix F when the number of slots b = 2, 4, 8 and the number of buckets m = 2 ¹⁵ , 2 ²⁰ , 2 ^25. This means that the number of 0s in the matrix F is much greater than 1. In extreme cases, the matrix F is approximately a sparse matrix.

Based on this conclusion, only the subscript of the data fingerprint inserted into the second candidate bucket p ₂ in each bucket is saved, and the position marking table PFT is composed of m vectors, each vector saves the fingerprint record Table FRT corresponds to the position subscripts of the data fingerprint inserted into the p ₂ position in the bucket, and the size of each subscript is log b bits. Figure 4 is a schematic diagram of the structure of the position marking table.

With the help of the location information of the position tag table PFT, during the data query process, if a matching fingerprint is found in the fingerprint record table FRT, it is also necessary to confirm in the corresponding vector of the position tag table PFT that the two fingerprints are from the same bucket position, that is, whether the subscripts of the two fingerprints in the bucket can be queried in the corresponding vector, as shown in Figure 4. The fingerprint of the data y to be queried is hashed to bucket[i+1], and bucket[i+1] is the p ₂ position of y. Assuming that the fingerprint of x in the position tag table FRT matches y, the position subscript in the bucket of x is found in vector[i+1], indicating that the current bucket is also the p ₂ position of x, which means that the entire data summary of x and y is the same, so the search is returned successful.

Embodiment 2

In one or more embodiments, a data insertion method based on a cuckoo filter is disclosed. The cuckoo filter based on data fingerprint position mark provided in the first embodiment is used. When inserting a data x, the data summary dig _x corresponding to x is first calculated, and then the fingerprint f _x of x and two candidate buckets are calculated. The data insertion process is shown in Figure 5, and the insertion algorithm is shown in Table 1. The insertion process is divided into three cases:

(1) If two candidate buckets and There are empty slots, so a bucket is randomly selected. Store the fingerprint f _x in any empty slot e _j , j∈[0,b). If i=2, that is, the data fingerprint f _x is finally stored in the second candidate bucket, then store j in

(2) If there is only one bucket among the two candidate buckets If there are empty slots left in the bucket, f _x is stored in any empty slot e _j of the bucket, j∈[0,b). If i=2, that is, the data fingerprint f _x is finally stored in the second candidate bucket, then j is stored in

(3) If both candidate buckets have no empty slots, and Randomly select a bucket Random eviction The data fingerprint f _x' in any slot e _j ,j∈[0,b) in the , and stores f _x in e _j . equal and equal Then in the vector Insert j in equal and equal Then in the vector If i = 2, that is, the data fingerprint f _x is finally saved in the second candidate bucket, then j is stored in

The evicted element f _x' calculates the dual position of the current insertion position If there is an empty slot in the bucket, f _x' is inserted into the empty slot and the position index value of the corresponding vector in the PFT is updated. If there is no empty slot, the above eviction process is repeated until all items are stored in the filter. There is a maximum number of evictions MAXKICKNUM. If the eviction process exceeds MAXKICKNUM, the element insertion fails and the algorithm exits.

Table 1 Insertion algorithm

Embodiment 3

In one or more embodiments, a data search method based on a cuckoo filter is disclosed. The cuckoo filter based on data fingerprint position mark provided in the first embodiment is used. The data search process is shown in FIG6 , and the search algorithm is shown in Table 2. When searching for a data y, the data summary dig _y and the data fingerprint f _y of y are first calculated, and then the two insertion candidate bucket positions of y are calculated. Match the data fingerprint f _y with all the fingerprints in the two buckets:

If the bucket If the fingerprint stored in slot e _j ,j∈[0,b) matches f _y , then Search for j in , if it does not exist, return a success, otherwise return a failure.

If the bucket If the fingerprint stored in slot e _k ,k∈[0,b) matches f _y , then Search for k in , if it exists, return a success, otherwise return a failure.

Table 2 Search algorithm

Embodiment 4

In one or more embodiments, a data deletion method based on a cuckoo filter is disclosed. The cuckoo filter based on data fingerprint position marking provided in the first embodiment is used. The deletion process is shown in FIG7 , and the deletion algorithm is shown in Table 3. When deleting a data z, the element z to be deleted is first searched in the filter by the search method provided in the third embodiment, and corresponding operations are performed according to the search results:

(1) If the search is successful, the fingerprint is deleted from the corresponding position in the FRT and the The position mark in the PFT corresponding vector returns the deletion success, specifically:

If the data fingerprint to be deleted is in the first candidate bucket, delete the data fingerprint from the first candidate bucket;

If the data fingerprint to be deleted is in the second candidate bucket, the data fingerprint is deleted from the second candidate bucket, and the position mark in the vector corresponding to the second candidate bucket is deleted.

(2) If the search fails, it means that the element does not exist in the filter and the deletion fails.

Table 3 Deletion algorithm

The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and variations. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included in the protection scope of the present invention.

Claims (9)

The cuckoo filter based on data fingerprint position marking is characterized by being composed of a fingerprint record table and a position marking table; The fingerprint record table is composed of m buckets for storing inserted data fingerprints, wherein each bucket has b slots for storing data fingerprints; The position mark table is composed of m vectors, and a vector is created for each bucket to record the insertion position information of the data fingerprint in the fingerprint record table; Each data fingerprint corresponds to two candidate buckets, and the calculation method of the two candidate buckets is specifically as follows:

in, represents the first candidate bucket, represents the second candidate bucket, x represents the data to be inserted, dig _x represents the data summary, f _x represents the data fingerprint, l is the fingerprint length, h _b (·) represents the hash function with fixed-length output, and m represents the number of buckets; a slot of a bucket is selected to save the data fingerprint. If and only if it is finally saved in the second candidate bucket, the position subscript value of the slot is recorded in the vector corresponding to the second candidate bucket. The cuckoo filter based on data fingerprint position marking as described in claim 1 is characterized in that the number of buckets m is an exponential power of 2. The cuckoo filter based on data fingerprint position marking according to claim 1, characterized in that the data fingerprint is calculated in the following manner: Get the data to be inserted; The data summary of the data to be inserted is calculated through the hash function and modulus operation:
dig _x = _ha (x) ^mod2n Where n is the length of the data summary, and _ha (·) represents a hash function with a fixed-length output; Based on the data to be inserted and the data summary, the low-order part of the data summary is directly used as the data fingerprint of the data to be inserted. A data insertion method based on a cuckoo filter, characterized in that the cuckoo filter is a cuckoo filter based on data fingerprint position marking according to any one of claims 1 to 3, when inserting a data x, firstly calculate the data summary dig _x corresponding to x, the data fingerprint f _x and two candidate buckets Then insert, the insertion process is: Select an empty slot e _j from the two candidate buckets to save the data fingerprint. If there are no empty slots in the two candidate buckets, select a slot e _j , evict the original data fingerprint f _x' in the slot e _j through the eviction process, and save the data fingerprint f _x to the empty slot e _j ; If the data fingerprint f _x is finally saved in the second candidate bucket, the position index value j of slot e _j is stored in the bucket The corresponding vector. The data insertion method based on the cuckoo filter according to claim 4 is characterized in that the selecting an empty slot e _j of one bucket from the two candidate buckets to store the data fingerprint is specifically divided into two cases: (1) If both candidate buckets have empty slots, a bucket is randomly selected and the data fingerprint is stored in any empty slot e _j , j∈[0,b), where j is the position subscript value of slot e _j ; (2) If only one of the two candidate buckets has an empty slot, the data fingerprint is stored in any empty slot e _j of the bucket, j ∈ [0, b), where j is the position index value of slot e _j . The data insertion method based on cuckoo filter according to claim 4 is characterized in that, if both candidate buckets have no empty slots, the eviction process is specifically as follows: Randomly select a bucket from the two candidate buckets, randomly evict the data fingerprint f _x' in any slot e _j , j∈[0,b) in the bucket, and store f _x in e _j , and update the bucket Corresponding vector The position subscript value of ; The evicted element f _x' calculates the dual position of the current insertion position. If there is an empty slot in the bucket, f _x' is inserted into the empty slot and the position subscript value of the corresponding vector is updated. If there is no empty slot, the eviction process is repeated until all items are stored in the filter. A data search method based on a cuckoo filter, characterized in that the cuckoo filter is a cuckoo filter based on data fingerprint position marking as described in any one of claims 1 to 3, when searching for a data y, firstly calculate the data summary dig _x corresponding to y, the data fingerprint f _y and two candidate buckets Then match the data fingerprint f _y with all the fingerprints in the two buckets: If the first candidate bucket If the fingerprint stored in slot e _j ,j∈[0,b) matches f _y , then Search for j in the search, if it does not exist, return a successful search, otherwise return a failed search; If the second candidate bucket If the fingerprint stored in slot e _k ,k∈[0,b) matches f _y , then Search for k in , if it exists, return a success, otherwise return a failure. A data deletion method based on a cuckoo filter, characterized in that the cuckoo filter is a cuckoo filter based on a data fingerprint position mark as claimed in any one of claims 1 to 3, when deleting a data z, searching for the data fingerprint of the deleted data z, and performing subsequent operations in two cases: If the search is successful, the data fingerprint is deleted from the corresponding position in the fingerprint record table, and the position mark in the corresponding vector is deleted, and a deletion success is returned; If the search fails, it means that the deleted data z does not exist in the filter, and the deletion fails. The data deletion method based on the cuckoo filter according to claim 8 is characterized in that the deletion operation when the search is successful is specifically: If the data fingerprint to be deleted is in the first candidate bucket, delete the data fingerprint from the first candidate bucket; If the data fingerprint to be deleted is in the second candidate bucket, the data fingerprint is deleted from the second candidate bucket, and the position mark in the vector corresponding to the second candidate bucket is deleted.