Rolling bloom filter for data with retention policy

摘要

A data structure comprising two or more sub data structures representing a given data set is maintained. Each of the two or more sub data structures comprises an array of bit positions and has a set of hash functions associated therewith. Each of the hash functions is operable to map an element of the given data set to at least one of the bit positions of the array. One of the two or more sub data structures is recognized as a master sub data structure and the others of the two or more sub data structures as slave sub data structures. Insertion and deletion of elements in the data structure is based on the recognition of each of the two or more sub data structures as the master sub data structure or one of the slave sub data structures.

主权项

1. An apparatus, comprising:
a memory storing a data structure comprising two or more sub data structures representing a given data set, each of the two or more sub data structures comprising an array of bit positions and having a set of hash functions associated therewith, wherein each of the hash functions is operable to map an element of the given data set to at least one of the bit positions of the array; and at least one processor device coupled to the memory and configured to sequentially recognize one of the two or more sub data structures as a master sub data structure and the others of the two or more sub data structures as slave sub data structures during a master sub data structure rotation cycle, wherein insertion and deletion of elements in the data structure is based on the recognition of each of the two or more sub data structures as the master sub data structure or one of the slave sub data structures, wherein the master sub data structure is the sub data structure upon which one or more operations directed to the data structure are referenced, and wherein the master sub data structure rotation cycle is a function of a given policy for retaining data in the data structure; wherein the at least one processor device is further configured to delete elements stored in the one of the two or more sub data structures recognized as the master sub data structure after recognition of the sub data structure as the master sub data structure.