System and method for merging sketches via key obfuscation and applications thereof

1 . A method, comprising:

receiving performance metrics specified with respect to a merged sketch from a plurality of sketches from a plurality of data sketch sources, wherein the performance metrics include:

a first metric specifying an upper bound of false positive probability in identifying matching obfuscated keys from different data sketch sources,

a second metric specifying an upper bound of false negative probability in identifying matching obfuscated keys from different data sketch sources, and

a third metric specifying an upper bound of a probability of inferring an original key based on multiple obfuscated keys generated based on the original key;

generating sketch merging parameters in accordance with the performance metrics, wherein the sketch merging parameters include a first set relating to generating obfuscated keys for the plurality of sketches and a second set relating to identifying matching obfuscated keys;

receiving the plurality of sketches from the plurality of data sketch sources, wherein each of the plurality of sketches includes obfuscated keys generated based on the first set of sketch merging parameters; and

merging the sketches by identifying matching obfuscated keys in accordance with the second set of sketch merging parameters to generate a merged sketch.

2 . The method of claim 1 , wherein the first set of the sketch merging parameters include:

a number of bits used to generate keys of data in the plurality of sketches; and

a bit flipping probability for flipping each bit of a key when obfuscating a key.

3 . The method of claim 2 , wherein the second set of the sketch merging parameters includes a threshold to be used in determining whether two obfuscated keys correspond to the same original key.

4 . The method of claim 3 , wherein the step of generating the sketch merging parameters comprises:

determining the bit flipping probability based on the third metric;

determining the threshold based on the second metric and the bit flipping probability; and

determining the number of bits used to generate the codes based on the first metric and the threshold.

5 . The method of claim 1 , wherein the step of merging the sketches comprises:

identifying pairs of obfuscated keys, wherein each of the pairs includes two obfuscated keys from different data sketch sources;

obtaining a similarity measure between two obfuscated keys in each of the pairs;

determining whether the two obfuscated keys in each of the pairs match based on the similarity measure thereof and the second set of sketch merging parameters;

selecting matching pairs with the two obfuscated keys therein are determined to match; and

generating the merged sketch based on the matching pairs.

6 . The method of claim 1 , further comprising:

receiving a query for information associated with the sketches from the plurality of data sketch sources; and

identifying the information in response to the query based on the merged sketch.

7 . A machine-readable and non-transitory medium having information recorded thereon, wherein the information, when read by the machine, causes the machine to perform the following steps:

receiving performance metrics specified with respect to a merged sketch from a plurality of sketches from a plurality of data sketch sources, wherein the performance metrics include:

a first metric specifying an upper bound of false positive probability in identifying matching obfuscated keys from different data sketch sources,

a second metric specifying an upper bound of false negative probability in identifying matching obfuscated keys from different data sketch sources, and

a third metric specifying an upper bound of a probability of inferring an original key based on multiple obfuscated keys generated based on the original key;

generating sketch merging parameters in accordance with the performance metrics, wherein the sketch merging parameters include a first set relating to generating obfuscated keys for the plurality of sketches and a second set relating to identifying matching obfuscated keys;

receiving the plurality of sketches from the plurality of data sketch sources, wherein each of the plurality of sketches includes obfuscated keys generated based on the first set of sketch merging parameters; and

merging the sketches by identifying matching obfuscated keys in accordance with the second set of sketch merging parameters to generate a merged sketch.

8 . The medium of claim 7 , wherein the first set of the sketch merging parameters include:

a number of bits used to generate keys of data in the plurality of sketches; and

a bit flipping probability for flipping each bit of a key when obfuscating a key.

9 . The medium of claim 8 , wherein the second set of the sketch merging parameters includes a threshold to be used in determining whether two obfuscated keys correspond to the same original key.

10 . The medium of claim 9 , wherein the step of generating the sketch merging parameters comprises:

determining the bit flipping probability based on the third metric;

determining the threshold based on the second metric and the bit flipping probability; and

determining the number of bits used to generate the codes based on the first metric and the threshold.

11 . The medium of claim 7 , wherein the step of merging the sketches comprises:

identifying pairs of obfuscated keys, wherein each of the pairs includes two obfuscated keys from different data sketch sources;

obtaining a similarity measure between two obfuscated keys in each of the pairs;

determining whether the two obfuscated keys in each of the pairs match based on the similarity measure thereof and the second set of sketch merging parameters;

selecting matching pairs with the two obfuscated keys therein are determined to match; and

generating the merged sketch based on the matching pairs.

12 . The medium of claim 7 , wherein the information, when read by the machine, further causes the machine to perform the following steps:

receiving a query for information associated with the sketches from the plurality of data sketch sources; and

identifying the information in response to the query based on the merged sketch.

13 . A system, comprising:

memory storing computer program instructions; and

one or more processors that, in response to executing the computer program instructions, effectuate steps comprising:

receiving performance metrics specified with respect to a merged sketch from a plurality of sketches from a plurality of data sketch sources, wherein the performance metrics include:

a first metric specifying an upper bound of false positive probability in identifying matching obfuscated keys from different data sketch sources,

a second metric specifying an upper bound of false negative probability in identifying matching obfuscated keys from different data sketch sources, and

a third metric specifying an upper bound of a probability of inferring an original key based on multiple obfuscated keys generated based on the original key;

generating sketch merging parameters in accordance with the performance metrics, wherein the sketch merging parameters include a first set relating to generating obfuscated keys for the plurality of sketches and a second set relating to identifying matching obfuscated keys;

receiving the plurality of sketches from the plurality of data sketch sources, wherein each of the plurality of sketches includes obfuscated keys generated based on the first set of sketch merging parameters; and

merging the sketches by identifying matching obfuscated keys in accordance with the second set of sketch merging parameters to generate a merged sketch.

14 . The system of claim 13 , wherein

the first set of the sketch merging parameters include:

a number of bits used to generate keys of data in the plurality of sketches, and

a bit flipping probability for flipping each bit of a key when obfuscating a key; and

the second set of the sketch merging parameters includes a threshold to be used in determining whether two obfuscated keys correspond to the same original key.

15 . The system of claim 14 , wherein the step of generating the sketch merging parameters comprises:

determining the bit flipping probability based on the third metric;

determining the threshold based on the second metric and the bit flipping probability; and

determining the number of bits used to generate the codes based on the first metric and the threshold.

16 . The system of claim 13 , wherein the step of merging the sketches comprises:

identifying pairs of obfuscated keys, wherein each of the pairs includes two obfuscated keys from different data sketch sources;

obtaining a similarity measure between two obfuscated keys in each of the pairs;

determining whether the two obfuscated keys in each of the pairs match based on the similarity measure thereof and the second set of sketch merging parameters;

selecting matching pairs with the two obfuscated keys therein are determined to match; and

generating the merged sketch based on the matching pairs.

17 . The system of claim 13 , wherein the steps further comprise:

receiving a query for information associated with the sketches from the plurality of data sketch sources; and

identifying the information in response to the query based on the merged sketch.