Method and system for determining sets of variant items

• US 9,418,138 B2
• Filed: 09/10/2015
• Issued: 08/16/2016
• 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: Roy Chowdhury, Amber, Kalinin, Alexander Y., Kumar, Vijay
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): ASPINWALL, EVAN S
• Application Number:
  US14/850,934
• Publication Number:
  US 20150379117A1
• Time in Patent Office: 341 Days
• Field of Search: 707/749
• 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;

accessing data that includes, for each individual item of individual ones of a plurality of items, a corresponding one or more text strings that describe, and are distinct from, the individual item;

for each particular item of at least some of the individual ones of the plurality of items;

for each of one or more other items of the individual ones of the plurality of items that are distinct from the particular item, comparing the one or more text strings describing the other item with the one or more text strings describing the particular item;

based at least in part on said comparing, identifying at least one of the one or more other items that are each distinct from, but a potential variant of, the particular item;

subsequent to said identifying, and for each identified other item of at least some of the one or more identified other items, generating an aligned pair, wherein one member of the aligned pair comprises the one or more text strings describing the identified other item, and the other member of the aligned pair comprises the one or more text strings describing the particular item, and wherein said generating comprises aligning the text in the one member with respect to the text in the other member; and

subsequent to said generating, and for each aligned pair of at least some of the one or more aligned pairs;

determining one or more misalignments between the text in one member of the aligned pair and the text in the other member of the aligned pair; and

assigning a similarity score to the aligned pair, wherein the similarity score depends at least in part on the determined one or more misalignments, and indicates a degree of confidence that the particular item that corresponds to the one or more text strings of one member of the aligned pair, and the other item that corresponds to the one or more text strings of the other member of the aligned pair, are distinct variants of each other;

based at least in part on a plurality of the generated aligned pairs, and on the similarity scores assigned to each of those aligned pairs, determining one or more variant sets of items from the plurality of items, wherein each variant set comprises multiple items of the plurality of items such that each item of the variant set is indicated to be a variant of a same item;

generating a network-based page based at least in part on the determined one or more variant sets of items; and

transmitting the generated network-based page over a communication network to a client computing device.

2. The computer-implemented method of claim 1, wherein said determining the one or more variant sets comprises:

generating a stored representation of an affinity graph comprising multiple nodes, wherein each node corresponds to one item of the plurality of items and is coupled to at least one other node of the multiple nodes by a weighted edge to which an item similarity weight is assigned;

wherein the item similarity weight assigned to each weighted edge that couples a first node and a second node of the multiple nodes is based, at least in part, on the similarity score assigned to an aligned pair of the generated aligned pairs whose first member comprises one or more text strings describing the item corresponding to the first node, and whose second member comprises one or more text strings describing the item corresponding to the second node;

performing graph clustering on the stored representation of the affinity graph to determine one or more clusters of nodes, wherein said graph clustering determines which nodes to include in a cluster based, at least in part, on the item similarity weights assigned to the weighted edges coupling the nodes of the affinity graph which are to be included in cluster; and

for each cluster of at least some of the determined one or more clusters, indicating that the items corresponding to the nodes in the cluster belong to a same variant set of the one or more variant sets.

3. The computer-implemented method of claim 1, wherein said corresponding one or more text strings that describe, and are distinct from, the individual item to which they correspond comprise one or more of:

a title for the individual item, variant attributes of the individual item, a product description of the individual item, and specifications of the individual item.

4. The computer-implemented method of claim 1, further comprising receiving said corresponding one or more text strings that describe, and are distinct from, the individual item to which they correspond from a merchant supplying the individual item.

5. The computer-implemented method of claim 1, wherein the data include an index of the plurality of items, and said accessing and said comparing include searching the index in order to identify the at least one of the one or more other items that are each distinct from, but a potential variant of, the particular item.

6. The computer-implemented method of claim 1, wherein said aligning the text in the one member with respect to the text in the other member comprises applying a text alignment algorithm to align the one or more text strings of the one member with respect to the one or more text strings of the other member.

7. The computer-implemented method of claim 6, wherein the text alignment algorithm comprises a version of a Needleman-Wunsch algorithm for aligning a group of one or more text strings with another group of one or more text strings.

8. The computer-implemented method of claim 7, wherein the version of the Needleman-Wunsch algorithm is weighted such that when performing said aligning the text in the one member with respect to the text in the other member, said applying the version of the Needleman-Wunsch algorithm penalizes a gap detected in the one or more text strings of the one member or the one or more text strings of the other member more than it penalizes a mismatch between the one or more text strings of the one member and the one or more text strings of the other member.

9. The computer-implemented method of claim 1, wherein the determined one or more misalignments comprise multiple misalignments;

wherein the method further includes, for each individual misalignment of the multiple misalignments, determining a respective subscore for the aligned pair based on the individual misalignment; and

wherein said assigning the similarity score to the aligned pair comprises assigning a result of a summation of the multiple subscores assigned to the aligned pair.

10. 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 perform;

accessing data that includes, for each individual item of individual ones of a plurality of items, a corresponding one or more text strings that describe, and are distinct from, the individual item;

for each particular item of at least some of the individual ones of the plurality of items;

for each of one or more other items of the individual ones of the plurality of items that are distinct from the particular item, comparing the one or more text strings describing the other item with the one or more text strings describing the particular item;

based at least in part on said comparing, identifying at least one of the one or more other items that are each distinct from, but a potential variant of, the particular item;

subsequent to said identifying, and for each identified other item of at least some of the one or more identified other items, generating an aligned pair, wherein one member of the aligned pair comprises the one or more text strings describing the identified other item, and the other member of the aligned pair comprises the one or more text strings describing the particular item, and wherein said generating comprises aligning the text in the one member with respect to the text in the other member; and

subsequent to said generating, and for each aligned pair of at least some of the one or more aligned pairs;

determining one or more misalignments between the text in one member of the aligned pair and the text in the other member of the aligned pair; and

assigning a similarity score to the aligned pair, wherein the similarity score depends at least in part on the determined one or more misalignments, and indicates a degree of confidence that the particular item that corresponds to the one or more text strings of one member of the aligned pair, and the other item that corresponds to the one or more text strings of the other member of the aligned pair, are distinct variants of each other;

based at least in part on a plurality of the generated aligned pairs, and on the similarity scores assigned to each of those aligned pairs, determining one or more variant sets of items from the plurality of items, wherein each variant set comprises multiple items of the plurality of items such that each item of the variant set is indicated to be a variant of a same item

generating a network-based page based at least in part on the determined one or more variant sets of items; and

transmitting the generated network-based page over a communication network to a client computing device.

11. The system of claim 10, wherein to perform said determining the one or more variant sets, the program instructions are further configured to perform:

generating a stored representation of an affinity graph comprising multiple nodes, wherein each node corresponds to one item of the plurality of items and is coupled to at least one other node of the multiple nodes by a weighted edge to which an item similarity weight is assigned;

wherein the item similarity weight assigned to each weighted edge that couples a first node and a second node of the multiple nodes is based, at least in part, on the similarity score assigned to an aligned pair of the generated aligned pairs whose first member comprises one or more text strings describing the item corresponding to the first node, and whose second member comprises one or more text strings describing the item corresponding to the second node;

performing graph clustering on the stored representation of the affinity graph to determine one or more clusters of nodes, wherein said graph clustering determines which nodes to include in a cluster based, at least in part, on the item similarity weights assigned to the weighted edges coupling the nodes of the affinity graph which are to be included in cluster; and

for each cluster of at least some of the determined one or more clusters, indicating that the items corresponding to the nodes in the cluster belong to a same variant set of the one or more variant sets.

12. The system of claim 10, wherein said corresponding one or more text strings that describe, and are distinct from, the individual item to which they correspond comprise one or more of:

a title for the individual item, variant attributes of the individual item, a product description of the individual item, and specifications of the individual item.

13. The system of claim 10, wherein to perform said determining the one or more misalignments, the program instructions are further configured to perform, for at least one misalignment of the determined one or more misalignments between the text in one member of the aligned pair and the text in the other member of the aligned pair, determining that a word of the text in one member of the aligned pair does not match a corresponding other word of the text in the other member of the aligned pair.

14. The system of claim 13, wherein the program instructions are further configured to, for the at least one misalignment of the determined one or more misalignments, assign a subscore to the aligned pair based on determining that the word and the corresponding other word match words of a predetermined set of words.

15. The system of claim 14, wherein the predetermined set of words comprises one or more of:

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

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

accessing data that includes, for each individual item of individual ones of a plurality of items, a corresponding one or more text strings that describe, and are distinct from, the individual item;

for each particular item of at least some of the individual ones of the plurality of items;

for each of one or more other items of the individual ones of the plurality of items that are distinct from the particular item, comparing the one or more text strings describing the other item with the one or more text strings describing the particular item;

based at least in part on said comparing, identifying at least one of the one or more other items that are each distinct from, but a potential variant of, the particular item;

subsequent to said identifying, and for each identified other item of at least some of the one or more identified other items, generating an aligned pair, wherein one member of the aligned pair comprises the one or more text strings describing the identified other item, and the other member of the aligned pair comprises the one or more text strings describing the particular item, and wherein said generating comprises aligning the text in the one member with respect to the text in the other member; and

subsequent to said generating, and for each aligned pair of at least some of the one or more aligned pairs;

determining one or more misalignments between the text in one member of the aligned pair and the text in the other member of the aligned pair; and

assigning a similarity score to the aligned pair, wherein the similarity score depends at least in part on the determined one or more misalignments, and indicates a degree of confidence that the particular item that corresponds to the one or more text strings of one member of the aligned pair, and the other item that corresponds to the one or more text strings of the other member of the aligned pair, are distinct variants of each other;

based at least in part on a plurality of the generated aligned pairs, and on the similarity scores assigned to each of those aligned pairs, determining one or more variant sets of items from the plurality of items, wherein each variant set comprises multiple items of the plurality of items such that each item of the variant set is indicated to be a variant of a same item

generating a network-based page based at least in part on the determined one or more variant sets of items; and

transmitting the generated network-based page over a communication network to a client computing device.

17. The computer-readable non-transitory storage medium of claim 16, wherein to perform said determining the one or more variant sets, the program instructions are further computer-executable to perform:

generating a stored representation of an affinity graph comprising multiple nodes, wherein each node corresponds to one item of the plurality of items and is coupled to at least one other node of the multiple nodes by a weighted edge to which an item similarity weight is assigned;

wherein the item similarity weight assigned to each weighted edge that couples a first node and a second node of the multiple nodes is based, at least in part, on the similarity score assigned to an aligned pair of the generated aligned pairs whose first member comprises one or more text strings describing the item corresponding to the first node, and whose second member comprises one or more text strings describing the item corresponding to the second node;

performing graph clustering on the stored representation of the affinity graph to determine one or more clusters of nodes, wherein said graph clustering determines which nodes to include in a cluster based, at least in part, on the item similarity weights assigned to the weighted edges coupling the nodes of the affinity graph which are to be included in cluster; and

for each cluster of at least some of the determined one or more clusters, indicating that the items corresponding to the nodes in the cluster belong to a same variant set of the one or more variant sets.

18. The computer-readable non-transitory storage medium of claim 16, wherein said corresponding one or more text strings that describe, and are distinct from, the individual item to which they correspond comprise one or more of:

a title for the individual item, variant attributes of the individual item, a product description of the individual item, and specifications of the individual item.

19. The computer-readable non-transitory storage medium of claim 16, wherein the program instructions are further computer-executable to perform receiving said corresponding one or more text strings that describe, and are distinct from, the individual item to which they correspond from a merchant supplying the individual item.

20. The computer-readable non-transitory storage medium of claim 16, wherein the determined one or more misalignments of the aligned pair comprise multiple misalignments;

wherein the program instructions are further computer-executable to perform, for each individual misalignment of the multiple misalignments, determining a respective subscore for the aligned pair based on the individual misalignment; and

wherein said assigning the similarity score to the aligned pair comprises assigning a result of a summation of the multiple subscores assigned to the aligned pair.