Distributable hash filter for nonprobabilistic set inclusion
In certain embodiments, a method includes recursively performing a procedure that includes using an allowed set of object identifiers and a hash function to update a bit array, using a disallowed set of object identifiers and the hash function to further update the bit array where collisions occur, repeating the process with a new allowed set that includes object identifiers from the original allowed set that collided with the disallowed set and a new hash function, until reaching a round where no collisions occurred, generating a data structure that includes the bit arrays created during each recursive round, and compressing the data structure.
1 . A device, comprising:
one or more processors; and
one or more non-transitory computer readable media storing instructions which,
when executed by the one or more processors, cause the one or more processors to:
obtain an allowed set comprising a first plurality of identifiers corresponding to a plurality of objects;
obtain, according to the allowed set and a total set of identifiers, a disallowed set comprising a second plurality of identifiers;
generate an initial bit array comprising a first value at each position of a plurality of positions in the initial bit array;
obtain a first set of index values corresponding to a subset of positions of the plurality of positions using the first plurality of identifiers and a first hash function;
set each of the subset of positions in the initial bit array to a second value to obtain an updated bit array;
perform a first collision check using the first hash function, the disallowed set, and the updated bit array to obtain a sparse bit array; and
generate, when the first collision check results in no collisions, a data structure comprising the sparse bit array.
2 . The device of claim 1 , wherein the instructions, when executed by the one or more processors, further cause the one or more processors to, when the first collision check results in one or more collisions:
obtain a new allowed set comprising a subset of the identifiers of the allowed set based on the first collision check;
obtain a new set of index values using the new allowed set and a different hash function;
set, using the new set of index values, a new subset of positions of a new initial bit array to the second value;
perform a second collision check using the disallowed set, the different hash function, and the new initial bit array to obtain a second sparse bit array; and
generate, when the second collision check results in no collisions, the data structure comprising the sparse bit array and the second sparse bit array.
3 . The device of claim 2 , wherein the instructions, when executed by the one or more processors, further cause the one or more processors to:
perform a plurality of rounds of sparse bit array generation after performing the first collision check and before performing the second collision check.
4 . The device of claim 1 , wherein the instructions, when executed by the one or more processors, further cause the one or more processors to:
compress the data structure to obtain a compressed data structure.
5 . The device of claim 4 , wherein the compressed data structure is distributed for testing membership in the allowed set in response to a request that includes an identifier of an object.
6 . The device of claim 5 , wherein the compressed data structure is distributed to a user for inclusion in the request.
7 . The device of claim 4 , wherein the compressed data structure is compressed using a lossless compression technique.
8 . The device of claim 1 , wherein each identifier in the first plurality of identifiers and the second plurality of identifiers are separate device identifiers corresponding to a plurality of devices of a device ecosystem.
9 . The device of claim 1 , wherein the instructions, when executed by the one or more processors, further cause the one or more processors to:
select the first hash function based at least in part on the first hash function being configured to output values corresponding to index positions of the initial bit array.
10 . A computer-implemented method, comprising:
obtaining an allowed set comprising a first plurality of identifiers corresponding to a plurality of objects;
obtaining, according to the allowed set and a total set of identifiers, a disallowed set comprising a second plurality of identifiers;
generating an initial bit array comprising a first value at each position of a plurality of positions in the initial bit array;
obtaining a first set of index values corresponding to a subset of positions of the plurality of positions using the first plurality of identifiers and a first hash function;
setting each of the subset of positions in the initial bit array to a second value to obtain an updated bit array;
performing a first collision check using the first hash function, the disallowed set, and the updated bit array to obtain a sparse bit array; and
generating, when the first collision check results in no collisions, a data structure comprising the sparse bit array.
11 . The computer-implemented method of claim 10 , further comprising, when the first collision check results in one or more collisions:
obtaining a new allowed set comprising a subset of the identifiers of the allowed set based on the first collision check;
obtaining a new set of index values using the new allowed set and a different hash function;
setting, using the new set of index values, a new subset of positions of a new initial bit array to the second value;
performing a second collision check using the disallowed set, the different hash function, and the new initial bit array to obtain a second sparse bit array; and
generating, when the second collision check results in no collisions, the data structure comprising the sparse bit array and the second sparse bit array.
12 . The computer-implemented method of claim 11 , further comprising:
performing a plurality of rounds of sparse bit array generation after performing the first collision check and before performing the second collision check.
13 . The computer-implemented method of claim 10 , further comprising:
compressing the data structure to obtain a compressed data structure.
14 . The computer-implemented method of claim 13 , wherein the compressed data structure is distributed for testing membership in the allowed set in response to a request that includes an identifier of an object.
15 . The computer-implemented method of claim 14 , wherein the compressed data structure is distributed to a user for inclusion in the request.
16 . The computer-implemented method of claim 13 , wherein the compressed data structure is compressed using a lossless compression technique.
17 . The computer-implemented method of claim 10 , wherein each identifier in the first plurality of identifiers and the second plurality of identifiers are separate device identifiers corresponding to a plurality of devices of a device ecosystem.
18 . The computer-implemented method of claim 10 , further comprising:
selecting the first hash function based at least in part on the first hash function being configured to output values corresponding to index positions of the initial bit array.
19 . A non-transitory computer-readable medium storing programming for execution by one or more processors, the programming comprising instructions to:
obtain an allowed set comprising a first plurality of identifiers corresponding to a plurality of objects;
obtain, according to the allowed set and a total set of identifiers, a disallowed set comprising a second plurality of identifiers;
generate an initial bit array comprising a first value at each position of a plurality of positions in the initial bit array;
obtain a first set of index values corresponding to a subset of positions of the plurality of positions using the first plurality of identifiers and a first hash function;
set each of the subset of positions in the initial bit array to a second value to obtain an updated bit array;
perform a first collision check using the first hash function, the disallowed set, and the updated bit array to obtain a sparse bit array; and
generate, when the first collision check results in no collisions, a data structure comprising the sparse bit array.
20 . The non-transitory computer-readable medium of claim 19 , wherein the programming comprises further instructions to, when the first collision check results in one or more collisions:
obtain a new allowed set comprising a subset of the identifiers of the allowed set based on the first collision check;
obtain a new set of index values using the new allowed set and a different hash function;
set, using the new set of index values, a new subset of positions of a new initial bit array to the second value;
perform a second collision check using the disallowed set, the different hash function, and the new initial bit array to obtain a second sparse bit array; and
generate, when the second collision check results in no collisions, the data structure comprising the sparse bit array and the second sparse bit array.