Hybrid encoding for local differential privacy

1 . A method comprising:

obtaining dataset for transmission;

dividing the dataset into two subsets according to one or more selection criteria, wherein data items that satisfy the one or more selection criteria are added to a first subset and the data items that do not satisfy the one or more selection criteria are added to a second subset, wherein the first subset is smaller than the second subset;

encoding the data items of the first subset according to a first encoding technique and encoding the data items of the second subset according to a second encoding technique, wherein the first encoding technique is unary encoding and the second encoding technique is hash-based encoding;

applying a local differential privacy (LDP) mechanism to data elements of the first subset and the second subset to generate an LDP message; and

transmitting the LDP message to an external recipient.

2 . The method of claim 1 , wherein the data items are encoded in a vector having a first portion used to encode values of data items in the first subset and a second portion used to encode hashed data item values from the second subset.

3 . The method of claim 1 , wherein a hash-based encoding domain is less than a domain of values of the data items in the second subset.

4 . The method of claim 1 , wherein a same LDP mechanism is applied to the first encoding technique and the second encoding technique.

5 . The method of claim 1 , wherein the LDP mechanism flips one or more bits of an encoding vector to add noise to the LDP message sent to the external recipient.

6 . The method of claim 1 , wherein the dataset is divided according to top n values of data items according to the one or more selection criteria.

7 . A system comprising:

one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

obtaining dataset for transmission;

dividing the dataset into two subsets according to one or more selection criteria, wherein data items that satisfy the one or more selection criteria are added to a first subset and the data items that do not satisfy the one or more selection criteria are added to a second subset, wherein the first subset is smaller than the second subset;

encoding the data items of the first subset according to a first encoding technique and encoding the data items of the second subset according to a second encoding technique, wherein the first encoding technique is unary encoding and the second encoding technique is hash-based encoding;

applying a local differential privacy (LDP) mechanism to data elements of the first subset and the second subset to generate an LDP message; and

transmitting the LDP message to an external recipient.

8 . The system of claim 7 , wherein the data items are encoded in a vector having a first portion used to encode values of data items in the first subset and a second portion used to encode hashed data item values from the second subset.

9 . The system of claim 8 , wherein a hash-based encoding domain is less than a domain of values of the data items in the second subset.

10 . The system of claim 7 , wherein a same LDP mechanism is applied to the first encoding technique and the second encoding technique.

11 . The system of claim 7 , wherein the LDP mechanism flips one or more bits of an encoding vector to add noise to the LDP message sent to the external recipient.

12 . The system of claim 7 , wherein the dataset is divided according to top n values of data items according to the one or more selection criteria.

13 . One or more non-transitory computer storage media encoded with computer program instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

obtaining dataset for transmission;

dividing the dataset into two subsets according to one or more selection criteria, wherein data items that satisfy the one or more selection criteria are added to a first subset and the data items that do not satisfy the one or more selection criteria are added to a second subset, wherein the first subset is smaller than the second subset;

encoding the data items of the first subset according to a first encoding technique and encoding the data items of the second subset according to a second encoding technique, wherein the first encoding technique is unary encoding and the second encoding technique is hash-based encoding;

applying a local differential privacy (LDP) mechanism to data elements of the first subset and the second subset to generate an LDP message; and

transmitting the LDP message to an external recipient.

14 . The one or more non-transitory computer storage media of claim 13 , wherein the data items are encoded in a vector having a first portion used to encode values of data items in the first subset and a second portion used to encode hashed data item values from the second subset.

15 . The one or more non-transitory computer storage media of claim 13 , wherein a hash-based encoding domain is less than a domain of values of the data items in the second subset.

16 . The one or more non-transitory computer storage media of claim 13 , wherein a same LDP mechanism is applied to the first encoding technique and the second encoding technique.

17 . The one or more non-transitory computer storage media of claim 13 , wherein the dataset is divided according to top n values of data items according to the one or more selection criteria.