Search clustering

• US 8,589,398 B2
• Filed: 02/03/2012
• Issued: 11/19/2013
• Est. Priority Date: 11/20/2006
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Sundaresan, Neelakantan, Ganesan, Kavita, Grandhi, Roopnath
• Primary Examiner(s): Lee, Wilson
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US13/366,000
• Publication Number:
  US 20120185446A1
• Time in Patent Office: 655 Days
• Field of Search: 707/722, 707736-737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

In one example embodiment, a method is illustrated as including retrieving item data from a plurality of listings, the item data filtered from noise data, constructing at least one base cluster having at least one document with common item data stored in a suffix ordering, compacting the at least one base cluster to create a compacted cluster representation having a reduced duplicate suffix ordering amongst the clusters, and merging the compacted cluster representation to generate a merged cluster, the merging based upon a first overlap value applied to the at least one document with common item data.

Claims

1. A method comprising:

identifying noise data using a demand factor that is based on relationships of items and categories to query terms of search queries;

retrieving, from a plurality of listings, item data that is filtered from the noise data based on the demand factor;

constructing, using a processor of a machine, at least one base cluster having at least one document with common item data stored in a suffix ordering;

compacting the at least one base cluster to create a compacted cluster representation having a reduced duplicate suffix ordering amongst clusters; and

merging the compacted cluster representation to generate a merged cluster based upon a first overlap value applied to the at least one document with common item data.

2. The method of claim 1, further comprising calculating the demand factor based on the relationships of the items and the categories to query terms of search queries, the relationships established from user actions resulting from the search queries.

3. The method of claim 1, further comprising calculating a relevance score using the demand factor.

4. The method of claim 3, wherein the relevance score is calculated, in part, based on a comparison of a similarity of a demand category histogram and a supply category histogram.

5. The method of claim 3, further comprising using the relevance score to prune irrelevant clusters.

6. The method of claim 1, wherein the item data includes at least one selection of an item title, an item category, and seller information.

7. The method of claim 1, further comprising filtering item data from noise data based upon a frequency with which a word is used in a search as compared to a frequency another word is used in the search.

8. The method of claim 1, wherein the suffix ordering is stored in a data structure that includes at least one of a trie, a hash table, a binary search tree, a red-black tree, or a heap.

9. The method of claim 1, further comprising merging the compacted cluster representation based upon at least one of a relevance-weight factor, a seller factor, a price factor, a category factor, or an image factor.

10. The method of claim 1, further comprising evaluating the merged cluster to determine a coverage value for the merged cluster and a second overlap value relating to the at least one document contained within the merged cluster.

11. The method of claim 10, further comprising merging the compacted cluster representation to generate the merged cluster based upon the coverage value and the second overlap value.

12. The method of claim 1, further comprising:

receiving a search query, the search query relating to item data; and

extracting the item data from the merged cluster as a search result, the search result extracted based upon a similarity between the search query and the item data.

13. A system comprising:

a processor of a machine;

a demand data engine to identify noise data using a demand factor that is based on relationships of items and categories to query terms of search queries;

a retrieving engine to retrieve, from a plurality of listings, item data that is filtered from the noise data based on the demand factor;

a cluster generator to construct, using the processor, at least one base cluster having at least one document with common item data stored in a suffix ordering;

a compacting engine to compact the at least one base cluster to create a compacted cluster representation having a reduced duplicate suffix ordering amongst clusters; and

a first merging engine to merge the compacted cluster representation to generate a merged cluster based upon a first overlap value applied to the at least one document with common item data.

14. he system of claim 13, further comprising a separating engine to filter the item data from the noise data based upon a frequency with which a word is used in a search as compared to a frequency another word is used in the search.

15. The system of claim 13, further comprising a second merging engine to merge the compacted cluster representation based upon at least one of a relevance-weight factor, a seller factor, a price factor, a category factor, or an image factor.

16. The system of claim 13, further comprising a calculator to calculate a relevance score using the demand factor, the relevance score calculated, in part, based on a comparison of a similarity of a demand category histogram and a supply category histogram.

17. The system of claim 16, wherein the relevance score is used to prune irrelevant clusters.

18. The system of claim 13, further comprising an evaluation engine to evaluate the merged cluster to determine a coverage value for the merged cluster and a second overlap value relating to the at least one document contained within the merged cluster.

19. The system of claim 18, further comprising a third merging engine to merge the compacted cluster representation to generate a merged cluster based upon the coverage value and the second overlap value.

20. A tangible machine-readable storage device comprising instructions, which, when implemented by one or more machines that cause the one or more machines to perform the operations comprising:

identifying noise data using a demand factor that is based on relationships of items and categories to query terms of search queries;

retrieving, from a plurality of listings, item data that is filtered from the noise data based on the demand factor;

constructing, using a processor, at least one base cluster having at least one document with common item data stored in a suffix ordering;

compacting the at least one base cluster to create a compacted cluster representation having a reduced duplicate suffix ordering amongst clusters; and

merging the compacted cluster representation to generate a merged cluster based upon a first overlap value applied to the at least one document with common item data.