Data compression for optimized error and efficiency

A method of conducting a nearest neighbor search:

• reading a first vector belonging to an unsorted vector space;
• generating, based on the first vector, a first sorted vector belonging to a sorted vector space, the sorted vector space comprising a plurality of sorted vectors, wherein generating the first sorted vector comprises generating a first permutation vector indicating a position of each element of the first sorted vector in the first vector;
• determining, for each sorted vector of the plurality of sorted vectors, a first distance between the first sorted vector and that sorted vector;
• selecting a subset of the plurality of sorted vectors based on the first distance between the first sorted vector and each sorted vector;
• generating, for each sorted vector of the subset, a projected vector based on the first permutation vector and that sorted vector, each projected vector belonging to the unsorted vector space;
• determining, for each sorted vector of the subset, a second distance between the first vector and the projected vector for that sorted vector;
• selecting a nearest sorted vector from the subset based on the second distances;
• and
• providing the nearest sorted vector.

A computer program product comprising:

• one or more computer-readable storage media;
• and
• program instructions stored on the one or more computer-readable storage media to perform operations comprising:
• reading a first vector belonging to an unsorted vector space;
• generating, based on the first vector, a first sorted vector belonging to a sorted vector space, the sorted vector space comprising a plurality of codewords, wherein generating the first sorted vector comprises generating a first permutation vector indicating a position of each element of the first sorted vector in the first vector;
• determining a distance between the first sorted vector and each codeword of the plurality of codewords;
• selecting a nearest codeword from the plurality of codewords based on the distances;
• and
• providing a compressed representation of the first vector, the compressed representation comprising an identification of the nearest codeword and the first permutation vector.

A computer system comprising:

• a processor set;
• one or more computer-readable storage media;
• and
• program instructions stored on the one or more computer-readable storage media to perform operations comprising:
• reading a first vector belonging to an unsorted vector space;
• generating, based on the first vector, a first sorted vector belonging to a sorted vector space, the sorted vector space comprising a plurality of codewords, wherein generating the first sorted vector comprises generating a first permutation vector indicating a position of each element of the first sorted vector in the first vector;
• determining a distance between the first sorted vector and each codeword of the plurality of codewords;
• selecting a nearest codeword from the plurality of codewords based on the distances;
• and
• providing a compressed representation of the first vector, the compressed representation comprising an identification of the nearest codeword and the first permutation vector.