Approximate k nearest neighbors on hardware accelerators

A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising:

• obtaining a set of one or more query vectors;
• obtaining a set of database vectors, wherein each database vector has a respective index, and wherein the database vectors are partitioned into a plurality of bins based on the indices;
• and
• performing, on a hardware accelerator and for each query vector in the set, a search for the k most similar database vectors to the query vector according to a similarity measure, comprising:
• computing, by circuitry of the hardware accelerator and for each query vector, a respective similarity value between the query vector and each database vector according to the similarity measure;
• and
• for each query vector, identifying, by the hardware accelerator and for each bin, (i) an index of the most similar database vector within the bin and (ii) the respective similarity value for the most similar database vector within the bin.

One or more non-transitory computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

• obtaining a set of one or more query vectors;
• obtaining a set of database vectors, wherein each database vector has a respective index, and wherein the database vectors are partitioned into a plurality of bins based on the indices;
• and
• performing, on a hardware accelerator and for each query vector in the set, a search for the k most similar database vectors to the query vector according to a similarity measure, comprising:
• computing, by circuitry of the hardware accelerator and for each query vector, a respective similarity value between the query vector and each database vector according to the similarity measure;
• and
• for each query vector, identifying, by the hardware accelerator and for each bin, (i) an index of the most similar database vector within the bin and (ii) the respective similarity value for the most similar database vector within the bin.