DIFFERENTIAL PRIVACY USING A COUNT MEAN SKETCH

• US 20180349636A1
• Filed: 11/07/2017
• Published: 12/06/2018
• Est. Priority Date: 06/04/2017
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bhowmick, Abhishek, Vyrros, Andrew H., Vaishampayan, Umesh S.
• Granted Patent: US 10,599,867 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 1/28 Supervision thereof, e.g. detecting power-supply failure by out of limits supervision
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/0483 Interaction with page-structured environments, e.g. book metaphor
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]

Abstract

Embodiments described herein provide a privacy mechanism to protect user data when transmitting the data to a server that estimates a frequency of such data amongst a set of client devices. In one embodiment, a differential privacy mechanism is implemented using a count-mean-sketch technique that can reduce resource requirements required to enable privacy while providing provable guarantees regarding privacy and utility. For instance, the mechanism can provide the ability to tailor utility (e.g. accuracy of estimations) against the resource requirements (e.g. transmission bandwidth and computation complexity).

Claims

1. An electronic device comprising:

a non-transitory machine-readable medium to store instructions;

one or more processors to execute the instructions; and

a memory coupled to the one or more processors, the memory to store the instructions which, when executed by the one or more processors, cause the one or more processors to;

detect an interaction in relation to an application, the interaction performed in response to instructions within a webpage presented by the application, wherein the webpage presented by the application is to cause presentation of a media item;

associate the webpage presented by the application to a category based on the interaction, the category selected from a set of categories related to an inferred preference for presentation of the webpage by the application;

create a privatized encoding including a representation of the webpage presented by application and a representation of the category; and

transmit the privatized encoding to at least one server, the server to accumulate a privatized encoding from multiple devices to estimate a frequency of the webpage presented by the application being associated with the category amongst the multiple devices.

2. The electronic device as in claim 1, wherein the response is provided in response to initiation, attempted initiation, or allowance of auto-play of a media item presented by the webpage or a web application associated with the webpage and the set of categories includes a first category related to an inferred preference to enable auto-play of the media item.

3. The electronic device as in claim 2, wherein the response includes to allow auto-play of the media item to exceed a predetermined time value after the webpage presents the media item or to enlarge or maximize the media item after auto-play is initiated for the media item.

4. The electronic device as in claim 2, wherein auto-play is disabled for the webpage visited by a user based on a setting and the response includes to select to play the media item for which the webpage attempted to initiate auto-play within a predetermined time value of presentation of the media item.

5. The electronic device as in claim 1, wherein the response is provided in response to initiation, attempted initiation, or allowance of auto-play of a media item within the webpage or a web application associated with the webpage, and the set of categories include a second category related to inferring a user preference of disabling auto-play of media content.

6. The electronic device as in claim 5, wherein the response includes to close or minimize the application or a tab associated with the webpage.

7. The electronic device as in claim 5, wherein the response includes to mute or lower a system volume.

8. The electronic device as in claim 5, wherein auto-play is disabled for the webpage based on a setting and the response includes to navigate away from the media item without playback of the media item.

9. The electronic device as in claim 5, wherein the response includes to interrupt an auto-play of the media item within a predetermined time value of the webpage presenting the media item, and wherein to interrupt the auto-play includes to pause, stop, or mute the media item, or to lower a volume of the media item to a predetermined level.

10. The electronic device as in claim 1, the instructions further to cause the one or more processors to:

determine that content on a webpage to be displayed by the application includes logic that indicates that media content set for auto-play; and

adjust one or more presentation settings for the media content prior to presentation of the media content by the application.

11. The electronic device as in claim 10, wherein to adjust the one or more presentation settings includes to disable auto-play, delay the auto-play, pause the auto-play, or mute the media content.

12. The electronic device of claim 1, wherein to create the privatized encoding, the instructions are to cause the one or more processors to:

create a hash value of the representation of the webpage and the representation of the category via a randomly selected hash function,

encode an initialized vector via a sign flip of a value of the initialized vector at a position corresponding to the hash value, and

change at least some of the values of the initialized vector with a predefined probability determined based on a privacy parameter.

13. A computing system, comprising:

one or more processors; and

a memory coupled to the one or more processors, the memory storing instructions, which when executed by the one or more processors, cause the computing system to perform operations comprising;

receiving, from each of a set of client devices, a privatized encoding of a webpage and a category associated with the webpage, wherein the category relates to inferring a preference for presentation of media content on the webpage;

accumulating privatized encodings from the set of client devices; and

estimating a frequency of a selected webpage being associated with the category based on the accumulated privatized encodings from the set of client devices.

14. The computing system as in claim 13, additionally comprising:

accumulating a sketch of the privatized encodings received from the set of client devices, the sketch including frequency estimations of the privatized encodings; and

estimating a frequency of the selected webpage being associated with the category amongst the frequencies included in the sketch of the privatized encodings.

15. The computing system of claim 13, wherein estimating the frequency of the selected webpage includes determining a count using a count-mean-sketch operation.

16. The computing system as in claim 13, wherein the category relates to inferring preference with respect to use of a reader mode for display of content on the webpage wherein the reader mode is a mode in which menu items are not displayed.

17. The computing system as in claim 13, wherein the category relates to inferring a preference a preference for content blocking settings for the webpage.

18. The computing system as in claim 13, wherein the category relates to inferring a user preference of enabling auto-play of media content on the webpage.

19. The computing system of claim 18, the operations additionally comprising adding the selected webpage to a whitelist based on an estimated frequency of users providing an inference of a preference to enable auto-play for the webpage, wherein the whitelist includes a list of webpages for which automatic playback is allowed.

20. The computing system of claim 19, the operations additionally comprising removing the selected webpage from the whitelist or adding the selected webpage to a blacklist based on the estimated frequency of users providing an inference of a preference to disable auto-play for the webpage, wherein the whitelist includes a list of webpages for which auto-play is allowed, and the whitelist includes a list of webpages for which auto-play is disabled.

21. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

receiving, from each of a set of client devices, a privatized encoding of a webpage and a category associated with the webpage, wherein the category relates to inferring a user preference of enabling auto-play of media content on the webpage;

accumulating privatized encodings from the set of client devices; and

estimating a frequency of a selected webpage being associated with the category based on the accumulated privatized encodings from the set of client devices.

22. The non-transitory machine-readable medium as in claim 21, the operations additionally comprising:

accumulating a sketch of the privatized encodings received from the set of client devices, the sketch including frequency estimations of the privatized encodings; and

estimating a frequency of the selected webpage being associated with the category amongst the frequencies included in the sketch of the privatized encodings.

23. The non-transitory machine-readable medium as in claim 21, the operations additionally comprising adding the selected webpage to a whitelist based on an estimated frequency of users providing an inference of a preference to enable auto-play for the webpage, wherein the whitelist includes a list of webpages for which automatic playback is allowed.

24. The non-transitory machine-readable medium as in claim 23, the operations additionally comprising removing the selected webpage from the whitelist or adding the selected webpage to a blacklist based on the estimated frequency of users providing an inference of a preference to disable auto-play for the webpage, wherein the whitelist includes a list of webpages for which auto-play is allowed, and the whitelist includes a list of webpages for which auto-play is disabled.

25. The non-transitory machine-readable medium as in claim 24, wherein estimating the frequency of the selected webpage includes determining a count using a count-mean-sketch operation.

26. A data processing system comprising:

a non-transitory machine-readable medium to store instructions;

one or more processors to execute the instructions; and

a memory coupled to the one or more processors, the memory to store the instructions which, when executed by the one or more processors, cause the one or more processors to;

detect an interaction with the data processing system in relation to a content item of presented content, the interaction determined to be in response to execution of instructions to present the content item;

associate the presented content with a category based on the interaction, the category selected from a set of categories related to an inferred preference for presentation of the presented content;

create a privatized encoding including a representation of the presented content and a representation of the category; and

transmit the privatized encoding to at least one server, the server to accumulate a privatized encoding from multiple devices to estimate a frequency of the presented content being associated with the category amongst the multiple devices.

27. The data processing system as in claim 26, wherein the presented content includes a webpage, a web application, or a user interface of an application, and the content item includes a user interface element of the webpage, a user interface element of the web application, or a user interface element of the application.

28. The data processing system as in claim 26, wherein the content item is presented by an application and the category is a setting selection provided by the application.

29. The data processing system as in claim 28, wherein the application is web browser or another application to view presented content.