Granted Patent B2

US 12,346,321 · App. 17/718,983 · Granted Jul 1, 2025

Inventors: Song Xu (Shanghai, CN); Lanxin Zhang (Shanghai, CN); Yufeng Qu (Shanghai, CN); Chunyi Li (Shanghai, CN)

Assignee: MONTAGE TECHNOLOGY CO., LTD.

G06F16/24542G06F16/24539

Abstract

Claims (37)

1. A method for querying in a candidate vector set candidate vectors similar to object vectors, wherein the candidate vector set comprises a plurality of candidate vectors each being quantized as having a central vector portion and a residual vector portion, and the candidate vector set comprises a plurality of candidate vector subsets, the method comprising:

acquiring a set of object vectors;

querying, for each object vector of the set of object vectors, a first number of candidate vector subsets that are closest to the object vector;

generating and storing a plurality of common calculation results in a cache based on a set of central vector portions and a set of residual vector portions of candidate vectors of the first number of candidate vector subsets;

generating and storing pre-calculation results as a pre-calculation result table in the form of a look-up table based on the set of object vectors and the set of residual vector portion; and

determining, for each object vector of the set of object vectors, a second number of candidate vectors that are similar to the object vector among the candidate vectors in the corresponding first number of candidate vector subsets based on the stored pre-calculation results and common calculation results,

wherein generating the plurality of common calculation results is performed offline and generating the pre-calculation results is performed online;

wherein each of the central vector portions, the residual vector portions and the object vectors are divided into M segments using IVF-PQ algorithm, wherein M is a natural number greater than 1, and a common calculation result is expressed as: (xq−C i ) 2 +(pq_centroids(k,l)) 2 +2*(C i |pq_centroids(k,l)), wherein xq denotes an object vector, and pq_centroids (k, l) denotes a residual vector portions, 1 denotes an 1-th segment of a residual vector portion, 1=1 . . . M, and k denotes a quantized value of the 1-th segment of a residual vector portion; Ci denotes the i-th central vector portion associated with a candidate vector, and i is a natural number; and

wherein a pre-calculation result is expressed as: −2(xq|pq_centroids(k,l)).

2. The method according to claim 1 , wherein the step for determining, for each object vector of the set of object vectors, a second number of candidate vectors that are similar to the object vector among the candidate vectors in the corresponding first number of candidate vector subsets based on the stored pre-calculation results and common calculation results comprises:

calculating, for each object vector, respective distances between the object vector and the candidate vectors in the corresponding first number of candidate vector subsets; and

sorting the candidate vectors based on the calculated distances, to determine a second number of candidate vectors that are closest to the object vector as the second number of candidate vectors that are similar to the object vector.

3. A similarity query apparatus for querying in a candidate vector set candidate vectors similar to object vectors, wherein the candidate vector set comprises a plurality of candidate vectors each being quantized as having a central vector portion and a residual vector portion, and the candidate vector set comprises a plurality of candidate vector subsets, the similarity query apparatus comprising:

a calculation module for calculating respective distances between an object vector and the plurality of candidate vectors subsets, and for calculating respective similarities between candidate vectors and an object vector; and

a sorting module for sorting the distances between an object vector and the plurality of candidate vector subsets, and for sorting the similarities between candidate vectors and an object vector;

wherein the calculation module performs the calculating of distances and similarities through the following steps:

acquiring a set of object vectors; and

for each object vector of the set of object vectors:

calculating respective distances between the object vector and the candidate vector subsets and providing the distances to the sorting module;

generating and storing a plurality of common calculation results in a cache based on a set of central vector portions and a set of residual vector portions of the candidate vectors of a first number of candidate vector subsets that are closest to the object vector;

generating and storing pre-calculation results as a pre-calculation result table in the form of a look-up table based on the set of object vectors and the set of residual vector portions; and

determining a second number of candidate vectors that are similar to the object vector among the candidate vectors in the corresponding first number of candidate vector subsets based on the stored pre-calculation results and common calculation results;

wherein generating the plurality of common calculation results is performed offline and generating the pre-calculation results is performed online;

wherein each of the T, the residual vector portions and the object vectors are divided into M segments using IVF-PQ algorithm, wherein M is a natural number greater than 1, and a common calculation result is expressed as: (xq−C i ) 2 +(pq_centroids(k,l)) 2 +2*(C i |pq_centroids(k,l)), wherein xq denotes an object vector, and pq_centroids (k, l) denotes a residual vector portions, 1 denotes an 1-th segment of a residual vector portion, 1=1 . . . M, and k denotes a quantized value of the 1-th segment of a residual vector portion; Ci denotes the i-th central vector portion associated with a candidate vector, and i is a natural number; and

wherein a pre-calculation result is expressed as: −2(xq|pq_centroids(k,l)).

4. The apparatus according to claim 3 , wherein the calculation module comprises:

a calculation processor for performing calculation on data received by the calculation module; and

a decoding calculator for receiving and storing the pre-calculation results calculated by the calculation processor, searching for corresponding pre-calculation results in response to a decoding query request, calculating respective distances between an object vector and candidate vectors based on the pre-calculation results and the common calculation results, and determining the distances as similarity calculation results for the candidate vectors.

5. The apparatus according to claim 4 , wherein the decoding calculator comprises one or more decoding threads, and each of the decoding threads comprises:

a cache for caching data;

a plurality of lookup tables for storing respective pre-calculation results corresponding to the object vectors; and

an add tree for summing data.

6. The apparatus according to claim 3 , wherein the sorting module comprises:

a plurality of data queues, a plurality of sorting networks, and a plurality of merging networks, wherein each data queue is coupled in series with a sorting network and merging network for sorting similarity calculation results received thereby.

7. The apparatus according to claim 6 , wherein the sorting module comprises:

a plurality of data multiplexers each being configured for selectively coupling an output of a merging network to an input of another merging network to merge similarity calculation results of the two merging networks.

8. The apparatus according to claim 7 , wherein each merging network is further coupled to the calculation module to provide the first number of candidate vector subsets that are closest to the object vector.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (9)