SEARCH CLUSTERING

• US 20080120292A1
• Filed: 06/29/2007
• Published: 05/22/2008
• 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
• Granted Patent: US 8,131,722 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• 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 compact 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:

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 compact 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.

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

3. The method of claim 1, wherein the item data is part of a plurality of merged clusters organized into a hierarchy of merged clusters.

4. 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.

5. 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, and a heap.

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

7. The method of claim 6, further comprising calculating 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.

8. The method of claim 1, further comprising labeling the at least one base cluster.

9. 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 documents contained within the merged cluster.

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

11. 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.

12. A computer system comprising:

a retrieving engine to retrieve item data from a plurality of listings, the item data filtered from noise data;

a cluster generator to construct 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 the clusters; and

a first merging engine to merge the compact 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.

13. The computer system of claim 12, wherein the item data includes at least one of an item title, an item category, and seller information.

14. The computer system of claim 12, wherein the item data is part of a plurality of merged clusters organized into a hierarchy of merged clusters.

15. The computer system of claim 12, further comprising a separating engine to filter 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.

16. The computer system of claim 12, 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, and a heap.

17. The computer system of claim 12, further comprising a second merging engine to merge the compact cluster representation based upon at least one of a demand factor, a relevance-weight factor, a seller factor, a price factor, a category factor, and an image factor.

18. The computer system of claim 17, 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.

19. The computer system of claim 12, further comprising a labeling engine to label the at least one base cluster.

20. The computer system of claim 12, 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 documents contained within the merged cluster.

21. The computer system of claim 20, 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.

22. The computer system of claim 12, further comprising:

a receiver to receive a search query, the search query relating to item data; and

an extractor to extract 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.

23. An apparatus comprising:

means for retrieving item data from a plurality of listings, the item data filtered from noise data;

means for constructing at least one base cluster having at least one document with common item data stored in a suffix ordering;

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

means for merging the compact 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.

24. A machine-readable medium comprising instructions, which, when implemented by one or more machines that cause the one or more machines to perform the following operations:

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 compact 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.