Duplicate account identification and scoring

• US 7,725,421 B1
• Filed: 07/26/2006
• Issued: 05/25/2010
• Est. Priority Date: 07/26/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wong, Julian, Gedalius, Joel, Sinay, Brian, Verma, Naval
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Hocker; John P
• Application Number:
  US11/460,061
• Time in Patent Office: 1,399 Days
• Field of Search: 707 1- 10
• US Class Current: 707/702
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: G06Q 40/02 Banking, e.g. interest calculation or account maintenance credit or loans G06Q40/03

Abstract

A system matches accounts based on attributes of the accounts, and scores the matched account pairs based on a probability of the matched accounts being duplicate accounts. The system can utilize the matched and scored account pairs to determine duplicate accounts, and terminate at least one of the accounts in a duplicate account pair.

Claims

1. A method performed by a computer system, the method comprising:

receiving, using a communication interface associated with the computer system, a trigger event for a first user account;

receiving, using a communication interface associated with the computer system, a string related to the first account;

converting, using one or more processors associated with the computer system, the string into a histogram of characters of the string;

converting, using one or more processors associated with the computer system, the histogram of characters into a histogram of bins using a character to bin mapping;

appending, using one or more processors associated with the computer system, a length of the string as a last bin of the histogram of bins;

calculating, using one or more processors associated with the computer system, a particular number of nearest neighbors for the histogram of bins in a kd-tree;

calculating, using one or more processors associated with the computer system, a string edit distance between the histogram of bins and a particular neighbor of the calculated nearest neighbors;

if the string edit distance is greater than a preset threshold for the particular neighbor, designating a match between the first user account and a second user account that is associated with the particular neighbor, to create a matched user account pair, where the designating is performed using one or more processors associated with the computer system; and

scoring, using one or more processors associated with the computer system, the matched user account pair.

2. The method of claim 1, further comprising:

searching for the trigger event.

3. The method of claim 1, further comprising:

storing the matched user account pair.

4. The method of claim 1, where the scoring comprises:

creating a graph that includes the first and second user accounts on one side, and values for account attributes on another side;

locating an edge from one of the first and second user accounts to one account attribute value; and

applying a weight to the edge.

5. The method of claim 1, where the scoring comprises:

scoring the matched user account pair according to the following equation;

Score(A1,A2)=½

*[p(A2|A1)+p(A1|A2)],

where A1 is the first user account, A2 is the second user account, p(A2|A1) is the probability of reaching node A2 in a unidirected bi-partite graph if one started at node A1 and were allowed to traverse a path of size two, and p(A1|A2) is the probability of reaching node A1 in the unidirected bi-partite graph if one started at node A2 and were allowed to traverse a path of size two.

6. The method of claim 1, where the score for the matched user account pair represents a probability of the first and second user accounts being owned by the same user.

7. The method of claim 1, where the scoring comprises:

scoring the matched user account pair based on a single account attribute at a time; and

combining the scores from different account attributes to generate a single score for the matched user account pair.

29. The method of claim 1, further comprising:

utilizing the scored matched account pairs to determine duplicate accounts; and

terminating at least one of the accounts in a duplicate account pair.

30. The method of claim 1, where the trigger event comprises at least one of a user logging into the first user account or the first user account being recently created.

8. A computer system comprising:

one or more server devices comprising;

a backend matching unit that;

receives a string related to a first account,

converts the string into a histogram of characters of the string,

converts the histogram of characters into a histogram of bins using a character to bin mapping,

appends a length of the string as a last bin to the histogram of bins,

calculates a string edit distance between the histogram of bins and a neighbor in a kd-tree,

if the string edit distance is greater than a threshold, designates a matched account pair of the first account and a second account associated with the neighbor, and

assigns scores to the matched account pair; and

a prioritization reviewing unit that receives matched account pairs and the scores of the pairs, and prioritizes the matched account pairs based on the scores.

9. The system of claim 8, further comprising:

a frontend reviewing unit that reviews the matched account pairs, and determines if the matched account pairs are potential duplicate accounts.

10. The system of claim 8, where the backend matching unit searches for trigger events and performs account matching and scoring on accounts corresponding to the triggered events.

11. The system of claim 8, where the backend matching unit:

creates a graph that includes accounts on one side, and values for account attributes on another side,

locates an edge from the accounts to the account attribute values, and

applies a weight to the edge.

12. The system of claim 8, where the backend matching unit:

scores a matched account pair according to the following equation;

Score(A1,A2)=½

*[p(A2|A1)+p(A1|A2)],

where A1 is a first account, A2 is the a second account, p(A2|A1) is the probability of reaching node A2 in a unidirected bi-partite graph if one started at node A1 and were allowed to traverse a path of size two, and p(A1|A2) is the probability of reaching node A1 in the unidirected bi-partite graph if one started at node A2 and were allowed to traverse a path of size two.

13. The system of claim 12, where the score for the matched account pair represents a probability of the first and second accounts being associated with the same user.

14. The system of claim 8, where the backend matching unit:

scores each matched account pair based on a single account attribute at a time; and

combines the scores from different account attributes to generate a single score for the matched account pair.

15. The system of claim 8, where the prioritization reviewing unit reviews terminated accounts.

16. The system of claim 15, where the prioritization reviewing unit matches open accounts to the terminated accounts for matches that may be greater than a preset score threshold.

17. The system of claim 16, where the prioritization reviewing unit prioritizes the matched accounts greater than the preset score threshold based on the scores of the matched accounts.

18. The system of claim 17, where the prioritization reviewing unit filters recently reviewed matched accounts or matched accounts already in storage.

19. The system of claim 9, where the frontend reviewing unit provides an interface for confirmation of matched accounts.

20. The system of claim 19, where the frontend reviewing unit receives account scores and attributes, and displayable information.

21. The system of claim 20, where the interface of the frontend reviewing unit provides a table that includes rows corresponding to each account and columns corresponding to account attributes.

22. The system of claim 21, where the table further includes a column that indicates matches between two accounts based on one or more account attributes.

23. The system of claim 22, where the frontend reviewing unit enables identification of two accounts that are determined to be the same user by selecting the two rows corresponding to the identified accounts.

24. The system of claim 22, where the frontend reviewing automatically identifies accounts having matches equal to or above a preset threshold.

25. The system of claim 9, where the frontend reviewing unit terminates one of two accounts determined to be duplicates based on matches equal to or exceeding a preset threshold.

26. The system of claim 9, where the frontend reviewing unit terminates two accounts determined to be duplicates.

27. A system comprising:

one or more devices comprising;

a memory to store accounts;

means for receiving trigger events for the accounts;

means for mapping characters to bins;

means for converting a string associated with one of the accounts into a histogram of bins based on the mapping;

means for appending a length of the string to the histogram of bins as an additional bin of the histogram of bins;

means for determining a string edit distance between the histogram of bins and a neighbor in a kd-tree;

means for matching the one of the accounts to another one of the accounts based on the string edit distance being greater than a threshold where the other one of the accounts is associated with the neighbor in the kd-tree;

means for scoring the matched accounts; and

means for utilizing the matched and scored account pair to determine a duplicate account.

31. The system of claim 27, where the attributes include user name, user address, login information, personal information, payment information, industry information, or account information.

32. The system of claim 27, where the scores represent probabilities of accounts being owned by the same user.

33. The system of claim 27, where the trigger events comprise at least one of a user logging into an account or an account being created.

34. The system of claim 27, further comprising:

means for terminating a determined duplicate account.

28. A system comprising:

a memory to store a plurality of instructions; and

a processor to execute instructions in the memory to;

match accounts based on attributes of the accounts,

retrieve strings associated with the attributes,

convert strings into histograms of characters,

convert the histograms of characters into histograms of bins based on a character-to-bin mapping,

append a histogram of bins with an extra bin representing a length of the string associated with the histogram,

calculate a string edit distance between the histogram of bins and a neighbor in a kd-tree, where the string is associated with an attribute of a first account and where the neighbor is associated with a corresponding attribute of a second account,

score the first account and the second account based on the string edit distance,

utilize the scored account pair to determine whether the first account pair and the second account pair comprise duplicate accounts, and

terminate at least one of the first account or the second account.

35. The system of claim 28, where the character-to-bin mapping is based on Huffman coding.

36. The system of claim 28, where the processor further executes instructions in the memory to:

indicate, for the scored account pair, which particular attributes of the first account and the second account match.

37. One or more memory devices storing instructions executable by one or more processors, the one or more memory devices comprising:

one or more instructions to receive a trigger event for a first user account;

one or more instructions to receive a string related to the first account;

one or more instructions to convert the string into a histogram of characters of the string;

one or more instructions to convert the histogram of characters into a histogram of bins using a character to bin mapping;

one or more instructions to append a length of the string as a last bin of the histogram of bins;

one or more instructions to calculate a particular number of nearest neighbors for the histogram of bins in a kd-tree;

one or more instructions to calculate a string edit distance between the histogram of bins and a particular neighbor of the calculated nearest neighbors;

one or more instructions to, if the string edit distance is greater than a preset threshold for the particular neighbor, designate a match between the first user account and a second user account that is associated with the particular neighbor, to create a matched user account pair; and

one or more instructions to score the matched user account pair.

38. The one or more memory devices of claim 37, where the one or more instructions to score the matched user account pair comprise:

one or more instructions to create a graph that includes the first and second user accounts on one side, and values for account attributes on another side;

one or more instructions to locate an edge from one of the first and second user accounts to one account attribute value; and

one or more instructions to apply a weight to the edge.

39. The one or more memory devices of claim 37, where the one or more instructions to score the matched user account pair comprise:

one or more instructions to score the matched user account pair based on a single account attribute at a time; and

one or more instructions to combine the scores from different account attributes to generate a single score for the matched user account pair.