US6598054B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for clustering data objects in a collection
Assignee: Google LLC
•
Filing: 1999-10-19
•
Granted: 2003-07-22
•
Expires: 2019-10-19
Abstract
Abstract A system and method for browsing, retrieving, and recommending information from a collection uses multi-modal features of the documents in the collection, as well as an analysis of users' prior browsing and retrieval behavior. The system and method are premised on various disclosed methods for quantitatively representing documents in a document collection as vectors in multi-dimensional vector spaces, quantitatively determining similarity between documents, and clustering documents according to those similarities. The system and method also rely on methods for quantitatively representing users in a user population, quantitatively determining similarity between users, clustering users according to those similarities, and visually representing clusters of users by analogy to clusters of documents.
Inventors
- 👤 Hinrich Schuetze
- 👤 Peter L. Pirolli
- 👤 James E. Pitkow
- 👤 Ed H. Chi
- 👤 Jun Li
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 16:44
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/358; G06F16/90; G06F16/904; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
101 words
A method for selecting a set of initial cluster centers in wavefront clustering a collection of objects, each object being represented by a set of multi-modal feature vectors, comprising the steps of: selecting a first number of first objects from the collection; computing a vector centroid of the first objects using the set of multi-modal feature vectors associated with each object; selecting a second number of second objects from the collection; identifying a second number of initial cluster centers between the centroid and the second objects; and wavefront clustering the collection of objects using the second number of initial cluster centers.
Claim 2
Independent Claim
101 words
A method for selecting a set of initial cluster centers in wavefront clustering a collection of objects, each object being represented by a set of multi-modal feature vectors, comprising the steps of: selecting a first number of first objects from the collection; computing a vector centroid of the first objects using the set of multi-modal feature vectors associated with each object; selecting a second number of second objects from the collection; identifying a second number of initial cluster centers between the centroid and the second objects; and wavefront clustering the collection of objects using the second number of initial cluster centers.
Claim 3
Dependent Claim
16 words
The method of claim 1 , wherein the first objects are selected randomly from the collection.
Claim 4
Dependent Claim
21 words
The method of claim 2 , wherein the first number is much smaller than the number of objects in the collection.
Claim 5
Dependent Claim
15 words
The method of claim 3 , wherein the first number is greater than five (5).
Claim 6
Dependent Claim
13 words
The method of claim 4 , wherein the second number is ten (10).
Claim 7
Dependent Claim
16 words
The method of claim 1 , wherein the second objects are selected randomly from the collection.
Claim 8
Dependent Claim
20 words
The method of claim 6 , wherein the second number is equal to a desired number of initial cluster centers.
Claim 9
Dependent Claim
75 words
The method of claim 1 , wherein each of the second number of initial cluster centers is calculated according to {right arrow over (x)} i ′=α{right arrow over (c)}+(1−α){right arrow over (x)} i , where {right arrow over (x)} i ′ represents an initial cluster center, α represents a scalar factor, {right arrow over (x)} i represents one of the second objects, and {right arrow over (c)} represents the vector centroid of the first objects.
Claim 10
Dependent Claim
13 words
The method of claim 8 , wherein α is approximately equal to 0.9.
Claim 11
Dependent Claim
99 words
A computer readable medium storing instructions for wavefront clustering a collection of objects, each object being represented by a set of multi-modal feature vectors, comprising the instructions for: randomly selecting a first number of first objects from the collection; computing a vector centroid of the first objects using the set of multi-modal feature vectors associated with each object; randomly selecting a second number of second objects from the collection; identifying a second number of initial cluster centers between the centroid and the second objects; and performing iterated k-means wavefront clustering around the initial cluster centers to cluster the objects.
Claim 12
Dependent Claim
99 words
A computer readable medium storing instructions for wavefront clustering a collection of objects, each object being represented by a set of multi-modal feature vectors, comprising the instructions for: randomly selecting a first number of first objects from the collection; computing a vector centroid of the first objects using the set of multi-modal feature vectors associated with each object; randomly selecting a second number of second objects from the collection; identifying a second number of initial cluster centers between the centroid and the second objects; and performing iterated k-means wavefront clustering around the initial cluster centers to cluster the objects.
Claim 13
Dependent Claim
23 words
The computer readable medium of claim 10 , wherein the first number is much smaller than the number of objects in the collection.
Claim 14
Dependent Claim
17 words
The computer readable medium of claim 11 , wherein the first number is greater than five (5).
Claim 15
Dependent Claim
22 words
The computer readable medium of claim 10 , wherein the second number is equal to a desired number of initial cluster centers.
Claim 16
Dependent Claim
77 words
The computer readable medium of claim 13 , wherein each of the second number of initial cluster centers is calculated according to {right arrow over (x)} i ′=α{right arrow over (c)}+(1−α){right arrow over (x)} i , where {right arrow over (x)} i ′ represents an initial cluster center, α represents a scalar factor, {right arrow over (x)} i represents one of the second objects, and {right arrow over (c)} represents the vector centroid of the first objects.
Claim 17
Dependent Claim
13 words
The method of claim 14 , wherein α is approximately equal to 0.9.
Claim 18
Dependent Claim
129 words
A signal for transmitting computer instructions for selecting a set of initial cluster centers in wavefront clustering a collection of objects, each object being represented by a set of multi-modal feature vectors, the instructions comprising: randomly selecting a first number of first objects from the collection, the first number being less than a number of objects in the collection; computing a vector centroid of the first objects using the set of multi-modal feature vectors associated with each object; selecting a second number of second objects from the collection, the second number equaling a desired number of initial cluster centers; identifying a second number of initial cluster centers between the centroid and the second objects; and wavefront clustering the collection of objects using the second number of initial cluster centers.
Claim 19
Dependent Claim
129 words
A signal for transmitting computer instructions for selecting a set of initial cluster centers in wavefront clustering a collection of objects, each object being represented by a set of multi-modal feature vectors, the instructions comprising: randomly selecting a first number of first objects from the collection, the first number being less than a number of objects in the collection; computing a vector centroid of the first objects using the set of multi-modal feature vectors associated with each object; selecting a second number of second objects from the collection, the second number equaling a desired number of initial cluster centers; identifying a second number of initial cluster centers between the centroid and the second objects; and wavefront clustering the collection of objects using the second number of initial cluster centers.
Claim 20
Dependent Claim
75 words
The signal of claim 16 , wherein each of the second number of initial cluster centers is calculated according to {right arrow over (x)} i ′=α{right arrow over (c)}+(1−α){right arrow over (x)} i , where {right arrow over (x)} i ′ represents an initial cluster center, α represents a scalar factor, {right arrow over (x)} i represents one of the second objects, and {right arrow over (c)} represents the vector centroid of the first objects.
Claim 21
Dependent Claim
13 words
The signal of claim 17 , wherein α is approximately equal to 0.9.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-07-21 | 2007-01-20 | 2007-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-07-21 | 2011-01-20 | 2011-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-07-21 | 2015-01-20 | 2015-07-22 | $7700.00 | Window Closed / Lapsed |