Computing device and approximate nearest neighbor search method

An ANNs method, for a computing device including a processor, a memory and a storage device, the ANNs method comprising:

• enabling, by the processor, the memory loading a k-means tree index, wherein the k-means tree index is corresponding to a plurality of vectors;
• obtaining, by the processor, a node, with the shortest distance from a query vector, among one or more nodes of each of a plurality of levels, from a root level to a leaf level of the k-means tree, sequentially, until a result node in the leaf level is obtained;
• enabling, by the processor, the memory loading a RNG, corresponding to the result node, of one or more RNGs storing in the storage device;
• obtaining, by the processor, a nearest vector cluster, from a plurality of vector clusters, with the shortest distance from the query vector, and enabling the memory loading a nearest posting list content, corresponding to the nearest vector cluster, of a plurality of posting list contents storing in the storage device;
• and
• using a plurality of full-precision vector contents of the plurality of vectors in the nearest posting list content as a query result and outputting the query result,
• wherein the one or more RNGs are respectively corresponding to the one or more nodes in the leaf level, and the plurality of posting list contents are respectively corresponding to the plurality of vector clusters in each of the one or more RNGs.

A computing device for ANNs, comprising:

• a processor, configured to process a plurality of vectors and generate a space partitioning data, the space partitioning data comprising:
• a k-means tree index, corresponding to the plurality of vectors and including a plurality of levels, from a root level to a leaf level, wherein each of the plurality of levels comprises one or more nodes;
• one or more RNGs, corresponding to the one or more nodes of the leaf level of the k-means tree, each of the one or more RNGs including a plurality of vector clusters;
• and
• a plurality of posting list contents, corresponding to the plurality of vector clusters in each of the one or more RNGs;
• a memory, configured to load the k-means tree;
• and
• a storage device, configured to store the one or more RNGs and the plurality of posting list contents,
• wherein, when the processor executes the ANNs, the processor executes:
• receiving a search instruction including a query vector;
• obtaining a node, with the shortest distance from the query vector, among the one or more nodes of each of the plurality of levels, from the root level to the leaf level of the k-means tree, sequentially, until a result node in the leaf level is obtained;
• enabling the memory loading a RNG, corresponding to the result node, of the one or more RNGs from the storage device;
• obtaining a nearest vector cluster, from the plurality of vector clusters, with the shortest distance from the query vector;
• enabling the memory loading a nearest posting list content, corresponding to the nearest vector cluster, of the plurality of posting list contents from the storage device;
• and
• using a plurality of full-precision vector contents of the plurality of vectors in the nearest posting list content as a query result and outputting the query result.