Multi-pass data organization and automatic naming

• US 7,933,877 B2
• Filed: 04/30/2010
• Issued: 04/26/2011
• Est. Priority Date: 12/28/2006
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Sarwar, Badrul M., Mount, John A.
• Primary Examiner(s): Fleurantin; Jean B.
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US12/771,958
• Publication Number:
  US 20100223289A1
• Time in Patent Office: 361 Days
• Field of Search: 707/688, 707/736, 707/769, 707/770, 709/217, 709/218, 709/219
• US Class Current: 707/688
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A method and a system to organize a data set into groups of data subsets in multiple passes using different parameters and to automatically name the groups is disclosed. For example, a data set is retrieved in accordance with a search query submitted by a user. The data set is organized into clusters based on a statistic(s) of the data set. The data set is then organized into groups of data subsets based on an attribute(s) indicated by the data set. Each of the groups are automatically named based on a property shared by data units of the group. The name(s) of a group may be mined from the data units of the group, retrieved from a structure that maps to attribute values indicated by the data units of the group, etc.

Claims

1. A computer-implemented method comprising:

receiving a query from a client machine;

retrieving a data set based on the query.

the data set including a plurality of data units;

a data unit of the plurality of data units being representative of an item,

the data unit includes a value of an attribute of the item represented by the data unit;

performing a first operation that organizes the data set into a first plurality of clusters;

performing a second operation that partitions the first plurality of clusters into a second plurality of clusters and a third plurality of clusters, the second plurality of clusters being characterized by an attribute common to each cluster of the second plurality of clusters,

a cluster of the second plurality of clusters including the data unit,

the attribute common to each cluster of the second plurality of clusters being the attribute of the item,

the third plurality of clusters being characterized by absence of the attribute from each cluster of the third plurality of clusters,

the second operation being performed using a processor of a server machine communicatively coupled to the client machine and to a database; and

storing the second plurality of clusters in the database.

2. The computer-implemented method of claim 1, wherein

the first operation includes a statistical analysis of the data set.

3. The computer-implemented method of claim 2, wherein

the statistical analysis processes information selected from a group consisting of:

an attribute of an item;

a number of attributes of the item;

a description of the item;

an amount of text in the description of the item;

a taxonomy of the item;

a probability that the item co-occurs with a further item; and

user behavior data.

4. The computer-implemented method of claim 2, wherein

the statistical analysis is based on a technique selected from a group consisting of:

k-means clustering;

fuzzy clustering; and

agglomerative clustering.

5. The computer-implemented method of claim 1, wherein:

the first plurality of clusters includes a first cluster; and

the second operation determines that an entirety of the first cluster is to be included in the second plurality of clusters.

6. The computer-implemented method of claim 1, wherein:

the first plurality of clusters includes a first cluster;

the second operation divides the first cluster into first and second portions and determines that the first portion is to be included in the second plurality of clusters; and

the second portion is absent from the second plurality of clusters.

7. The computer-implemented method of claim 1 further comprising

naming a cluster of the second plurality of clusters.

8. The computer-implemented method of claim 7, wherein:

the cluster includes data units, each of the data units representing one of a plurality of items;

the naming is based on a property shared by a majority of the data units included in the cluster; and

the method further comprises

determining the property shared by the majority of the data units.

9. The computer-implemented method of claim 8, wherein:

each of the data units includes one of a plurality of values; and

the determining of the property includes identifying a value common to each of the majority of the data units.

10. The computer-implemented method of claim 8, wherein:

each of the data units includes one of a plurality of values;

the determining of the property includes identifying a value related to each of the majority of the data units; and

the identifying of the value includes accessing a data structure that includes at least one of synonyms or similar terms.

11. The method of claim 1, wherein:

the second operation is performed subsequent to the first operation.

12. A system comprising:

a memory to host a data set including plurality of data units;

a navigation module configured to retrieve a plurality of data units responsive to a query received from a client machine;

a data unit of the plurality of data units being representative of an item,

the data unit including a value of an attribute of the item represented by the data unit;

a hardware-implemented organizing module communicatively coupled to the navigation module, the organizing module being configured to;

perform a first operation that organizes the data set into a first plurality of clusters; and

perform a second operation that partitions the first plurality of clusters into a second plurality of clusters and a third plurality of clusters,

the second plurality clusters being characterized by an attribute common to each cluster of the second plurality of clusters,

a cluster of the second plurality of clusters includes the data unit;

the attribute common to each cluster of the second plurality of clusters is the attribute of the item,

the third plurality of clusters being characterized by absence of the attribute from each cluster of the third plurality of clusters; and

a storage module communicatively coupled to the organizing module, the storage module being configured to store the second plurality of clusters in a database.

13. The system of claim 12, wherein:

the first operation includes a statistical analysis of the data set; and

the statistical analysis is based on a technique selected from a group consisting of;

k-means clustering;

fuzzy clustering; and

agglomerative clustering.

14. The system of claim 12, wherein:

the first plurality of clusters includes a first cluster;

the second operation divides the first cluster into first and second portions and determines that the first portion is to be included in the second plurality of clusters; and

the second plurality of clusters does not include the second portion.

15. The system of claim 12 further comprising

a naming module communicatively coupled to the organizing module, the naming module being configured to name a cluster of the second plurality of clusters.

16. A machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to perform a method comprising:

receiving a query from a client machine;

retrieving a data set based on the query;

the data set including a plurality of data units;

a data unit of the plurality of data units being representative of an item,

the data unit includes a value of an attribute of the item represented by the data unit;

performing a first operation that organizes the data set into a first plurality of clusters;

performing a second operation that partitions the first plurality of clusters into a second plurality of clusters and a third plurality of clusters,

the second plurality of clusters being characterized by an attribute common to each cluster of the second plurality of clusters,

a cluster of the second plurality of clusters includes the data unit;

the attribute common to each cluster of the second plurality of clusters is the attribute of the item,

the third plurality clusters being characterized by absence of the attribute from each cluster of the third plurality clusters; and

storing the second plurality of clusters in a database.

17. The machine-readable storage medium of claim 16, wherein:

the first plurality of clusters includes a first cluster;

the second operation divides the first cluster into first and second portions and determines that the first portion is to be included in the second plurality of clusters; and

the second portion is absent from the second plurality of clusters.