EMOJI FREQUENCY DETECTION AND DEEP LINK FREQUENCY

• US 20190068628A1
• Filed: 10/12/2018
• Published: 02/28/2019
• Est. Priority Date: 06/12/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Thakurta, Abhradeep Guha, Vyrros, Andrew H., Vaishampayan, Umesh S., Kapoor, Gaurav, Freudiger, Julien, Prakash, Vipul Ved, Legendre, Arnaud, Duplinsky, Steven
• Granted Patent: US 10,454,962 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 40/134 Hyperlinking
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: H04L 63/0421 Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

Systems and methods are disclosed for generating term frequencies of known terms based on crowdsourced differentially private sketches of the known terms. An asset catalog can be updated with new frequency counts for known terms based on the crowdsourced differentially private sketches. Known terms can have a classification. A client device can maintain a privacy budget for each classification of known terms. Classifications can include emojis, deep links, locations, finance terms, and health terms, etc. A privacy budget ensures that a client does not transmit too much information to a term frequency server, thereby compromising the privacy of the client device.

Claims

1. A data processing system on a set of one or more servers, the data processing system comprising:

a non-transitory machine-readable media storing instructions;

one or more processors to execute the instructions, wherein the instructions, when executed, cause the one or more processors to;

receive a batch of differentially private sketches comprising terms known to the set of one or more servers, the differentially private sketches received from a plurality of client devices;

generate or retrieve a differentially private sketch of each of a set of terms known to the set of one or more servers to generate a set of differentially private sketches of known terms;

select a differentially private sketch from the batch of differentially private sketches;

query the set of differentially private sketches of known terms to find a match to the selected differentially private sketch; and

add data from the selected differentially private sketch to a matching differentially private sketch of known terms.

2. The data processing system of claim 1, the one or more processors further to determine a frequency of the term corresponding to a differentially private sketch.

3. The data processing system of claim 2, wherein to determine the frequency of a known term, the one or more processors are to:

generate a vector including multiple values obtained from different rows in the matching differentially private sketch for the term;

determine a sketch count value that is a median of the multiple values in the vector or a minimum of the multiple values in vector; and

determine the frequency of the term, wherein the frequency of the term is a product of the sketch count value and a count of different rows in the matching differentially private sketch for the known term.

4. The data processing system of claim 3, wherein the count of different rows in the matching differentially private sketch for the term corresponds with a count of the multiple values obtained from the different rows.

5. The data processing system of claim 3, the one or more processors further to update an asset catalog having frequencies of known terms with the determined frequencies of known terms generated from a received batch of rows of differentially private sketches to generate an updated asset catalog.

6. The data processing system of claim 5, the one or more processors further to transmit the updated asset catalog to at least one client device.

7. The data processing system as in claim 1, wherein to add the data from the selected differentially private sketch to the matching differentially private sketch of known terms, the one or more processors are to:

select a differentially private sketch vector from the selected differentially private sketch;

select a hash function used to generate the differentially private sketch vector;

select an index used to generate the differentially private sketch vector; and

add the vector to the matching differentially private sketch of known terms at a location in the differentially private sketch that corresponds with the hash function and the index.

8. The data processing system as in claim 1, wherein the matching differentially private sketch of known terms includes multiple rows and columns and each row corresponds to a hash function in a set of hash functions.

9. The data processing system as in claim 1, wherein the terms known to the one or more servers include an emoji, a deep link, a location, a finance term, or health term.

10. One or more non-transitory machine-readable media storing executable instructions which when executed by a set of one or more servers cause one or more processors of the set of one or more servers to perform operations comprising:

receiving a batch of differentially private sketches comprising terms known to the set of one or more servers, the differentially private sketches received from a plurality of client devices;

generating or retrieving a differentially private sketch of each of a set of terms known to the set of one or more servers to generate a set of differentially private sketches of known terms;

selecting a differentially private sketch from the batch of differentially private sketches;

querying the set of differentially private sketches of known terms to find a match to the selected differentially private sketch; and

adding data from the selected differentially private sketch to a matching differentially private sketch of known terms.

11. The non-transitory machine-readable media of claim 10, the operations further comprising determining a frequency of the term corresponding to a differentially private sketch.

12. The non-transitory machine-readable media of claim 11, wherein determining the frequency of a known term includes operations comprising:

generating a vector including multiple values obtained from different rows in the matching differentially private sketch for the term;

determining a sketch count value that is a median of the multiple values in the vector or a minimum of the multiple values in vector; and

determining the frequency of the term, wherein the frequency of the term is a product of the sketch count value and a count of different rows in the matching differentially private sketch for the known term.

13. The non-transitory machine-readable media of claim 12, wherein the count of different rows in the matching differentially private sketch for the term corresponds with a count of the multiple values obtained from the different rows.

14. The non-transitory machine-readable media of claim 12, the operations additionally comprising:

updating an asset catalog having frequencies of known terms with the determined frequencies of known terms generated from a received batch of rows of differentially private sketches to generate an updated asset catalog; and

transmitting the updated asset catalog to at least one client device.

15. The non-transitory machine-readable media as in claim 10, wherein adding the data from the selected differentially private sketch to the matching differentially private sketch of known terms includes operations comprising:

selecting a differentially private sketch vector from the selected differentially private sketch;

selecting a hash function used to generate the differentially private sketch vector;

selecting an index used to generate the differentially private sketch vector; and

adding the vector to the matching differentially private sketch of known terms at a location in the differentially private sketch that corresponds with the hash function and the index.

16. The non-transitory machine-readable media as in claim 10, wherein the matching differentially private sketch of known terms includes multiple rows and columns and each row corresponds to a hash function in a set of hash functions.

17. The non-transitory machine-readable media as in claim 10, wherein the terms known to the one or more servers include an emoji, a deep link, a location, a finance term, or health term.

18. A method implemented on a set of one or more servers, the method comprising:

receiving a batch of differentially private sketches comprising terms known to the set of one or more servers, the differentially private sketches received from a plurality of client devices;

generating or retrieving a differentially private sketch of each of a set of terms known to the set of one or more servers to generate a set of differentially private sketches of known terms;

selecting a differentially private sketch from the batch of differentially private sketches;

querying the set of differentially private sketches of known terms to find a match to the selected differentially private sketch; and

adding data from the selected differentially private sketch to a matching differentially private sketch of known terms.

19. The method as in claim 18, additionally comprising:

generating a vector including multiple values obtained from different rows in the matching differentially private sketch for a term;

determining a sketch count value that is a median of the multiple values in the vector or a minimum of the multiple values in vector; and

determining a frequency of the term, wherein the frequency of the term is a product of the sketch count value and a count of different rows in the matching differentially private sketch for the term, and the count of different rows in the matching differentially private sketch for the term corresponds with a count of the multiple values obtained from the different rows.

20. The method as in claim 18, additionally comprising:

adding the data from the selected differentially private sketch to the matching differentially private sketch of known terms by selecting a differentially private sketch vector from the selected differentially private sketch, selecting a hash function used to generate the differentially private sketch vector, selecting an index used to generate the differentially private sketch vector, and adding the vector to the matching differentially private sketch of known terms at a location in the differentially private sketch that corresponds with the hash function and the index; and

wherein the terms known to the one or more servers include an emoji, a deep link, a location, a finance term, or health term.