Dictionary for hierarchical attributes from catalog items

• US 8,606,788 B2
• Filed: 06/15/2011
• Issued: 12/10/2013
• Est. Priority Date: 06/15/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Zhimin, Laureano, Eduardo, Luo, Renfei, Mutungu, Tsheko, Narasayya, Vivek, Talby, David
• Primary Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US13/160,532
• Publication Number:
  US 20120323921A1
• Time in Patent Office: 909 Days
• Field of Search: None
• US Class Current: 707/740
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

A plurality of items included in a catalog may be obtained, each item associated with an item category. Brand indicators may be obtained, each brand indicator associated with the item category. Brand indicators associated with each of the items may be determined, and the each item may be assigned to a partition group associated with the brand indicator that is associated with the each item. Correlated string tokens that are correlated, greater than a predetermined correlation threshold value, with the brand indicator associated with the partition group that is associated with the each one of the items, the correlated string tokens associated with the each one of the plurality of items, may be determined. A dictionary hierarchy may be generated based on the one or more correlated string tokens.

Claims

1. A system comprising:

a dictionary manager embodied via executable instructions stored on a computer-readable storage medium, the dictionary manager including;

an item input engine configured to obtain a plurality of item character strings, each item character string representing an item in a catalog, each item associated with a category;

a brand input engine configured to obtain a plurality of brand character strings associated with the category;

a brand matching engine configured to determine, for each item character string included in the plurality of item character strings, whether a matched substring of the each item character string represents a match with one of the obtained brand character strings;

a matching indicator engine configured to generate a matching indicator indicating that the each item character string includes a match with the one of the obtained brand character strings, based on a match result of the matching determination by the brand matching engine;

a correlated segment engine configured to obtain, for each one of the obtained brand character strings, and for each one of the item character strings that includes a match with the each one of the obtained brand character strings, one or more correlated segments, other than the matched substring, of the each one of the item character strings that includes a match with the each one of the obtained brand character strings, based on determining that the obtained correlated segments are correlated, greater than a predetermined correlation threshold, with the each one of the obtained brand character strings;

a hierarchy generator configured to generate a dictionary hierarchy based on the obtained correlated segments;

a catalog input engine configured to obtain the catalog, the catalog including a list of items represented by item character strings;

a brand expansion engine configured to request an expanded list of brand values based on an initial list of brand values associated with the category; and

a category determination engine configured to request a determination of the category associated with the plurality of item character strings,

the item input engine configured to obtain the plurality of item character strings, each item character string representing an item in the catalog, each item associated with the category, based on the determination of the category determined by the category determination engine.

2. The system of claim 1, wherein:

each one of the plurality of item character strings is associated with one or more of;

a product included in a product catalog or an item included in an enumerated list of items included in a group of items.

3. The system of claim 1, further comprising:

a brand filtering engine configured to filter the expanded list of brand values based on positions of each brand value represented as a substring in groups of the plurality of item character strings.

4. The system of claim 1, further comprising:

a partition initialization engine configured to initialize a plurality of brand partition sets, each brand partition set associated with one of the obtained brand character strings, wherein

the matching indicator engine is configured to generate the matching indicator based on updating the brand partition set associated with the one of the obtained brand character strings that matches the matched substring to indicate an addition of the item associated with the each item character string, based on a match result of the matching determination by the brand matching engine.

5. The system of claim 4, further comprising:

a token determination engine configured to determine a respective plurality of item tokens associated with each respective one of the plurality of item character strings, wherein

the correlated segment engine is configured to determine a correlation value associated with each one of the tokens, based on determining a correlation of the each one of the tokens with the brand character string associated with the brand partition set that includes the item associated with the item character string that includes the each one of the tokens.

6. The system of claim 5, wherein:

the correlated segment engine is configured to determine the correlation value associated with the each one of the tokens, based on a comparison of;

a number of item character strings that are associated with the brand partition set that includes the item associated with the item character string that includes the each one of the tokens, and that include the one of the tokens, and

a number of item character strings that include the one of the tokens.

7. The system of claim 5, further comprising:

a token sequence determination engine configured to determine sequences of tokens included in the each respective one of the plurality of item character strings, the sequences of tokens matching values of attributes associated with the items represented by the plurality of item character strings; and

a cohesion determination engine configured to determine a cohesion value associated with adjacent sequences of tokens included in the each respective one of the plurality of item character strings.

8. The system of claim 5, wherein:

the hierarchy generator is configured to generate the dictionary hierarchy based on obtaining atomic token sequences based on the obtained correlated segments,

updating a tree structure based on the obtained atomic sequences, and

assigning an attribute value to the tree structure.

9. The system of claim 8, wherein:

the tree structure is based on a hierarchical arrangement associated with a hierarchy that is associated with hierarchical attributes associated with the category and the catalog, each of the attributes included as one or more substrings of one or more of the plurality of item character strings.

10. The system of claim 1, further comprising:

a partition initialization engine configured to determine a plurality of brand partition storage areas, each brand partition storage area associated with one of the obtained brand character strings, wherein

the matching indicator engine is configured to store the each item character string in the brand partition storage area associated with one of the obtained brand character strings that matches the matched substring, based on a result of the matching determination by the brand matching engine.

11. A method comprising:

obtaining a plurality of item character strings, each item character string representing an item in a catalog, each item associated with a category;

obtaining a plurality of brand character strings associated with the category;

determining via a device processor, for each item character string included in the plurality of item character strings, whether a matched substring of the each item character string represents a match with one of the obtained brand character strings;

generating a matching indicator indicating that the each item character string includes a match with the one of the obtained brand character strings, based on a match result of the matching determination;

obtaining, for each one of the obtained brand character strings, and for each one of the item character strings that includes a match with the each one of the obtained brand character strings, one or more correlated segments, other than the matched substring, of the each one of the item character strings that includes a match with the each one of the obtained brand character strings, based on determining that the obtained correlated segments are correlated, greater than a predetermined correlation threshold, with the each one of the obtained brand character strings;

generating a dictionary hierarchy based on the obtained correlated segments;

obtaining the catalog, the catalog including a list of items represented by item character strings;

requesting an expanded list of brand values based on an initial list of brand values associated with the category; and

requesting a determination of the category associated with the plurality of item character strings, the plurality of item character strings obtained, based on the determination of the determined category.

12. The method of claim 11, wherein:

each one of the plurality of item character strings is associated with one or more of;

a product included in a product catalog or an item included in an enumerated list of items included in a group of items.

13. The method of claim 11, further comprising:

filtering the expanded list of brand values based on positions of each brand value represented as a substring in groups of the plurality of item character strings.

14. The method of claim 11, further comprising:

initializing a plurality of brand partition sets, each brand partition set associated with one of the obtained brand character strings, wherein

the matching indicator is generated based on updating the brand partition set associated with the one of the obtained brand character strings that matches the matched substring to indicate an addition of the item associated with the each item character string, based on a match result of the matching determination by the brand matching engine.

15. A computer program product tangibly embodied on a machine readable storage device and including executable code configured to cause one or more processors to:

obtain a plurality of item character strings, each item character string representing an item in a catalog, each item associated with a category;

obtain a plurality of brand character strings associated with the category;

determine, for each item character string included in the plurality of item character strings, whether a matched substring of the each item character string represents a match with one of the obtained brand character strings;

generate a matching indicator indicating that the each item character string includes a match with the one of the obtained brand character strings, based on a match result of the matching determination;

obtain, for each one of the obtained brand character strings, and for each one of the item character strings that includes a match with the each one of the obtained brand character strings, one or more correlated segments, other than the matched substring, of the each one of the item character strings that includes a match with the each one of the obtained brand character strings, based on determining that the obtained correlated segments are correlated, greater than a predetermined correlation threshold, with the each one of the obtained brand character strings;

generate a dictionary hierarchy based on the obtained correlated segments;

obtain the catalog, the catalog including a list of items represented by item character strings;

request an expanded list of brand values based on an initial list of brand values associated with the category; and

request a determination of the category associated with the plurality of item character strings,

the plurality of item character strings obtained, based on the determination of the determined category.

16. The computer program product of claim 15, wherein the executable code is configured to cause the one or more processors to:

initialize a plurality of brand partition sets, each brand partition set associated with one of the obtained brand character strings, wherein

the matching indicator is generated based on updating the brand partition set associated with the one of the obtained brand character strings that matches the matched substring to indicate an addition of the item associated with the each item character string, based on a match result of the matching determination.

17. The computer program product of claim 16, wherein the executable code is configured to cause the one or more processors to:

determine a respective plurality of item tokens associated with each respective one of the plurality of item character strings, wherein

a correlation value associated with each one of the tokens is determined, based on determining a correlation of the each one of the tokens with the brand character string associated with the brand partition set that includes the item associated with the item character string that includes the each one of the tokens.

18. The computer program product of claim 17, wherein the executable code is configured to cause the one or more processors to:

determine the correlation value associated with the each one of the tokens, based on a comparison of;

a number of item character strings that are associated with the brand partition set that includes the item associated with the item character string that includes the each one of the tokens, and that include the one of the tokens, and

a number of item character strings that include the one of the tokens.

19. The computer program product of claim 17, wherein the executable code is configured to cause the one or more processors to:

determine sequences of tokens included in the each respective one of the plurality of item character strings, the sequences of tokens matching values of attributes associated with the items represented by the plurality of item character strings; and

determine a cohesion value associated with adjacent sequences of tokens included in the each respective one of the plurality of item character strings.

20. The computer program product of claim 17, wherein the executable code is configured to cause the one or more processors to:

generate the dictionary hierarchy based on;

obtaining atomic token sequences based on the obtained correlated segments,

updating a tree structure based on the obtained atomic sequences, and assigning an attribute value to the tree structure.