Smaller Proximate Search Index

Abstract

A data management system accesses a set of vectors containing binary values and generates vector blocks comprising binary values from each vector. Each of at least a portion of the vector blocks for each vector contain a set of two or more binary values from the vector. The data management system generates a block index based on the vector blocks. The block index includes a set of vector block arrays, each vector block array corresponding to a position in the vectors and including the binary values of a vector block from each vector. The data management system can identify relevant vectors for a target vector by generating vector blocks from the target vector and querying the block index to identify candidate vectors.

The invention claimed is: 
     
         1 . A computer-implemented method comprising:
 accessing a set of vectors, each vector comprising binary values;   for each vector from the set of vectors, generating a set of vector blocks with each vector block corresponding with a position in the vector and each of at least a portion of the vector blocks comprising two or more of the binary values from the vector; and   generating, using one or more processors, a block index having a set of block arrays with each vector block array identifying, for a corresponding position in the vectors, binary values of the vector block from the corresponding position for each vector.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein accessing the set of vectors comprises:
 accessing a set of floating value vectors; and   converting floating values in the floating values vectors to binary values to provide the set of vectors.   
     
     
         3 . The computer-implemented method of  claim 1 , wherein generating the set of vector blocks for each vector comprises assigning a vector identifier for the vector to each vector block for the vector. 
     
     
         4 . The computer-implemented method of  claim 1 , wherein generating the block index comprises:
 for a first vector block array corresponding with a first position in the vectors, storing a vector block from the first corresponding position for each vector from the set of vectors.   
     
     
         5 . The computer-implemented method of  claim 4 , wherein generating the block index further comprises:
 ordering the vector blocks in the first vector block array based on binary values of the vector blocks.   
     
     
         6 . The computer-implemented method of  claim 5 , wherein generating the block index further comprises:
 encoding binary values of a first vector block in the first vector block array by representing the binary values of the first vector block based on a difference between the binary values of the first vector block and the binary values of a previous vector block in the first vector block array.   
     
     
         7 . The computer-implemented method of  claim 4 , wherein generating the block index further comprises:
 consolidating one or more vector blocks in the first vector block array that include same binary values.   
     
     
         8 . The computer-implemented method of  claim 7 , wherein generating the block index further comprises:
 encoding vector identifiers of vectors for each consolidated vector block by representing at least one vector identifier based on a change from a previous vector identifier in the consolidated vector block.   
     
     
         9 . The computer-implemented method of  claim 1 , wherein the method further comprises:
 receiving a target vector comprising binary values;   identifying, using the block index, a set of candidate vectors based on a hamming distance between the target vector and each candidate vector from the set of candidate vectors; and   determining, from the set of candidate vectors, a set of one or more result vectors.   
     
     
         10 . The computer-implemented method of  claim 1 , wherein each vector corresponds to a data object represented by a respective vector. 
     
     
         11 . A non-transitory computer-readable medium storing instructions that, when executed by one or more computer processors of a computing system, cause the computing system to perform operations comprising:
 receiving a target vector comprising binary values;   accessing a block index storing data for a set of vectors, each vector from the set of vectors comprising binary values, the block index comprising a set of vector block arrays with each vector block array being associated with a corresponding position in the vectors and identifying binary values of a vector block from the corresponding position for each vector, each at least a portion of the vectors blocks comprising two or more binary values from each vector; and   identifying, using the block index, a set of candidate vectors based on a distance between the target vector and each candidate vector from the set of candidate vectors.   
     
     
         12 . The non-transitory computer-readable medium of  claim 11 , wherein receiving the target vector comprises:
 receiving a data object;   converting the data object to a floating value vector; and   converting floating values in the floating value vector to binary values to provide the target vector.   
     
     
         13 . The non-transitory computer-readable medium of  claim 11 , wherein identifying the set of candidate vectors comprises:
 generating a set of vectors blocks for the target vector based on the corresponding positions associated with the vector block arrays in the block index; and   searching the block index by comparing binary values of each vector block from the target vector to binary values for the set of vectors identified by each vector block array.   
     
     
         14 . The non-transitory computer-readable medium of  claim 11 , wherein the distance between the target vector and each candidate vector comprises a hamming distance. 
     
     
         15 . The non-transitory computer-readable medium of  claim 14 , wherein identifying the set of candidate vectors comprises:
 determining a hamming distance for each vector from the set of vectors; and   comparing the hamming distance for each vector from the set of vectors to a distance threshold.   
     
     
         16 . The non-transitory computer-readable medium of  claim 11 , wherein the operations further comprise:
 selecting, from the set of candidate vectors, one or more result vectors.   
     
     
         17 . The non-transitory computer-readable medium of  claim 16 , wherein selecting the one or more result vectors comprises:
 determining a distance between a floating value vector for the target vector and a floating value vector for each candidate vector; and   selecting the one or more result vectors based on the determined distances.   
     
     
         18 . A system comprising:
 one or more processors; and   one or more computer-readable media storing instructions, that when used by the one or more processors, cause the one or more processors to:   generating a block index from a set of vectors comprising binary values by generating a set of vector blocks for each vector from the set of vectors and indexing data in the block index based on the vector blocks, the block index comprising a set of vector block arrays with each vector block array being associated with a corresponding position in the vectors and identifying binary values of a vector block from the corresponding position for each vector, each at least a portion of the vectors blocks comprising two or more binary values from each vector;   receiving a target vector comprising binary values;   generating target vector blocks from the target vector;   identifying one or more candidate vectors by searching the vector block arrays of the block index using binary values of each target vector block; and   selecting one or more result vectors from the candidate vectors.   
     
     
         19 . The system of  claim 18 , wherein identifying the one or more candidate vectors comprises:
 computing a hamming distance between the target vector and each vector; and   comparing the hamming distance for each vector to a threshold.   
     
     
         20 . The system of  claim 18 , wherein selecting the one or more result vectors comprises:
 determining a distance between a floating value vector for the target vector and a floating value vector for each candidate vector; and   selecting the one or more result vectors based on the distances.