Patent Document ID: 9626426
Application ID: 14163555
Patent Flag: 1

Claim One:
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.