CN-122019538-A - Vector query method and device

CN122019538ACN 122019538 ACN122019538 ACN 122019538ACN-122019538-A

Abstract

A vector query method and device comprises the steps of mapping a received query vector to a low-dimensional projection space to obtain a projection query point, obtaining an index tree with a plurality of subtrees and leaf nodes of the pre-built root node for storing data points in the low-dimensional projection space, wherein each node of the index tree corresponds to one area in the low-dimensional projection space, the area corresponding to the child node in the index tree is contained in the area corresponding to a father node, distributing the plurality of subtrees to a plurality of processing units, and executing range query on the distributed subtrees by each processing unit, wherein the method comprises the steps of traversing the nodes of the subtrees, pruning the subtrees of the non-leaf nodes if the lower limit of the distance between the corresponding area and the projection query point is larger than a preset search radius, and adding the data points contained in the first leaf nodes in the subtrees into a local candidate set for determining query results if the lower limit of the distance between the corresponding area and the projection query point is larger than the search radius.

Inventors

WEI JIUQI
XU QUANQING
YANG CHUANHUI

Assignees

北京奥星贝斯科技有限公司

Dates

Publication Date: 20260512
Application Date: 20260120

Claims (14)

1. A vector query method, comprising: obtaining a pre-constructed index tree, wherein each node of the index tree corresponds to one area in the low-dimensional projection space, the area corresponding to a child node of any father node in the index tree is contained in the area corresponding to the father node, leaf nodes of the index tree are used for storing data points in the low-dimensional projection space, and a root node of the index tree is provided with a plurality of subtrees; The method comprises the steps of distributing a plurality of subtrees to a plurality of processing units, and executing range query on the distributed subtrees by each processing unit, wherein the range query comprises traversing nodes of the subtrees, pruning the subtrees of non-leaf nodes if the lower limit of the distance between the area corresponding to the non-leaf nodes and the projection query point is larger than a preset search radius for the non-leaf nodes in the subtrees, and adding data points contained in the first leaf nodes into a local candidate set corresponding to the subtrees if the lower limit of the distance between the area corresponding to the first leaf nodes and the projection query point is larger than the search radius for the first leaf nodes in the subtrees, wherein the local candidate set is used for determining query results corresponding to the query vectors.
2. The method of claim 1, further comprising: Determining the actual distance between each data point in the total candidate set and the query vector in the original high-dimensional space, sorting each data point in the total candidate set according to the actual distance, and determining at least one data point as the query result according to the sorting result.
3. The method of claim 2, wherein obtaining pre-constructed index trees whose root nodes correspond to low-dimensional projection spaces comprises obtaining L pre-constructed index trees, wherein L is an integer greater than or equal to 2, the root node of each index tree corresponding to one low-dimensional projection space, each index tree having a plurality of sub-trees, each sub-tree corresponding to one axis-aligned hyper-rectangular region in the low-dimensional projection space; The method comprises the steps of assigning the plurality of subtrees to the plurality of processing units, and executing range query on the assigned subtrees by each processing unit, wherein the range query comprises traversing nodes of the subtrees, pruning the subtrees of non-leaf nodes if the lower limit of the distance between the area corresponding to the non-leaf node and the projection query point is larger than a preset search radius for the non-leaf nodes in the subtrees, and adding data points contained in the first leaf nodes into a local candidate set corresponding to the subtrees if the lower limit of the distance between the area corresponding to the first leaf node and the projection query point is larger than the search radius for the first leaf nodes in the subtrees, wherein the method comprises the following steps: For any index tree, a plurality of subtrees of the index tree are distributed to the plurality of processing units, each processing unit executes range query on the distributed subtrees, and the range query comprises traversing nodes of the subtrees, pruning subtrees of non-leaf nodes if the lower limit of the distance between the area corresponding to the non-leaf nodes and the projection query point is larger than a preset search radius for the non-leaf nodes in the subtrees; Determining the actual distance between each data point in the total candidate set and the query vector in the original high-dimensional space, and determining at least one data point in the merging candidate set as a query result according to the actual distance, wherein the method comprises the following steps: and determining the actual distance between each data point in the total candidate set and the query vector in the original high-dimensional space, and determining at least one data point in the total candidate set as a query result according to the actual distance.
4. The method of claim 2, wherein adding the data points contained by the first leaf node to the corresponding local candidate set of the subtree comprises: Randomly inserting a first leaf node into one node storage queue of a plurality of node storage queues constructed in advance, wherein data points contained in nodes in the node storage queue are used for determining a query result corresponding to the query vector; merging the local candidate sets corresponding to all subtrees to obtain a total candidate set, wherein the method comprises the following steps: and obtaining a total candidate set according to the data points contained in the nodes of the plurality of node storage queues.
5. The method of claim 1, wherein the number of subtrees of the root node of the index tree is greater than or equal to 2 and less than or equal to 2 to the power of K, K being the number of dimensions of the low-dimensional projection space.
6. The method of claim 1, wherein mapping the query vector to a low-dimensional projection space results in a projected query point, comprising: and mapping the query vector in the original high-dimensional space to a low-dimensional projection space through a preset Hash projection matrix to obtain a projection query point.
7. The method of claim 1, wherein the region is an axis-aligned hyper-rectangular region; The lower distance boundary between the area corresponding to the non-leaf node and the projection query point comprises the Euclidean distance lower boundary between the hyper-rectangular area aligned with the axis corresponding to the non-leaf node and the projection query point; the lower distance boundary between the area corresponding to the first leaf node and the projection query point comprises the Euclidean distance lower boundary between the hyper-rectangular area corresponding to the first leaf node and the projection query point.
8. The method of claim 1, wherein the index tree is constructed by: acquiring a plurality of high-dimensional data, and mapping the plurality of high-dimensional data to a low-dimensional projection space to obtain a plurality of projection points; Determining a plurality of break points of each dimension of the low-dimensional projection space based on the coordinate distribution of all projection points in the dimension, dividing the dimension into a plurality of non-overlapping intervals according to the break points, determining a symbol corresponding to each interval of each dimension, and generating codes of the projection points according to the symbols corresponding to the intervals of the projection points in each dimension for each projection point in the plurality of projection points; The method comprises the steps of constructing an index tree, generating K first layer nodes of 2 below a root node of the index tree to serve as initial leaf nodes, determining a corresponding target leaf node of a projection point in the index tree according to codes of the projection point for each projection point in the plurality of projection points, inserting the projection point into the target leaf node, and if the number of the projection points of the target leaf node reaches a preset leaf node size threshold, binary splitting the target leaf node based on the target dimension determined from K dimensions of the low-dimensional projection space.
9. The method of claim 8, wherein for each dimension of the low-dimensional projection space, determining a plurality of break points for the dimension based on a coordinate distribution of all projection points across the dimension comprises: all dimensions of the low-dimensional projection space are divided into a plurality of dimension subsets each comprising a plurality of dimensions, the plurality of dimension subsets are allocated to a plurality of processing units, each processing unit being configured to determine a breakpoint of a dimension comprised in the allocated dimension subset.
10. The method of claim 8, wherein for each of the plurality of proxels, determining its target leaf node in the index tree and inserting the target leaf node according to the encoding of the proxel, if the number of proxels of the target leaf node reaches a preset leaf node size threshold, binary splitting the target leaf node based on a target dimension determined from K dimensions of a low-dimensional projection space, comprising: dividing all the projection points into a plurality of projection point subsets which respectively comprise a plurality of projection points, determining a corresponding target leaf node of the projection points in the index tree according to the codes of the projection points for each projection point in the allocated projection point subsets by each processing unit, inserting the projection points into the target leaf node, and if the number of the projection points of the target leaf node reaches a preset leaf node size threshold, binary splitting the target leaf node based on a target dimension determined from K dimensions of a low-dimensional projection space.
11. The method of claim 1, wherein determining the plurality of break points for the dimension based on the coordinate distribution of all proxels over the dimension comprises determining the plurality of break points for the dimension based on the coordinate distribution of all proxels over the dimension by a quick selection algorithm.
12. A vector query apparatus, comprising: The acquisition unit is configured to receive a query vector, map the query vector to a low-dimensional projection space and obtain a projection query point, acquire a pre-constructed index tree, wherein each node of the index tree corresponds to one region in the low-dimensional projection space, the region corresponding to a child node of any father node in the index tree is contained in the region corresponding to the father node, leaf nodes of the index tree are used for storing data points in the low-dimensional projection space, and a root node of the index tree is provided with a plurality of subtrees; The processing unit is configured to allocate the plurality of subtrees to the plurality of processing units, each processing unit executes range query on the allocated subtrees, the range query comprises traversing nodes of the subtrees, pruning subtrees of non-leaf nodes if the lower limit of the distance between the area corresponding to the non-leaf nodes and the projection query point is larger than a preset search radius for the non-leaf nodes in the subtrees, and adding data points contained in the first leaf nodes into local candidate sets corresponding to the subtrees if the lower limit of the distance between the area corresponding to the first leaf nodes and the projection query point is larger than the search radius for the first leaf nodes in the subtrees, wherein the local candidate sets are used for determining query results corresponding to the query vectors.
13. A computer readable storage medium having stored thereon a computer program which, when executed in a computer, causes the computer to perform the method of any of claims 1-11.
14. A computing device comprising a memory having executable code stored therein and a processor, which when executing the executable code, implements the method of any of claims 1-11.

Description

Vector query method and device Technical Field One or more embodiments of the present disclosure relate to the field of code compiling and trusted computing technology, and in particular, to a method and apparatus for querying a vector. Background The retrieval of the vectorized data (Vectorized Data) is a key technology in the field of artificial intelligence, and is widely applied to application scenes of artificial intelligence technologies such as intelligent search, question-answering systems, retrieval enhancement generation, multi-modal search and the like. The approximate nearest neighbor search (Approximate Nearest Neighbor Search) based on the local sensitive hash (‌ Locality-SENSITIVE HASHING, LSH ‌) is a commonly used vectorized data retrieval scheme, and the scheme has a high application rate due to high search efficiency and low calculation cost. However, the existing scheme of approximate nearest neighbor search based on locality sensitive hashing also has the problem that the parallelization computing capability of modern hardware cannot be fully utilized in the process of constructing an index for vector data and retrieving the vector data, and further, the problem of higher performance cannot be achieved in a parallelized hardware execution environment. Disclosure of Invention Embodiments in the present specification aim to provide a vector query method and apparatus, which greatly improve the speed of vector query and solve the deficiencies of the prior art by performing multiple parallel queries on an index tree of a vector projection space through the parallel processing characteristics of multiple processing units in a modern computer system. According to a first aspect, there is provided a vector query method, comprising: obtaining a pre-constructed index tree, wherein each node of the index tree corresponds to one area in the low-dimensional projection space, the area corresponding to a child node of any father node in the index tree is contained in the area corresponding to the father node, leaf nodes of the index tree are used for storing data points in the low-dimensional projection space, and a root node of the index tree is provided with a plurality of subtrees; The method comprises the steps of distributing a plurality of subtrees to a plurality of processing units, and executing range query on the distributed subtrees by each processing unit, wherein the range query comprises traversing nodes of the subtrees, pruning the subtrees of non-leaf nodes if the lower limit of the distance between the area corresponding to the non-leaf nodes and the projection query point is larger than a preset search radius for the non-leaf nodes in the subtrees, and adding data points contained in the first leaf nodes into a local candidate set corresponding to the subtrees if the lower limit of the distance between the area corresponding to the first leaf nodes and the projection query point is larger than the search radius for the first leaf nodes in the subtrees, wherein the local candidate set is used for determining query results corresponding to the query vectors. In one possible embodiment, the method further comprises: Determining the actual distance between each data point in the total candidate set and the query vector in the original high-dimensional space, sorting each data point in the total candidate set according to the actual distance, and determining at least one data point as the query result according to the sorting result. In one possible implementation, obtaining pre-constructed index trees, the root nodes of which correspond to low-dimensional projection spaces, comprises obtaining L pre-constructed index trees, wherein L is an integer greater than or equal to 2, the root node of each index tree corresponds to one low-dimensional projection space, each index tree has a plurality of subtrees, and each subtree corresponds to one axis alignment hyper-rectangular area in the low-dimensional projection space; The method comprises the steps of assigning the plurality of subtrees to the plurality of processing units, and executing range query on the assigned subtrees by each processing unit, wherein the range query comprises traversing nodes of the subtrees, pruning the subtrees of non-leaf nodes if the lower limit of the distance between the area corresponding to the non-leaf node and the projection query point is larger than a preset search radius for the non-leaf nodes in the subtrees, and adding data points contained in the first leaf nodes into a local candidate set corresponding to the subtrees if the lower limit of the distance between the area corresponding to the first leaf node and the projection query point is larger than the search radius for the first leaf nodes in the subtrees, wherein the method comprises the following steps: For any index tree, a plurality of subtrees of the index tree are distributed to the plurality of processing units, each processing unit executes