Method and system for determining sets of variant items

• US 9,135,396 B1
• Filed: 12/22/2008
• Issued: 09/15/2015
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Chowdhury, Amber Roy, Kumar, Vijay, Kalinin, Alexander Y.
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): ASPINWALL, EVAN S
• Application Number:
  US12/341,003
• Time in Patent Office: 2,458 Days
• Field of Search: 707/711, 707/722, 707/723, 707/726, 707/728, 707/735, 707/736, 707/737, 707/738, 707/739, 707/748, 707/749, 707/752, 707/758, 707/780, 707/999.006, 715/247, 715/256
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/30 Unsupervised data analysis
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics

Abstract

Various embodiments of a method and system for determining sets of variant items are described. Various embodiments may include a system configured to generate multiple item pairs each corresponding to a particular item and another item determined to be similar to the particular item. For the particular item and the other item, each item pair may include a respective sequence of text strings (e.g., a title). For each item pair, the system may perform a corresponding text alignment and determine one or more misalignments of the item pair. The system may also assign a similarity score to each item pair; the similarity score may be dependent on the misalignment(s) determined for the particular item pair. Based on each aligned item pair and the similarity score assigned to that aligned item pair, the system may generate an indication specifying that each of a set of items are variants of each other.

Claims

1. A computer-implemented method, comprising:

performing, by one or more computers having at least one processor and memory;

for each particular item of a plurality of items;

determining one or more other items of the plurality of items that are each distinct from but similar to the particular item, wherein said determining is based on accessing data that includes, for each item of the plurality of items, a textual description of the item that describes the item but is not itself an item in the plurality of items;

for each given item of the determined one or more other items, identifying an item data pair with one member comprising a sequence of text strings from the textual description of the particular item, and the other member comprising another sequence of text strings from the textual description of the given item;

subsequent to said identifying, aligning each identified item data pair, wherein said aligning the identified item data pair comprises aligning text in the sequence of text strings from the textual description of the particular item with text in the other sequence of text strings from the textual description of the given item; and

for each aligned item data pair, determining one or more misalignments of the aligned item data pair, and assigning a similarity score to the aligned item data pair dependent on the one or more misalignments, wherein the similarity score indicates a degree of confidence that the given item and the particular item are distinct variants of each other; and

based on a plurality of the aligned item data pairs and similarity scores assigned to each of those aligned item data pairs, determining a variant set comprising multiple ones of the plurality of items, wherein each item of the variant set is determined to be a variant of each other item of the variant set;

wherein at least one of the aligned item data pairs comprises multiple misalignments;

for each misalignment of the multiple misalignments, determining a respective subscore based on that misalignment;

wherein said assigning the similarity score to said at least one aligned item data pair comprises assigning a result of a combination of each of said subscores to said at least one aligned item data pair.

2. The computer-implemented method of claim 1, wherein determining the variant set comprises:

generating a stored representation of an affinity graph comprising multiple nodes, each node coupled to an other node by a weighted edge;

wherein each of said multiple nodes corresponds to one of said plurality of items;

wherein each weighted edge coupling a particular node to an other node is assigned an item similarity weight based on at least one of said assigned similarity scores assigned to an aligned item data pair comprising a sequence of text strings from the textual description of the item corresponding to said particular node, and further comprising another sequence of text strings from the textual description of the item corresponding to said other node;

performing graph clustering on said stored representation of the affinity graph to determine a cluster of nodes, wherein said graph clustering determines which nodes to include in the cluster based on the item similarity weights assigned to the weighted edges coupling the nodes of the multiple nodes; and

for each node of the cluster, indicating that the item that corresponds to that node is a member of said variant set.

3. The computer-implemented method of claim 1, wherein the sequence of text strings from the textual description of the particular item, and the other sequence of text strings from the textual description of the given item, respectively comprise one or more of:

an item title, item description, and item specification for the particular item and the other item.

4. The computer-implemented method of claim 1, further comprising receiving one or more of the sequences of text strings from a merchant that supplies the corresponding ones of said plurality of items.

5. The computer-implemented method of claim 1, wherein said determining the one or more other items that are each distinct from but similar to the particular item comprises performing a search of an index of multiple items to determine a list of results, and selecting the one or more other items from the list of results.

6. The computer-implemented method of claim 1, wherein said aligning each identified item data pair comprises performing a text alignment algorithm on the sequence of text strings from the textual description of the particular item and the other sequence of text strings from the textual description of the given item.

7. The computer-implemented method of claim 6, wherein said text-alignment algorithm comprises a version of a Needleman-Wunsch algorithm for text alignment of two sequences of text strings.

8. The computer-implemented method of claim 7, wherein said version of the Needleman-Wunsch algorithm is weighted such that said performing the version of the Needleman-Wunsch algorithm on the sequence of text strings from the textual description of the particular item and the other sequence of text strings from the textual description of the given item penalizes a gap detected between the two sequences more than a mismatch detected between the two sequences of text strings.

9. The computer-implemented method of claim 1, wherein the method further comprises weighting at least one of said subscores according to a respective configurable weight.

10. The computer-implemented method of claim 1, wherein said determining one or more misalignments of the aligned item data pair comprises, for at least one of said misalignments, determining that a word of said sequence of text strings from the textual description of said particular item does not match another word of the other sequence of text strings from the textual description of the given item.

11. The computer-implemented method of claim 10, wherein the method comprises, for the at least one misalignment, determining that said word, and said other word, match words of a predetermined set of words, and assigning a subscore to said at least one misalignment based on said predetermined set of words.

12. The computer-implemented method of claim 11, wherein said predetermined set of words comprises one of:

a set of multiple colors and a set of multiple sizes.

13. The computer-implemented method of claim 11, wherein said assigning a subscore to said at least one misalignment based on the predetermined set of words comprises assigning a positive subscore to said at least one misalignment.

14. The computer-implemented method of claim 11, wherein said predetermined set of words comprises one of:

a set of multiple product names, a set of multiple brands and a set of multiple sports teams.

15. The computer-implemented method of claim 11, wherein said assigning a subscore to said at least one misalignment based on the predetermined set of words comprises assigning a negative subscore to said at least one misalignment.

16. A system, comprising:

a memory comprising program instructions; and

one or more processors coupled to said memory, wherein the program instructions are executable by at least one of said one or more processors to;

for each particular item of a plurality of items;

determine one or more other items of the plurality of items that are each distinct from but similar to the particular item, wherein said determining is based on accessing data that includes, for each item of the plurality of items, a textual description of the item that describes the item but is not itself an item in the plurality of items;

for each given item of the determined one or more other items, identify an item data pair with one member comprising a sequence of text strings from the textual description of the particular item, and the other member comprising another sequence of text strings from the textual description of the given item;

subsequent to said identifying, align each identified item data pair, wherein to align the identified item data pair the program instructions are configured to align text in the sequence of text strings from the textual description of the particular item with text in the other sequence of text strings from the textual description of the given item; and

for each aligned item data pair, determine one or more misalignments of the aligned item data pair, and assign a similarity score to the aligned item data pair dependent on the one or more misalignments, wherein the similarity score indicates a degree of confidence that the given item and the particular item are distinct variants of each other; and

based on a plurality of the aligned item data pairs and similarity scores assigned to each of those aligned item data pairs, determine a variant set comprising multiple ones of the plurality of items, wherein each item of the variant set is determined to be a variant of each other item of the variant set;

wherein at least one of the aligned item data pairs comprises multiple misalignments;

for each misalignment of the multiple misalignments, determine a respective subscore based on that misalignment;

wherein to assign the similarity score to said at least one aligned item data pair, the program instructions are configured to assign a result of a combination of each of said subscores to said at least one aligned item data pair.

17. The system of claim 16, wherein to determine the variant set, the program instructions are configured to:

generate a stored representation of an affinity graph comprising multiple nodes, each node coupled to an other node by a weighted edge;

wherein each of said multiple nodes corresponds to one of said plurality of items;

wherein each weighted edge coupling a particular node to an other node is assigned an item similarity weight based on at least one of said assigned similarity scores assigned to an aligned item data pair comprising a sequence of text strings from the textual description of the item corresponding to said particular node, and further comprising another sequence of text strings from the textual description of the item corresponding to said other node;

perform graph clustering on said stored representation of the affinity graph to determine a cluster of nodes, wherein said graph clustering determines which nodes to include in the cluster based on the item similarity weights assigned to the weighted edges coupling the nodes of the multiple nodes; and

for each node of the cluster, indicate that the item that corresponds to that node is a member of said variant set.

18. The system of claim 16, wherein the sequence of text strings from the textual description of the particular item, and the other sequence of text strings from the textual description of the given item, respectively comprise one or more of:

an item title, item description, and item specification for the particular item and the other item.

19. The system of claim 16, wherein the program instructions are configured to receive one or more of the sequences of text strings from a merchant that supplies the corresponding ones of said plurality of items.

20. The system of claim 16, wherein to determine the one or more other items that are each distinct from but similar to the particular item, the program instructions are configured to perform a search of an index of multiple items to determine a list of results, and to select the one or more other items from the list of results.

21. The system of claim 16, wherein to align each identified item data pair, the program instructions are configured to perform a text alignment algorithm on the sequence of text strings from the textual description of the particular item and the other sequence of text strings from the textual description of the given item.

22. The system of claim 21, wherein said text-alignment algorithm comprises a version of a Needleman-Wunsch algorithm for text alignment of two sequences of text strings.

23. The system of claim 22, wherein said version of the Needleman-Wunsch algorithm is weighted such that said performing the version of the Needleman-Wunsch algorithm on the sequence of text strings from the textual description of the particular item and the other sequence of text strings from the textual description of the given item penalizes a gap detected between the two sequences more than a mismatch detected between the two sequences of text strings.

24. The system of claim 16, wherein each of said subscores is configured to be weighted according to a respective configurable weight.

25. The system of claim 16, wherein to determine the one or more misalignments of the aligned item data pair, the program instructions are configured to, for at least one of said misalignments, determine that a word of said sequence of text strings from the textual description of said particular item does not match another word of the other sequence of text strings from the textual description of the given item.

26. The system of claim 25, wherein the program instructions are configured to, for the at least one misalignment, determine that said word, and said other word, match words of a predetermined set of words, and assign a subscore to said at least one misalignment based on said predetermined set of words.

27. The system of claim 26, wherein said predetermined set of words comprises one of:

a set of multiple colors and a set of multiple sizes.

28. The system of claim 26, wherein to assign the subscore to said at least one misalignment based on the predetermined set of words, the program instructions are configured to assign a positive subscore to said at least one misalignment.

29. The system of claim 26, wherein said predetermined set of words comprises one of:

a set of multiple product names, a set of multiple brands and a set of multiple sports teams.

30. The system of claim 26, wherein to assign the subscore to said at least one misalignment based on the predetermined set of words, the program instructions are configured to assign a negative subscore to said at least one misalignment.

31. A computer-readable non-transitory storage medium storing program instructions computer-executable to:

for each particular item of a plurality of items;

determine one or more other items of the plurality of items that are each distinct from but similar to the particular item, wherein said determining is based on accessing data that includes, for each item of the plurality of items, a textual description of the item that describes the item but is not itself an item in the plurality of items;

for each given item of the determined one or more other items, identify an item data pair with one member comprising a sequence of text strings from the textual description of the particular item, and the other member comprising another sequence of text strings from the textual description of the given item;

subsequent to said identifying, align each identified item data pair, wherein to align the identified item data pair the program instructions are configured to align text in the sequence of text strings from the textual description of the particular item with text in the other sequence of text strings from the textual description of the given item; and

for each aligned item data pair, determine one or more misalignments of the aligned item data pair, and assign a similarity score to the aligned item data pair dependent on the one or more misalignments, wherein the similarity score indicates a degree of confidence that the given item and the particular item are distinct variants of each other; and

based on a plurality of the aligned item data pairs and similarity scores assigned to each of those aligned item data pairs, determine a variant set comprising multiple ones of the plurality of items, wherein each item of the variant set is determined to be a variant of each other item of the variant set;

wherein at least one of the aligned item data pairs comprises multiple misalignments;

for each misalignment of the multiple misalignments, determine a respective subscore based on that misalignment;

wherein to assign the similarity score to said at least one aligned item data pair, the program instructions are configured to assign a result of a combination of each of said subscores to said at least one aligned item data pair.

32. The computer-readable non-transitory storage medium of claim 31, wherein to determine the variant set, the program instructions are configured to:

generate a stored representation of an affinity graph comprising multiple nodes, each node coupled to an other node by a weighted edge;

wherein each of said multiple nodes corresponds to one of said plurality of items;

wherein each weighted edge coupling a particular node to an other node is assigned an item similarity weight based on at least one of said assigned similarity scores assigned to an aligned item data pair comprising a sequence of text strings from the textual description of the item corresponding to said particular node, and further comprising another sequence of text strings from the textual description of the item corresponding to said other node;

perform graph clustering on said stored representation of the affinity graph to determine a cluster of nodes, wherein said graph clustering determines which nodes to include in the cluster based on the item similarity weights assigned to the weighted edges coupling the nodes of the multiple nodes; and

for each node of the cluster, indicate that the item that corresponds to that node is a member of said variant set.

33. The computer-readable non-transitory storage medium of claim 31, wherein the sequence of text strings from the textual description of the particular item, and the other sequence of text strings from the textual description of the given item, respectively comprise one or more of:

an item title, item description, and item specification for the particular item and the other item.

34. The computer-readable non-transitory storage medium of claim 31, wherein the program instructions are configured to receive one or more of the sequences of text strings from a merchant that supplies the corresponding ones of said plurality of items.

35. The computer-readable non-transitory storage medium of claim 31, wherein to determine the one or more other items that are each distinct from but similar to the particular item, the program instructions are configured to perform a search of an index of multiple items to determine a list of results, and to select the one or more other items from the list of results.

36. The computer-readable non-transitory storage medium of claim 31, wherein to align each identified item data pair, the program instructions are configured to perform a text alignment algorithm on the sequence of text strings from the textual description of the particular item and the other sequence of text strings from the textual description of the given item.

37. The computer-readable non-transitory storage medium of claim 36, wherein said text-alignment algorithm comprises a version of a Needleman-Wunsch algorithm for text alignment of two sequences of text strings.

38. The computer-readable non-transitory storage medium of claim 37, wherein said version of the Needleman-Wunsch algorithm is weighted such that said performing the version of the Needleman-Wunsch algorithm on the sequence of text strings from the textual description of the particular item and the other sequence of text strings from the textual description of the given item penalizes a gap detected between the two sequences more than a mismatch detected between the two sequences of text strings.

39. The computer-readable non-transitory storage medium of claim 31, wherein each of said subscores is configured to be weighted according to a respective configurable weight.

40. The computer-readable non-transitory storage medium of claim 31, wherein to determine the one or more misalignments of the aligned item data pair, the program instructions are configured to, for at least one of said misalignments, determine that a word of said sequence of text strings from the textual description of said particular item does not match another word of the other sequence of text strings from the textual description of the given item.

41. The computer-readable non-transitory storage medium of claim 40, wherein the program instructions are configured to, for the at least one misalignment, determine that said word, and said other word, match words of a predetermined set of words, and assign a subscore to said at least one misalignment based on said predetermined set of words.

42. The computer-readable non-transitory storage medium of claim 41, wherein said predetermined set of words comprises one of:

a set of multiple colors and a set of multiple sizes.

43. The computer-readable non-transitory storage medium of claim 41, wherein to assign the subscore to said at least one misalignment based on the predetermined set of words, the program instructions are configured to assign a positive subscore to said at least one misalignment.

44. The computer-readable non-transitory storage medium of claim 41, wherein said predetermined set of words comprises one of:

a set of multiple product names, a set of multiple brands and a set of multiple sports teams.

45. The computer-readable non-transitory storage medium of claim 41, wherein to assign the subscore to said at least one misalignment based on the predetermined set of words, the program instructions are configured to assign a negative subscore to said at least one misalignment.

46. A computer-readable non-transitory storage medium storing program instructions computer-executable to, for a plurality of items:

identify a multiplicity of item pairs, each comprising two distinct items from the plurality of items that are similar to each other, wherein said determining is based on accessing data that includes, for each item of the plurality of items, a textual description of the item that describes the item but is not itself an item in the plurality of items;

for each identified item pair of the multiplicity of item pairs, receive a corresponding item information pair, wherein one member of the corresponding item information pair contains text from the textual description of one item of the identified item pair, while the other member of the corresponding item information pair contains text from the textual description of the other item of the identified item pair;

for each two members of each item information pair of the received plurality of item information pairs;

align the text in the one member with the text in the other member;

assign a score to the item information pair based on ascertaining the presence, within one or more predetermined variation phrase sets, of text strings determined to be mismatched within the aligned text, wherein the score indicates a degree of probability that the one item of the plurality of items whose textual description comprises the text in the one member and the other item of the plurality of items whose textual description comprises the text in the other member are variants of each other; and

based on the assigned score, determine a likelihood that the one item of the plurality of items whose textual description comprises the text in the one member and the other item of the plurality of items whose textual description comprises the text in the other member are variants of each other;

wherein at least one of the item information pairs comprises multiple mismatches;

for each mismatch of the multiple mismatches, determine a respective subscore based on that misalignment;

wherein to assign the score to said at least one item information pair, the program instructions are configured to assign a result of a combination of each of said subscores to said at least one item information pair.