Emoji frequency detection and deep link frequency

• US 9,894,089 B2
• Filed: 06/19/2017
• Issued: 02/13/2018
• 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, Freudinger, Julien, Prakash, Vipul Ved, Legendre, Arnaud, Duplinsky, Steven
• Primary Examiner(s): Schwartz, Darren B
• Application Number:
  US15/627,269
• Publication Number:
  US 20170359363A1
• Time in Patent Office: 239 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 computer-implemented method practiced on a set of one or more servers each comprising at least one hardware processor, the method comprising:

receiving a batch of differentially private term sketches comprising differentially private sketches of 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 known terms on the set of one or more servers, thereby generating a set differentially private sketches of known terms;

selecting a differentially private sketch from the batch;

querying, by the set of one or more servers, the set of differentially private sketches of known terms to find a match to the selected differentially sketch, the matching selected differentially private sketch, W, having dimensions of k rows and m columns, wherein each row∈

[k] corresponds to a hash function in a set of k hash functions, H; and

adding, by the set of one or more servers, the selected differentially private sketch data to the matching differentially private sketch.

2. The method of claim 1, further comprising:

determining the frequency of the term corresponding to the selected sketch.

3. The method of claim 2, further comprising:

updating an asset catalog having frequencies of known terms with the determined frequencies of known terms generated from the received batch of differentially private sketches, thereby generating an updated asset catalog; and

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

4. The method of claim 2, wherein determining the frequency of a known term comprises:

generating a vector, V, comprising k values, each value obtained from a different one of k rows in the matching differentially private sketch for the term;

determining a sketch count value, C, wherein C is one of;

a median of all values in vector V, or a minimum of all values in vector V; and

determining the frequency of the term by multiplying C by k.

5. The method of claim 1, wherein adding the selected differentially private sketch data to the matching differentially private sketch comprises:

selecting a differentially private sketch vector v_Hadamard from the selected differentially private sketch data, and a hash function h used to generate v_Hadamard, wherein h∈

H and an index j used to generate v_Hadamard;

adding vector v_Hadamard to the selected matching sketch W[h,j], wherein h is the row corresponding to the hash function used to generate v_Hadamard and j is an index used to generate v_Hadamard.

6. The method of claim 1, wherein adding the selected differentially private sketch data to the matching differentially private sketch comprises:

selecting a differentially private sketch vector v_priv from the selected differentially private sketch data and a hash function h used to generate v_priv, wherein h∈

H;

adding vector v_priv to the selected matching sketch W at row W_h corresponding to the hash function used to generate v_priv.

7. A non-transitory machine readable media storing executable instructions which when executed by a set of one or more servers cause a method practiced on the set of one or more servers each comprising at least one hardware processor, the method comprising:

receiving a batch of differentially private term sketches comprising differentially private sketches of 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 known terms on the set of one or more servers, thereby generating a set differentially private sketches of known terms;

selecting a differentially private sketch from the batch;

querying, by the set of one or more servers, the set of differentially private sketches of known terms to find a match to the selected differentially sketch, the matching selected differentially private sketch, W, having dimensions of k rows and m columns, wherein each row∈

[k] corresponds to a hash function in a set of k hash functions, H; and

adding, by the set of one or more servers, the selected differentially private sketch data to the matching differentially private sketch.

8. The media of claim 7, further comprising:

determining the frequency of the term corresponding to the selected sketch.

9. The media of claim 8, further comprising:

updating an asset catalog having frequencies of known terms with the determined frequencies of known terms generated from the received batch of differentially private sketches, thereby generating an updated asset catalog; and

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

10. The media of claim 8, wherein determining the frequency of a known term comprises:

generating a vector, V, comprising k values, each value obtained from a different one of k rows in the matching differentially private sketch for the term;

determining a sketch count value, C, wherein C is one of;

a median of all values in vector V, or a minimum of all values in vector V; and

determining the frequency of the term by multiplying C by k.

11. The media of claim 7, wherein adding the selected differentially private sketch data to the matching differentially private sketch comprises:

selecting a differentially private sketch vector v_Hadamard from the Selected differentially private sketch data, and a hash function h used to generate v_Hadamard, wherein h∈

H and an index j used to generate v_Hadamard;

adding vector v_Hadamard to the selected matching sketch W[h,j], wherein h is the row corresponding to the hash function used to generate v_Hadamard and j is an index used to generate v_Hadamard.

12. The media of claim 7, wherein adding the selected differentially private sketch data to the matching differentially private sketch comprises:

selecting a differentially private sketch vector v_priv from the selected differentially private sketch data and a hash function h used to generate v_priv, wherein h∈

H;

adding vector v_priv to the selected matching sketch W at row W_h corresponding to the hash function used to generate v_priv.