Document clustering that applies a locality sensitive hashing function to a feature vector to obtain a limited set of candidate clusters

1. A method of clustering a plurality of documents from a data stream comprising:

generating a feature vector for a document in the plurality of documents;

applying a locality sensitive hashing function to the feature vector;

retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector;

determining a distance between the feature vector of the document and each of the cluster centroids; and

assigning the document to a cluster based on the determined distances.

2. The method of claim 1 wherein the feature vector is {right arrow over (d)}=[d 1 , . . . , d T ] and applying a locality sensitive hashing function to the feature vector comprises:

calculating entries in a hash value

h

=

∑

i

=

1

K

⁢

min

j

=

1

,

…

⁢

,

T

d

j

>

0

⁢

mod

⁢

⁢

(

a

i

·

j

+

b

i

,

p

i

)

using indices j of non-zero entries of the feature vector and random numbers a i , b i , and p i for i=1, . . . K wherein mod is a function that returns a remainder of an integer division.

3. The method of claim 1 wherein applying a locality sensitive hashing function to the feature vector comprises:

hashing the feature vector with a locality sensitive hashing function comprising a series of hashing functions;

determining a set of values similar to a set of results of the hashing of the feature vector; and

determining a set of cluster identifiers based on the determined set of values.

4. The method of claim 1 wherein retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector further comprises:

selecting a group of cluster centroids based on a size of clusters associated with the cluster centroids.

5. The method of claim 1 wherein assigning the document to a cluster based on the determined distances comprises:

if the determined distances between the feature vector of the document and a plurality of cluster centroids are below a predetermined threshold:

assigning the document to clusters corresponding to that plurality of cluster centroids;

updating the cluster centroids based on the feature vector of the document; and

updating the relative ages of the cluster centroids.

6. The method of claim 1 wherein assigning the document to a cluster based on the determined distances comprises:

if a determined distance between the feature vector of the document and a particular cluster centroid is below a predetermined threshold and below the determined distances between the feature vector of the document and the other centroids:

assigning the document to a cluster associated with the particular cluster centroid;

updating the particular cluster centroid based on the feature vector of the document; and

updating the relative age of the particular cluster centroid.

7. The method of claim 1 wherein assigning the document to a cluster based on the determined distances comprises:

if none of the determined distances between the feature vector of the document and the cluster centroids are below a predetermined threshold:

assigning the document to a new cluster;

designating the feature vector of the document as a cluster centroid for the new cluster; and

assigning a relative age to the cluster centroid of the new cluster.

8. The method of claim 1 wherein retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector comprises:

retrieving a set of cluster identifiers from a cluster table, the cluster identifiers each indicative of a respective cluster centroid; and

retrieving the cluster centroids corresponding to the retrieved cluster identifiers from a memory.

9. An apparatus for clustering a plurality of documents from a data stream comprising:

means for generating a feature vector for a document in the plurality of documents;

means for applying a locality sensitive hashing function to the feature vector;

means for retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector;

means for determining a distance between the feature vector of the document and each of the cluster centroids; and

means for assigning the document to a cluster based on the determined distances.

10. The apparatus of claim 9 wherein the feature vector is {right arrow over (d)}=[d 1 , . . . , d T ] and the means for applying a locality sensitive hashing function to the feature vector comprises:

means for calculating entries in a hash value

h

=

∑

i

=

1

K

⁢

min

j

=

1

,

…

⁢

,

T

d

j

>

0

⁢

mod

⁢

⁢

(

a

i

·

j

+

b

i

,

p

i

)

using indices j of non-zero entries of the feature vector and random numbers a i , b i , and p i for i=1, . . . K wherein mod is a function that returns a remainder of an integer division.

11. The apparatus of claim 9 wherein the means for applying a locality sensitive hashing function to the feature vector comprises:

means for hashing the feature vector with a locality sensitive hashing function comprising a series of hashing functions;

means for determining a set of values similar to a set of results of the hashing of the feature vector; and

means for determining a set of cluster identifiers based on the determined set of values.

12. The apparatus of claim 9 wherein the means for retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector further comprises:

means for selecting a group of cluster centroids based on a size of clusters associated with the cluster centroids.

13. The apparatus of claim 9 wherein the means for assigning the document to a cluster based on the determined distances comprises:

means for assigning the document to clusters corresponding to that plurality of cluster centroids;

means for updating the cluster centroids based on the feature vector of the document; and

means for updating the relative ages of the cluster centroids if the determined distances between the feature vector of the document and a plurality of cluster centroids are below a predetermined threshold.

14. The apparatus of claim 9 wherein the means for assigning the document to a cluster based on the determined distances comprises:

means for assigning the document to a cluster associated with the particular cluster centroid;

means for updating the particular cluster centroid based on the feature vector of the document; and

means for updating the relative age of the particular cluster centroid if a determined distance between the feature vector of the document and a particular cluster centroid is below a predetermined threshold and below the determined distances between the feature vector of the document and the other centroids.

15. The apparatus of claim 9 wherein the means for assigning the document to a cluster based on the determined distances comprises:

means for assigning the document to a new cluster;

means for designating the feature vector of the document as a cluster centroid for the new cluster; and

means for assigning a relative age to the cluster centroid of the new cluster if none of the determined distances between the feature vector of the document and the cluster centroids are below a predetermined threshold.

16. The apparatus of claim 9 wherein the means for retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector comprises:

means for retrieving a set of cluster identifiers from a cluster table, the cluster identifiers each indicative of a respective cluster centroid; and

means for retrieving the cluster centroids corresponding to the retrieved cluster identifiers from a memory.

17. A machine readable medium having program instructions stored thereon, the instructions capable of execution by a processor and defining the steps of:

generating a feature vector for a document in a plurality of documents;

applying a locality sensitive hashing function to the feature vector;

retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector;

determining a distance between the feature vector of the document and each of the cluster centroids; and

assigning the document to a cluster based on the determined distances.

18. The machine readable medium of claim 17 , wherein the feature vector is {right arrow over (d)}=[d 1 , . . . , d T ] and the instructions for applying a locality sensitive hashing function to the feature vector comprises wherein the instructions further define the step of:

calculating entries in a hash value

h

=

∑

i

=

1

K

⁢

min

j

=

1

,

…

⁢

,

T

d

j

>

0

⁢

mod

⁢

⁢

(

a

i

·

j

+

b

i

,

p

i

)

using indices j of non-zero entries of the feature vector and random numbers a i , b i , and p i for i=1, . . . K wherein mod is a function that returns a remainder of an integer division.

19. The machine readable medium of claim 17 , wherein the instructions for applying a locality sensitive hashing function to the feature vector further define the steps of:

hashing the feature vector with a locality sensitive hashing function comprising a series of hashing functions;

determining a set of values similar to a set of results of the hashing of the feature vector; and

determining a set of cluster identifiers based on the determined set of values.

20. The machine readable medium of claim 17 , wherein the instructions for retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector further define the step of:

selecting a group of cluster centroids based on a size of clusters associated with the cluster centroids.

21. The machine readable medium of claim 17 , wherein the instructions for assigning the document to a cluster based on the determined distances further define the steps of:

if the determined distances between the feature vector of the document and a plurality of cluster centroids are below a predetermined threshold:

assigning the document to clusters corresponding to that plurality of cluster centroids;

updating the cluster centroids based on the feature vector of the document; and

updating the relative ages of the cluster centroids.

22. The machine readable medium of claim 17 , wherein the instructions for assigning the document to a cluster based on the determined distances further define the steps of:

if a determined distance between the feature vector of the document and a particular cluster centroid is below a predetermined threshold and below the determined distances between the feature vector of the document and the other centroids:

assigning the document to a cluster associated with the particular cluster centroid;

updating the particular cluster centroid based on the feature vector of the document; and

updating the relative age of the particular cluster centroid.

23. The machine readable medium of claim 17 , wherein the instructions for assigning the document to a cluster based on the determined distances further define the steps of:

if none of the determined distances between the feature vector of the document and the cluster centroids are below a predetermined threshold:

assigning the document to a new cluster;

designating the feature vector of the document as a cluster centroid for the new cluster; and

assigning a relative age to the cluster centroid of the new cluster.

24. The machine readable medium of claim 17 , wherein the instructions for retrieving a set of cluster centroids based on a result of the applied locality sensitive hashing function of the feature vector further define the steps of:

retrieving a set of cluster identifiers from a cluster table, the cluster identifiers each indicative of a respective cluster centroid; and

retrieving the cluster centroids corresponding to the retrieved cluster identifiers from a memory.