Clustering using locality-sensitive hashing with improved cost model

1. A computer-implemented method of clustering a set of query vectors into K clusters using locality-sensitive hashing (LSH), wherein the LSH is parameterized by a number of projections m, a quantization factor w, and a number of repetitions L and hashes a vector to a collection of buckets, comprising:

grouping the set of query vectors into K clusters; and

iterating the following steps until a termination condition is reached:

computing centroids of the K clusters; and

assigning each query vector of the set of query vectors to one of the K clusters with a nearest centroid using the LSH over the query vector and the K centroids, wherein the assigning comprises:

hashing each of the K centroids using the LSH into the collection of buckets; and

for each of the query vectors:

hashing the query vector using the LSH into the collection of buckets;

identifying the nearest centroid in the collection of the buckets to which the query vector is hashed; and

assigning the query vector to the cluster with the nearest centroid.

2. The computer-implemented method of claim 1 , further comprising:

re-computing parameters of the LSH over the set of query vectors and the set of K centroids before the use of the LSH in each iteration,

wherein the LSH is then used with the re-computed parameters.

3. The computer-implemented method of claim 2 , wherein setting parameters of the LSH is performed by:

for every value of m and every value of w:

computing a hit probability that a query data vector and its nearest data vector hash to the same bucket when the LSH is run with one projection and one repetition; and

computing a value of L that limits a classification error associated with executing the LSH to a predetermined error probability based on the hit probability; and

computing a value of a cost associated with executing the LSH on a query vector and the set of data vectors; and

outputting the computed values of w, m and L that minimize the value of the cost.

4. The computer-implemented method of claim 3 , wherein computing the hit probability comprises:

hashing each of the K centroids and each of a random subset of the set of query vectors using the LSH with one projection, the current value of w and one repetition; and

determining a percentage of the query vectors in the random subset, each of which is hashed to the same bucket as the centroid of the cluster to which the query vector currently belongs.

5. The computer-implemented method of claim 3 , wherein the value of the cost is computed by:

computing a first cost of hashing the query vector into a collection of buckets based on m;

computing a second cost of searching the data vectors in the union of the buckets based on L; and

determining a sum of the first cost and the second cost.

6. The computer-implemented method of claim 5 , wherein the second cost is proportional to an expected number of the data vectors that are hashed to a bucket to which the query vector is hashed, and computing the expected number comprises:

hashing each of the K centroids and each of a random subset of the set of query vectors using the LSH with the current values of m, w and L; and

determining the average number of the centroids hashed to the same bucket as one of the query vectors in the random subset.

7. The computer-implemented method of claim 6 , wherein

the hashing is performed by a number of processors, each performance involving a distinct subset of the set of query vectors, and

the determining is performed over the union of the distinct subsets of the set of query vectors.

8. The computer-implemented method of claim 1 , further comprising the step of reducing an upper bound for a classification error associated with executing the LSH in each iteration.

9. The computer-implemented method of claim 1 , wherein the identifying includes computing a distance between the query vector and every centroid in the union of the buckets.

10. A system for clustering a set of query vectors into K clusters using locality-sensitive hashing (LSH), wherein the LSH hashes a vector to a collection of buckets, comprising:

a component configured to group the set of query vectors into K clusters; and

a component configured to iterate the following steps until a termination condition is reached:

compute centroids of the K clusters; and

assign each of the query vectors to one of the K clusters with a nearest centroid using the LSH over the query vector and the set of K centroids, wherein the component is configured to assign by:

hashing each of the K centroids using the LSH into the collection of buckets; and

for each of the query vectors:

hashing the query vector using the LSH into the collection of buckets;

identifying the nearest centroid in the collection of the buckets to which the query vector is hashed; and

assigning the query vector to the cluster with the nearest centroid.

11. The system of claim 10 , further comprising:

a component configured to re-compute parameters of the LSH over the set of query vectors and the set of K centroids before the use of the LSH in each iteration,

wherein the LSH is then used with the re-computed parameters.

12. The system of claim 10 , further comprising a component configured to reduce an upper bound for a classification error associated with executing the LSH in each iteration.

13. The system of claim 10 , wherein the identifying includes computing a distance between the query vector and every centroid in the union of the buckets.

14. A non-transitory computer-readable storage medium storing computer-readable instructions for clustering a set of query vectors into K clusters using locality-sensitive hashing (LSH), wherein the LSH is parameterized by a number of projections m, a quantization factor w, and a number of repetitions L and hashes a vector to a collection of buckets, comprising:

instructions for grouping the set of query vectors into K clusters; and

instructions for iterating the following steps until a termination condition is reached:

instructions for computing centroids of the K clusters; and

instructions for assigning each query vector of the set of query vectors to one of the K clusters with a nearest centroid using the LSH over the query vector and the K centroids, wherein the assigning comprises:

hashing each of the K centroids using the LSH into the collection of buckets; and

for each of the query vectors:

hashing the query vector using the LSH into the collection of buckets;

identifying the nearest centroid in the collection of the buckets to which the query vector is hashed; and

assigning the query vector to the cluster with the nearest centroid.

15. The non-transitory computer-readable storage medium of claim 14 further comprising:

instructions for re-computing parameters of the LSH over the set of query vectors and the set of K centroids before the use of the LSH in each iteration, wherein the LSH is then used with the re-computed parameters.

16. The non-transitory computer-readable storage medium of claim 14 further comprising:

instructions for reducing an upper bound for a classification error associated with executing the LSH in each iteration.