Homework answers / question archive / In class we learned that the basic Bloom ?lter design doesn't support deletions

In class we learned that the basic Bloom ?lter design doesn't support deletions

Computer Science

Share With

In class we learned that the basic Bloom ?lter design doesn't support deletions. But a friend of yours came up with an {ingenious?) idea for supporting deletes: what if Iyour database maintains two Bloom ?lters: a normal one (that tracks inserted objects] and another special one, "deiete Bloom ?lter" that tracks deletes. The delete Bloom ?lter works exactly the same as a normal Bloom ?lter. except that it marks the Bioom ?lter's array with 1's only for delete operations [and not for insert operations). E.g.. deiete("cat"} would mark '1' in the array entries that are the outputs of the hash functions applied to "cat". Then. before the database looks up an item from disk, it ?rst checks both the normal and delete Bioom ?lters. If the corresponding entries for that item in the delete Bloom ?lter are all '1'5. the database can return: "object delet ". and it is assumed not to be stored in the database, removing the need to took it up from disk. Would this idea work? Piease explain.