Advanced Micro Devices, Inc.
SYSTEM AND METHOD FOR SELF-RESIZING ASSOCIATIVE PROBABILISTIC HASH-BASED DATA STRUCTURES

Abstract:

A method of maintaining a probabilistic filter includes, in response to receiving a key K.sub.1 for adding to the probabilistic filter, generating a fingerprint F.sub.1 based on applying a fingerprint hash function H.sub.F to the key K.sub.1, identifying an initial bucket B.sub.i1 by selecting between at least a first bucket B.sub.1 determined based on a first bucket hash function H.sub.1 of the key K.sub.1 and a second bucket B.sub.2 determined based on a second bucket hash function H.sub.2 of the key K.sub.1, and inserting the fingerprint F.sub.1 into the initial bucket B.sub.i1; and resizing the probabilistic filter. Resizing the probabilistic filter includes incrementing a resize counter value, determining a bucket B' for the fingerprint F.sub.1 based on a value of the fingerprint F.sub.1 and the resize counter value, and inserting the fingerprint F.sub.1 into the bucket B' in the probabilistic filter.