CN115129949A - Vector range retrieval method, device, equipment, medium and program product - Google Patents

Abstract

The application relates to the field of data retrieval, and discloses a vector range retrieval method, a device, equipment, a medium and a program product. The vector range retrieval method comprises the following steps: acquiring a query vector and a retrieval radius; loading the graph index and the compressed vector from a first storage area with slow read/write speed to a second storage area with fast read/write speed; determining a target representative vector closest to the query vector in the graph index according to the query vector and the retrieval radius in the second storage area; acquiring a compressed vector corresponding to the target representative vector in a second storage area, and determining the target compressed vector according to the distance between the query vector and the compressed vector; and acquiring an original vector corresponding to the target compressed backward vector from the first storage area according to the target compressed vector, and determining the target original vector according to the distance between the query vector and the original vector, so that the speed and efficiency of vector range retrieval can be improved, and the accuracy of vector range retrieval is improved.

Description

Method, apparatus, apparatus, medium and program product for vector range retrieval

technical field

The present application relates to the field of data retrieval, and in particular, to a method, apparatus, device, medium and program product for vector range retrieval.

Background technique

At present, information retrieval technology is widely used in image retrieval, machine learning, data mining and other fields. By abstracting information into high-dimensional feature vectors, the similarity between information can be quantified as the distance between feature vectors, and information retrieval can be transformed into Nearest Neighbor Search (NNS) in vector space.

Since the performance of the nearest neighbor retrieval algorithm will drop sharply in the massive and high-dimensional vector retrieval scenarios, Approximate Nearest Neighbor Search (ANNS) is usually used as an alternative algorithm. Approximate nearest neighbor retrieval can be accurate within an acceptable range. Under the loss of degree, multiple result vectors similar to the query vector are quickly obtained.

Approximate nearest neighbor retrieval can be divided into KNN retrieval and range retrieval. KNN retrieval fixedly returns K result vectors that are closest to the query vector. The distance retrieves all vectors within the radius, and the range retrieval returns an indeterminate number of result vectors.

The existing range retrieval methods are usually implemented by increasing the K value on the basis of KNN, that is, increasing the number of returned result vectors. Since the number of result vectors obtained by different retrievals varies greatly, it is difficult to determine a fixed range for range retrieval. If you set a smaller K value, when the number of result vectors is greater than the K value, the returned result will be incomplete, which will reduce the accuracy. If you set a larger K value, although a more complete result can be obtained However, when the number of result vectors is small or even zero, a lot of retrieval time will be wasted, resulting in lower retrieval efficiency.

SUMMARY OF THE INVENTION

The embodiments of the present application provide a method, apparatus, device, medium and program product for vector range retrieval, which are used to solve the problems of incomplete retrieval results or low retrieval efficiency when performing vector range retrieval in the prior art.

In a first aspect, an embodiment of the present application provides a vector range retrieval method, which is used in an electronic device, and the method includes:

Get the query vector and retrieval radius;

Load the graph index and the compressed vector from the first storage area to the second storage area, and the read/write speed of the first storage area is lower than that of the second storage area;

In the second storage area, at least one target representative vector whose distance is closest to the query vector in the graph index is determined according to at least the query vector and the retrieval radius;

Obtain a compressed vector corresponding to at least one target representative vector in the second storage area, and determine the target compressed vector at least according to the distance between the query vector and the compressed vector;

According to the target compressed vector, the original vector corresponding to the target compressed vector is obtained from the first storage area, and the target original vector is determined according to the distance between the query vector and the original vector.

It can be understood that the usual method of vector range retrieval can only be realized by increasing the number of result vectors, and there are problems that the returned results are incomplete or the retrieval efficiency is low. However, through the vector range retrieval solution of the present application, a solution with complete returned results and high retrieval efficiency can be realized, avoiding the shortcomings of the existing solution.

In a possible implementation of the above-mentioned first aspect, at least one target representative vector in the graph index with the closest distance to the query vector is determined according to at least the query vector and the retrieval radius, including:

Determine the query vector and retrieval radius, and further determine the maximum radius of the vector data set;

The representative vector in the graph index is obtained in a breadth-first manner, and at least one target representative vector whose distance from the query vector is smaller than the sum of the retrieval radius and the maximum radius of the vector dataset is determined.

Through the above method, all representative vectors including possible retrieval results can be determined as target representative vectors, so as to avoid omission of possible retrieval results due to insufficient number of target representative vectors.

In a possible implementation of the above first aspect, the target compressed vector is determined at least according to the distance between the query vector and the compressed vector, including:

Calculate the product quantized distance between the query vector and the compressed vector;

Determines the target compressed vector whose product quantization distance is less than a preset multiple of the retrieval radius.

Through the above method, the storage space occupied by the compressed vector can be reduced, and a distance calculation method with little increase in computational complexity is provided, and the information loss after compression of the original vector can be determined according to practical experience, thereby improving the range retrieval accuracy.

In a possible implementation of the above first aspect, the target original vector is determined according to the distance between the query vector and the original vector, including:

Calculate the distance between the query vector and the original vector;

Determines the target original vector whose distance is less than the retrieval radius.

Through the above method, the retrieval result is directly determined according to the query vector and the retrieval radius, which can improve the accuracy of the retrieval result.

In a possible implementation of the above-mentioned first aspect, the method further includes:

Returns the destination original vector to the second storage area.

In a possible implementation of the above-mentioned first aspect, the target original vector is returned, including:

Convert the target raw vector to unstructured data and return unstructured data.

Through the above method, a vector that is not easy for users to understand can be converted into unstructured data such as text, video, and audio that are easy for users to understand, which is convenient for users to read or recognize, and can improve user experience.

The embodiment of the present application provides a method for vector range retrieval of electronic devices. The method obtains a query vector and a retrieval radius, and loads the graph index and the compressed vector from the first storage area with slow read/write speed to the read/write speed. / The second storage area with fast writing speed, then determine the target representative vector in the graph index with the closest distance to the query vector in the second storage area according to the query vector and the retrieval radius, and obtain the corresponding target representative vector in the second storage area. The compressed vector, and then determine the target compressed vector according to the distance between the query vector and the compressed vector, and finally obtain the original vector corresponding to the target compressed vector from the first storage area according to the target compressed vector, and according to the query vector and the original vector. The distance between the vectors determines the target original vector, so that the speed and efficiency of vector range retrieval can be improved, and the accuracy of vector range retrieval can be improved at the same time.

In a second aspect, an embodiment of the present application provides a method for constructing a vector index for use in an electronic device, and the method includes:

get vector dataset;

Determine multiple clusters and representative vectors of clusters according to the vector data set;

Create a graph index based on the representative vector;

Obtain the original vector corresponding to the representative vector, and compress the original vector to obtain the compressed vector.

In a possible implementation of the above second aspect, establishing a graph index based on the representative vector includes:

Graph indices are built for representative vectors through a hierarchical navigable small-world algorithm.

In a possible implementation of the above second aspect, after the multiple clusters and the representative vectors of the clusters are determined according to the vector data set, the method further includes:

Get the cluster radius of multiple clusters in the vector dataset, and use the maximum value of the cluster radius as the maximum radius of the vector dataset.

In a possible implementation of the above-mentioned second aspect, the clustering radii of multiple clusters in the vector data set are obtained, including:

The distances between the representative vector of the cluster and the multiple original vectors in the cluster are calculated respectively, and the maximum value among the multiple distances is used as the cluster radius.

In a possible implementation of the above second aspect, the compressed vector is obtained by compressing the original vector, including:

The original vector is compressed by the product quantization method, and the compressed vector corresponding to the original vector is obtained.

In a possible implementation of the above second aspect, the original vector is compressed by a product quantization method, including:

Obtain multiple first sub-vectors of multiple original vectors in the vector dataset;

Determine a plurality of sub-vector clusters and sub-center point vectors corresponding to the sub-vector clusters according to the plurality of first sub-vectors;

Determine the first sub-center point vector with the closest distance to the first sub-vector of the original vector, and determine the number of the first sub-center point vector as the compressed vector corresponding to the first sub-vector;

The combination of the compressed vectors corresponding to each sub-vector in the original vector is determined as the compressed vector corresponding to the original vector.

The embodiment of the present application provides a method for constructing a vector index for an electronic device. The method obtains a vector data set, determines a plurality of clusters and representative vectors of the clusters according to the vector data set, and then establishes a graph index based on the representative vector. , and compress the original vector corresponding to the representative vector to obtain a compressed vector, thus constructing a two-level index for vector range retrieval, which provides a corresponding technical basis for improving the efficiency and accuracy of vector range retrieval.

In a third aspect, an embodiment of the present application provides an apparatus for vector range retrieval, the apparatus comprising:

The acquisition module is used to obtain the query vector and retrieval radius;

a loading module for loading the graph index and the compressed vector from the first storage area to the second storage area, and the read/write speed of the first storage area is lower than that of the second storage area;

A target representative vector determination module, configured to determine at least one target representative vector that is closest to the query vector in the graph index according to at least the query vector and the retrieval radius in the second storage area;

The target compressed vector determination module is used to obtain the compressed vector corresponding to at least one target representative vector in the second storage area, and determine the target compressed vector according to the distance between the query vector and the compressed vector;

The target original vector determination module is used to obtain the original vector corresponding to the target compressed vector from the first storage area according to the target compressed vector, and determine the target original vector according to the distance between the query vector and the original vector.

In a fourth aspect, an embodiment of the present application provides an apparatus for constructing a vector index, the apparatus comprising:

The acquisition module is used to acquire the vector dataset;

The clustering module is used to determine a plurality of clusters and the representative vectors of the clusters according to the vector data set;

The graph index creation module is used to establish graph index based on the representative vector;

The compression module is used to obtain the original vector corresponding to the representative vector, and compress the original vector to obtain the compressed vector.

In a fifth aspect, an embodiment of the present application provides an electronic device, the electronic device comprising:

memory for storing instructions for execution by one or more processors of the electronic device, and

The processor, which is one of the processors of the electronic device, is configured to execute any one of the above-mentioned first aspect and various possible implementations of the vector range retrieval method, or to execute the above-mentioned second aspect and each of the second aspect. Any of the possible implementations of constructing vector indices.

In a sixth aspect, an embodiment of the present application provides a readable storage medium, where an instruction is stored on the readable storage medium, and when the instruction is executed on an electronic device, the electronic device executes the above-mentioned first aspect and various possibilities of the first aspect Implement any one of the methods for vector range retrieval or perform any one of the above-mentioned second aspect and any of the various possible implementations of the second aspect to construct a vector index.

In a seventh aspect, an embodiment of the present application provides a computer program product, including a computer program/instruction, characterized in that, when the computer program/instruction is executed by a processor, the above-mentioned first aspect and various possible implementations of the first aspect are implemented Any one of the vector range retrieval methods in the above or any one of the above-mentioned second aspect and any of the various possible implementations of the second aspect to construct a vector index.

Description of drawings

FIG. 1 shows a schematic diagram of a query process of an approximate vector query method according to some embodiments of the present application.

FIG. 2 shows a schematic diagram of the correspondence between a center point and an inverted file according to some embodiments of the present application.

Fig. 3 shows a schematic diagram of a scene of a method for vector range retrieval according to some embodiments of the present application.

FIG. 4 shows a hardware structure diagram of an electronic device according to some embodiments of the present application.

FIG. 5 shows a schematic flowchart of building a primary index and a secondary index according to some embodiments of the present application.

Fig. 6 shows a schematic diagram of a graph index constructed according to a hierarchical navigable small world according to some embodiments of the present application.

FIG. 7 shows a schematic diagram of compressing an original vector according to a product quantization algorithm according to some embodiments of the present application.

FIG. 8 shows a schematic flowchart of a method for vector range retrieval according to some embodiments of the present application.

FIG. 9 shows a schematic diagram of a server loading a graph index and a compressed vector according to some embodiments of the present application.

Fig. 10 shows a schematic structural diagram of an apparatus for vector range retrieval according to some embodiments of the present application.

FIG. 11 shows a schematic structural diagram of an apparatus for constructing a vector index according to some embodiments of the present application.

Detailed ways

Illustrative embodiments of the present application include, but are not limited to, methods, apparatus, devices, media, and program products for vector range retrieval.

Hereinafter, some terms in this application will be explained so as to facilitate the understanding of those skilled in the art:

Vector: There are different definitions in different disciplines. In computer science, it refers to a sequence composed of multiple numbers. The number of numbers is the dimension of the vector. For example, a sequence composed of N numbers is an N-dimensional vector.

Vector range retrieval: Also known as vector range search, it refers to the retrieval of multiple target vectors whose similarity to the query vector is within a specified retrieval radius in a given vector data set according to a certain metric, and the target vector returned by vector range retrieval The number varies depending on the query vector and retrieval radius.

Graph index: An index created by a graph algorithm, expressed in the form of a graph, including edges between nodes, nodes corresponding to index data, and edges between associated nodes. During retrieval, the query vector is first retrieved in the graph composed of index data.

Vector quantization: It is a lossy data compression method for compressing vectors. By performing vector quantization on the original vector, the storage space occupied by the original vector can be reduced and the speed of vector loading can be improved.

Feature vector extraction: by abstracting each feature of unstructured data such as text, pictures, audio, video, etc. into an attribute, each attribute corresponds to one or more specific values, and then represented by multi-dimensional feature vectors corresponding to all attributes the unstructured data. For feature vector extraction of different types of unstructured data, different methods can be used, such as text segmentation and word conversion into vectors for text feature vector extraction, and image feature vector extraction. How the network converts pictures to vectors, etc.

Inverted Files Index (IVF): also known as reverse index, insert file or reverse file, is an indexing method, usually including index vector and inverted file, can quickly obtain the corresponding index vector according to the index vector inverted file. As an algorithm commonly used in approximate nearest neighbor retrieval, the vector space is divided into multiple clusters by clustering algorithms such as K-Means, and each cluster has its own center point vector. When querying, the query vector Calculate the distances to the center point vectors of multiple clusters separately and find the closest vector in the possibly multiple clusters with smaller distances. As shown in Figure 1, the clustered vector space includes cluster 1 and cluster 2. The center point vector of cluster 1 is center point 1, and the center point vector of cluster 2 is center point 2. When querying, the query The vector calculates the distance from the center point 1 and the center point 2 respectively, and then searches in the cluster 1 with the smallest distance, and the query result obtained is the closest vector 1. Specifically, the center point of each cluster in the vector space corresponds to an inverted file, and the vectors in the clusters are stored in the inverted file.

Inverted file: A file stored on persistent storage to store multiple vectors. As shown in Figure 2, the center point vector of cluster 1 [-3.2,1.7,2.4,…,0,2.1] corresponds to the inverted file 1, and the center point vector of cluster 2 [1.5,-0.3,3.9,… ,-2.8,0.1] corresponds to the inverted file 2. When the query vector searches for a similar vector in cluster 1, the search is performed in the inverted file 1 corresponding to cluster 1.

Clustering Algorithm: An unsupervised algorithm used to divide a collection of multiple data into subsets (or classes, clusters, or regions, etc.) by identifying relationships among the data. Some clustering algorithms can specify the number of subsets, such as K-means Clustering Algorithm (K-means) or clustering algorithm based on random selection (CLARANS), etc. Some clustering algorithms do not need to be specified. The number of subsets, the algorithm calculates the number of subsets according to its own principles and data conditions, such as density-based spatial clustering of applications with noise (Density-Based Spatial Clustering of Applications with Noise, DBSCAN), hierarchical structure-based balanced iterative reduction and clustering ( Balanced IterativeReducing and Clustering using Hierarchies, BIRCH) and so on.

It can be understood that, in various embodiments of the present application, the processor may be a microprocessor, a digital signal processor, a microcontroller, etc., and/or any combination thereof. According to another aspect, the processor may be a single-core processor, a multi-core processor, etc., and/or any combination thereof.

It can be understood that the vector range retrieval method of the present application is suitable for the scenario of performing vector range retrieval on unstructured data and retrieval radius submitted by the user.

The embodiments of the present application will be described in further detail below with reference to the accompanying drawings.

FIG. 3 provides a scenario for performing vector range retrieval according to some embodiments of the present application. As shown in FIG. 3 , the scenario includes a query component 100 , a data storage device 200 and a client 300 . The query component 100 includes a graph index retrieval module 101 , a compressed vector retrieval module 102 and an original vector retrieval module 103 .

The user inputs the query data and the retrieval radius through the retrieval interface provided by the client 300. The retrieval radius is used to describe the similarity between the retrieval result and the query data. Specifically, the smaller the distance between the retrieval result and the query data, the similarity is. higher.

It can be understood that the query data can be unstructured data or a query vector. Unstructured data may include: text data, picture data, audio data, and video data. Query vectors are high-dimensional vector data that describe the information users expect for range retrieval. The embodiments of the present application do not specifically limit the types of query data.

The client 300 receives the query data and retrieval radius input by the user, sends the query data and retrieval radius to the query component 100 at the back end for corresponding processing, and receives the result data returned by the query component 100 and displays it to the user.

It can be understood that if the query data received by the client 300 is unstructured data, the client 300 can directly send the unstructured data to the query component 100, or can first identify the type of the unstructured data, and determine the type of the unstructured data according to the unstructured data. The type of data converts the unstructured data into a query vector, and then sends the converted query vector to the query component 100 . This embodiment of the present application does not specifically limit whether the client 300 performs unstructured data conversion.

The query component 100 is configured to receive the query data and retrieval radius sent by the client 300 through the network, determine a corresponding query vector according to the query data, and then perform a corresponding range retrieval according to the query vector and retrieval radius to determine the retrieval result vector.

It can be understood that if the query data received by the query component 100 is a query vector, the query component 100 directly performs range retrieval according to the query vector and the retrieval radius; if the query data is unstructured data, the query component 100 first identifies the type of unstructured data, And according to the type of unstructured data, the unstructured data is converted into a query vector, and then the range retrieval is carried out according to the obtained query vector and retrieval radius. This embodiment of the present application does not specifically limit whether the query component 100 performs query vector conversion.

When the query component 100 performs range retrieval, it first transmits the query vector and the retrieval radius to the graph index retrieval module 101. The graph index retrieval module 101 performs retrieval in the pre-established graph index according to the query vector and retrieval radius, and determines the relationship between the query vector and the query vector. A vector of target indices whose similarity is in the range relative to the retrieval radius. The graph index retrieval module 101 transmits the obtained target index vector to the compressed vector retrieval module 102 . The compression vector retrieval module 102 determines the corresponding compression vector according to the target index vector, and determines the target compression vector satisfying the range retrieval condition according to the query vector and the retrieval radius. The compressed vector retrieval module 102 transmits the obtained target compressed vector to the original vector retrieval module 103 . The original vector retrieval module 103 determines the corresponding original vector according to the target compression vector, and determines the target original vector that satisfies the range retrieval condition according to the query vector and the retrieval radius, and the target original vector is the result of the vector range retrieval.

It can be understood that the query component 100 can return the target raw vector as result data to the client 300, can return the identifier of the target raw vector to the client 300, or can convert the target raw vector into corresponding unstructured data and return it to the client 300. The client 300 is not specifically limited in this embodiment of the present application.

In addition, the query component 100 is further configured to pre-establish a primary index and a secondary index for the vector data stored in the data storage device 200, and use the primary index and the secondary index during vector range retrieval to improve the speed and speed of vector range retrieval. efficiency. Here, the primary index is the center point vector obtained by clustering the vector data, the secondary index is the graph index established on the basis of the primary index, and the graph index is the graph algorithm based on the center point vector. built index. In addition, the query component 100 also compresses the original vector in the vector data by using the vector quantization method, which can save storage space and improve the computational efficiency during range retrieval.

The data storage device 200 is used for storing massive vector data. The stored vector data is obtained by processing massive unstructured data by means of vector conversion in advance. The vector data may include original vectors and compressed vectors after compressing the original vectors.

It can be understood that the above query component 100 and the client 300 may be two separate electronic devices, or may be one electronic device, such as a terminal in any specific form. The query component 100 and the data storage device 200 may be two separate electronic devices, or may be one electronic device, such as a server, which is not specifically limited in this embodiment of the present application.

The method provided by the technical solution of the present application obtains a center point vector as a primary index by clustering vector data, then establishes a graph index as a secondary index on the basis of the primary index, and analyzes the original vector corresponding to the center point vector. Compression is performed by vector quantization; when searching for a vector range, first search in the secondary index according to the query vector and retrieval radius to determine the target center point vector, and then search in the primary index according to the target center point vector to determine the corresponding target Compress the vector, and finally retrieve the original vector corresponding to the target compressed vector, determine the target original vector, and return the target original vector as the retrieval result, which can improve the speed and efficiency of vector range retrieval, and improve the accuracy of vector range retrieval.

FIG. 4 shows a block diagram of the hardware structure of an electronic device 20 for a method for vector range retrieval according to some embodiments of the present application. In the embodiment shown in FIG. 4 , the electronic device 20 may include one or more processors 201 , a system control logic 202 connected to at least one of the processors 201 , a system memory 203 connected to the system control logic 202 , and A non-volatile memory (NVM) 204 is connected to the system control logic 202 , and a network interface 206 is connected to the system control logic 202 .

In some embodiments, processor 201 may include one or more single-core or multi-core processors. In some embodiments, processor 201 may comprise any combination of general purpose processors and special purpose processors (eg, graphics processors, application processors, baseband processors, etc.). In embodiments where the electronic device 20 employs an enhanced base station (Evolved Node B, eNB) or radio access network (Radio Access Network, RAN) controller, the processor 201 may be configured to perform various conforming embodiments. For example, the processor 201 may be used to implement a method of vector range retrieval.

In some embodiments, system control logic 202 may include any suitable interface controller to provide any suitable interface to at least one of processor 201 with any suitable device or component in communication with system control logic 202 .

In some embodiments, system control logic 202 may include one or more memory controllers to provide an interface to system memory 203 . System memory 203 may be used to load as well as store data and/or instructions. For example, the system memory 203 may load the graph index and the compression vector in the embodiment of the present application, and may also store the received query vector and the like.

In some embodiments, the system memory 203 of the electronic device 20 may include any suitable volatile memory, such as a suitable dynamic random access memory (DRAM).

NVM memory 204 may include one or more tangible, non-transitory computer-readable media for storing data and/or instructions. In some embodiments, the NVM memory 204 may include any suitable non-volatile memory such as flash memory and/or any suitable non-volatile storage device, such as a hard disk drive (Hard Disk Drive, HDD), a compact disc (Compact Disc, At least one of a CD) drive and a Digital Versatile Disc (DVD) drive. In this embodiment of the present application, the NVM memory 204 may be used to store massive amounts of vector data.

NVM memory 204 may comprise a portion of storage resources on the apparatus in which electronic device 20 is installed, or it may be accessible by, but not necessarily be, part of the device. For example, NVM memory 204 may be accessed over a network via network interface 206 .

In particular, system memory 203 and NVM memory 204 may include temporary and permanent copies of instructions 205, respectively. The instructions 205 may include instructions that when executed by at least one of the processors 201 cause the electronic device 20 to implement the method shown in FIG. 2 . In some embodiments, instructions 205 , hardware, firmware and/or software components thereof may additionally/alternately reside in system control logic 202 , network interface 206 and/or processor 201 .

Network interface 206 may include a transceiver for providing a radio interface for electronic device 20 to communicate with any other suitable device (eg, front-end modules, antennas, etc.) over one or more networks. In some embodiments, network interface 206 may be integrated with other components of electronic device 20 . For example, network interface 206 may be integrated into at least one of processor 201, system memory 203, NVM memory 204, and a firmware device (not shown) having instructions that, when at least one of processors 201 executes the instructions , the electronic device 20 implements the method as shown in the method embodiment. In this embodiment of the present application, the network interface 206 may be used to receive unstructured data sent by the client, retrieval radius, received result data, and the like.

The network interface 206 may further include any suitable hardware and/or firmware to provide a multiple-input multiple-output radio interface. For example, network interface 206 may be a network adapter, wireless network adapter, telephone modem, and/or wireless modem.

In some embodiments, at least one of the processors 201 may be packaged with logic for one or more controllers of the system control logic 202 to form a System In a Package (SiP). In some embodiments, at least one of the processors 201 may be integrated on the same die with logic for one or more controllers of the system control logic 202 to form a System on Chip (SoC).

The electronic device 20 may further include an input/output (I/O) device 207 . I/O device 207 may include a user interface that enables a user to interact with electronic device 20 ; the peripheral component interface is designed to enable peripheral components to interact with electronic device 20 as well. In some embodiments, the electronic device 20 also includes sensors for determining at least one of environmental conditions and location information associated with the electronic device 20 .

In some embodiments, the user interface may include, but is not limited to, a display (eg, a liquid crystal display, a touch screen display, etc.), a speaker, a microphone, one or more cameras (eg, a still image camera and/or video camera), a flashlight (eg, a LED flash) and keyboard.

In some embodiments, peripheral component interfaces may include, but are not limited to, non-volatile memory ports, audio jacks, and power connectors.

In some embodiments, sensors may include, but are not limited to, gyroscope sensors, accelerometers, proximity sensors, ambient light sensors, and positioning units. The positioning unit may also be part of or interact with the network interface 206 to communicate with components of the positioning network (eg, BeiDou satellites).

It can be understood that the structure shown in FIG. 4 does not constitute a specific limitation on the electronic device 20 . In other embodiments of the present application, the electronic device 20 may include more or less components than shown, or combine some components, or separate some components, or arrange different components. The illustrated components may be implemented in hardware or software, or a combination of software and hardware.

The technical solutions of the present application will be described in detail below according to FIGS. 5 to 8 in combination with specific scenarios.

The specific process of establishing a vector index for a vector data set is explained below. FIG. 5 shows a schematic diagram of the construction flow of the primary index and the secondary index in the method for vector range retrieval implemented by the electronic device of the present application. As shown in Figure 5, establishing a primary index and a secondary index for a vector data set may include the following steps:

Step S501: Determine the vector data set.

Here, vector transformation is performed on the unstructured data in advance, and a set composed of massive vectors can be obtained, and the dimensions of the vectors are usually several hundred dimensions, such as 128 dimensions, 512 dimensions, and so on. The data of each dimension in the vector is represented as a floating-point number, usually a 64-bit floating-point number, and the storage space occupied by the data of each dimension is 8 bytes.

A vector set composed of massive vectors is a vector space, in which the number of vectors can range from millions to billions or even tens of billions. By indexing the vector space, the efficiency of vector range retrieval can be greatly improved.

It can be understood that when creating an index for a vector space, a vector data set can be obtained by sampling a vector space with a large number of vectors, such as a vector space of billions or tens of billions, and an index is established for the entire vector space according to the sampled vector data set; A vector space with a small number of vectors, such as a million-level or ten-million-level vector space, can be directly used as a vector data set, and an index can be established based on the vector data set. This embodiment of the present application does not specifically limit this.

In some embodiments, the index is established according to the vector data set, and the vector data set can be divided into a plurality of vector subsets through a clustering algorithm, and the vectors in each vector subset have similar properties in certain attributes.

In some embodiments, the entire vector space is determined as a vector data set, that is, all vectors in the vector space are regarded as vectors in the vector data set, and each vector participates in the classification calculation of the clustering algorithm, which is suitable for the order of magnitude comparison of vectors in the vector space. If it is small, the clustering result is more accurate, and the accuracy of the determined index vector is higher.

In some embodiments, the entire vector space is sampled to obtain a vector data set, that is, some vectors in the vector space are extracted as vectors in the vector data set, and only some of the vectors in the vector space will participate in the classification calculation of the clustering algorithm, which is suitable for vector space. In the case where the magnitude of the medium vector is large, because the classification result is obtained based on part of the vector, the clustering is inaccurate, and the accuracy of the determined index vector is reduced to a certain extent.

In some embodiments, different sampling methods can be used for sampling the vectors in the vector space, such as random sampling, stratified sampling, overall sampling, systematic sampling, and the like. The embodiments of the present application do not specifically limit the sampling method.

Step S502: Clustering the vectors in the vector data set to determine multiple clusters.

The vectors in the vector data set are input into the clustering algorithm, and the clustering algorithm performs clustering calculation on the input vectors to determine the corresponding clusters. In the clustering calculation process of the clustering algorithm, all the vectors in the input vector data set are input in each iteration, the similarity between the vectors and the classification center points is calculated and the vectors are classified, and then the classification center points of each category are recalculated. After repeated iterations, clusters that satisfy the termination conditions are obtained. As shown in Figure 1, the vector data set obtains cluster 1 and cluster 2 through the clustering algorithm. The representative vector of cluster 1 has center point 1, and the representative vector of cluster 2 is center point 2.

In some embodiments, clustering algorithms that do not require specifying the number of clusters, such as density-based noise-applied spatial clustering algorithms, hierarchical structure-based balanced iterative reduction and clustering algorithms, and the like, may be used. This type of clustering algorithm can determine the final number of clusters according to its own calculation, so that no user intervention is required.

In other embodiments, a clustering algorithm that can specify the number of clusters, such as a K-means clustering algorithm, a random selection-based clustering algorithm, etc., may be used. After this type of clustering algorithm performs clustering calculation, the number of categories obtained is the specified number of clusters. For example, if the specified number of clusters is 10, after the clustering algorithm clusters the vectors in the vector dataset, all vectors are divided into 10 classification sub-collections.

In some embodiments of the present application, the K-means algorithm is used as the clustering algorithm. During the execution of the K-means algorithm, K vectors are first determined in the vector data set as the initial cluster centers, and then the distance from the vector to the K cluster centers is calculated for each remaining vector in the vector data set, and the vector It is divided into the class corresponding to the cluster center with the smallest distance. After the remaining vectors are classified, the cluster center of each class is recalculated, and the new cluster center is used as the cluster center of the next iteration for repeated iteration calculation. After the preset termination condition is met, the execution of the algorithm is stopped. The K-means algorithm uses the Euclidean distance as the distance between vectors. The smaller the Euclidean distance, the more similar or even the same two vectors are. The K-means algorithm can achieve the local optimal clustering effect, and can ensure good scalability when dealing with massive data sets. At the same time, the complexity of the algorithm is low and easy to understand.

Step S503: Determine the representative vector of each cluster.

After clustering the vectors in the vector dataset, multiple clusters are obtained, and each cluster includes different vectors. The representative vector of the cluster is determined according to all the vectors in each cluster. The representative vector is the same as the The sum of the distances of other vectors in the same cluster is the smallest. In the embodiments of the present application, the center point vector is the representative vector of the cluster.

In some embodiments, the center point vector of the cluster may be determined according to the mean value of all vectors in the same cluster, and the value of each dimension in the center point vector is the arithmetic mean of the values of the corresponding dimension of all the vectors. For example, a cluster includes 3 vectors, respectively [3.5, 7.2, 4.7, -2.2, 2.5], [-1.3, 4.7, -5.1, 3.9, 8.5], [8.6, -0.2, 3.4, 6.4 , -0.5], then the center point vector of the cluster is [3.6, 3.9, 1.0, 2.7, 3.5].

It can be understood that other methods for calculating the mean value can also be used to calculate the center point vector of the cluster, such as geometric mean, root mean square mean, harmonic mean, weighted mean, etc. The method for determining the center point vector in this embodiment of the present application No specific restrictions are imposed.

In addition, the center point vector of the cluster may be a real vector, that is, a specific vector included in the cluster, or a virtual vector, that is, a vector that does not exist in the cluster. This embodiment of the present application does not specifically limit whether the center point vector is a real vector or a virtual vector.

As a representative vector of a cluster, it can be the center point vector as described above. In some embodiments, the representative vector can also be a vector selected based on other preset rules other than the center point vector. In the embodiment of the present application, the representative vector is the first-level index established in the vector space.

Step S504: Determine the original vector corresponding to each representative vector.

In the embodiment of the present application, the representative vector of each cluster is the center point vector of the cluster, the center point vector may correspond to the original vectors in multiple vector spaces, and the corresponding original vector may be retrieved through the center point vector.

In some embodiments, the representative vector represents a cluster in the vector data set, and the original vector in the cluster classified in the foregoing step is used as the original vector corresponding to the representative vector. Here, the representative vector and the corresponding original vector belong to the same cluster, indicating that the similarity between the original vector and the representative vector is higher than the similarity between the original vector and the representative vectors of other clusters, and the original vector belongs to the same Correspondence between the representative vectors of the clusters can better play the role of the index.

In some embodiments, the vector space is a vector data set. In the preceding steps, the original vectors in the vector data set have been classified into different clusters, and the center point vectors of the clusters are determined, and the original vectors in each cluster are classified into different clusters. A plurality of original vectors corresponding to the center point vector can be determined by the vector corresponding to the corresponding center point vector.

In some embodiments, the vector data set is a sample subset of the vector space, and only the cluster to which the original vector in the vector data set belongs is determined in the foregoing steps, so only the correspondence between the center point vector and the original vector in the vector data set is completed. The remaining original vectors in the vector space need to determine the corresponding clusters first, and then correspond to the center point vectors of the clusters. Specifically, the remaining original vectors in the vector space can calculate the distances between them and the center point vectors of all clusters, and classify themselves into the cluster with the smallest distance from them, so as to correspond to the center point vectors of the cluster. .

It can be understood that when calculating the distance between the original vector and the center point vectors of multiple clusters, the distance calculation method used is the same as the distance calculation method used when clustering the original vector in the vector data set in the preceding steps, so that through The original vector divided into a cluster by the clustering algorithm maintains a high similarity with the original vector divided into the cluster by the distance from the center point vector.

In some embodiments, the original vector corresponding to the representative vector may be stored in the inverted file. Specifically, each representative vector may correspond to an inverted file, and a plurality of original vectors corresponding to the representative vector are stored in the inverted file. As shown in Figure 2, the set of center points corresponds to multiple inverted files, wherein the center point [-3.2, 1.7, 2.4,..., 0, 2.1] corresponds to the inverted file 1, and the center point [-3.2, 1.7, 2.4] ,…,0,2.1] multiple original vectors belonging to the same cluster are stored in the inverted file 1, the center point [1.5,-0.3,3.9,…,-2.8,0.1] corresponds to the inverted file 2, and the center point [1.5,-0.3,3.9,…,-2.8,0.1] Multiple original vectors belonging to the same cluster are stored in inverted file 2.

In some embodiments of the present application, the cluster radius of the cluster is determined for each cluster, and the cluster radius refers to the maximum distance between the original vector in the cluster and the representative vector of the cluster. By determining the cluster radius of each cluster, the maximum distance between the original vector in the cluster and the center point vector as an index can be determined, thereby providing corresponding distance screening support for range retrieval based on the retrieval radius.

In some embodiments, the maximum radius of the vector space is determined from the cluster radius of each cluster. Since the cluster radius of each cluster is different, the maximum value of the cluster radius is determined as the maximum radius of the vector space, and the corresponding search range can be determined according to the maximum radius when performing range retrieval, so as to avoid missing possible search result vectors.

Step S505: Establish a corresponding graph index based on the representative vector.

In the embodiment of the present application, a graph index serving as a secondary index is established on the basis of the obtained representative vector of each cluster. Specifically, there are a large number of original vectors in the vector space, and the number of center point vectors used as primary indexes is also very large. By establishing a graph index for the center point vector, the retrieval efficiency of the index during range retrieval can be improved, and the range retrieval can be reduced. calculation time.

In some embodiments, a corresponding graph index is established for the representative vector through a Hierarchical Navigable Small Worlds (HNSW) algorithm. The constructed graph index includes multiple layers of navigable small worlds. Each layer of navigable small worlds includes several representative vectors. The bottom layer includes all representative vectors. The higher the layer, the fewer the number of representative vectors. The top layer has only one entry. A representative vector of points. There is an edge between the two representative vectors in the navigable small world of each layer when the two representative vectors are close enough.

Fig. 6 shows a schematic diagram of a graph index constructed according to a hierarchical navigable small world. As shown in Figure 6, the graph index constructed according to the hierarchical navigable small world algorithm includes 3 layers, the 0th layer is the bottom layer, the second layer is the highest layer, the 0th layer includes all the representative vectors, that is, the center point vector, and the first layer is the center point vector. Layer 1 includes some center point vectors in layer 0, and layer 2 includes some center point vectors in layer 1. The number of center point vectors in the upper layer is less, for example, layer 0 includes 8 There are four center point vectors in the first layer, and there is only one center point vector in the second layer, and the node Q is the query vector. Among them, the average distance between the center point vectors with edges in each layer, that is, the feature radius is constantly decreasing. For example, the feature radius between the four center point vectors in the first layer is greater than the sum of the eight center point vectors in the 0th layer. feature radius between.

It can be understood that the use of the hierarchical navigable small world algorithm to build a graph index for the center point vector is only an example, and does not constitute a limitation of the graph index algorithm. Other algorithms that can build graph indexes such as random graph algorithm, small world Algorithms, etc., are not specifically limited in this embodiment of the present application.

By using the hierarchical navigable small world algorithm to establish a graph index for the center point vector, the efficiency of distance calculation for the query vector in the graph index can be improved, and the number of center point vectors for distance calculation with the query vector can also be reduced. Efficiency of range retrieval.

Step S506: Compress the original vector to obtain a compressed vector.

Here, the original vector corresponding to the representative vector is usually a high-dimensional vector with a large dimension, such as 128-dimensional, 256-dimensional, etc., each dimension is usually a floating-point number, and the storage space occupied by the floating-point number is at least 4 bytes, Usually 8 bytes, an original vector with a dimension of 128 occupies at least 512 bytes of storage space, while the original vector corresponding to a representative vector is usually more than tens of thousands, and the storage space occupied is very large. The storage space occupied by the original vectors corresponding to thousands or even tens of thousands of representative vectors is huge, and it is almost impossible to load them into the memory or cache at the same time. Partial loading and rotation scheduling will cause the original vectors to be stored between memory and disk. Frequent call-in and call-out will seriously reduce the efficiency of vector range retrieval.

In some embodiments of the present application, the original vector can be compressed by compressing the dimension data in the original vector, thereby reducing the storage space occupied by the original vector.

In some embodiments, the original vector is compressed by a Product Quantization (PQ) algorithm to obtain a compressed vector. The product quantization algorithm is a retrieval algorithm. The product here is a Cartesian product. By decomposing a high-dimensional vector into the Cartesian product of multiple low-dimensional vectors, and quantizing the multiple low-dimensional vectors obtained by the decomposition, the high A dimensional vector can be represented by a quantized coded combination of multiple low-dimensional vectors.

The compression of the original vector will be specifically described below by taking the product quantization method as an example. Here, the dimension of the original vector is 128 dimensions, the original vector is divided into 8 sub-vectors, and the dimension of each sub-vector is 16 dimensions. FIG. 7 shows a schematic diagram of compressing the original vector according to the product quantization algorithm. As shown in Figure 7, the original vector is divided into 8 sub-vectors y ₁ to y ₈ , the dimensions of the y ₁ to y ₈ sub-vectors are 16 dimensions, and the y ₁ sub-vectors of each original vector in the vector space are formed into a 16-dimensional vector The vector set is clustered by K-Means algorithm and the number of clusters is set to 256. After clustering, 256 clusters are obtained, and a center point vector is determined for each cluster. Thus, 256 center point vectors can be obtained. The 256 center point vectors are sequentially numbered, and the number can be represented by an 8-bit binary number. Calculate the distance between the y ₁ sub-vector and the 256 center point vectors, and use the number corresponding to the center point vector with the closest distance to the y ₁ sub-vector as the compression code corresponding to the y ₁ sub-vector, that is, q ₁ (y ₁ ), the compression code is an 8-bit binary number. Similarly, the y ₂ sub-vectors of each original vector in the vector space are formed into a vector set and clustered to obtain another 256 center point vectors, and the distance between the y ₂ sub-vector and the 256 center point vectors is calculated. The number corresponding to the center point vector with the closest distance between the y ₂ sub-vectors is used as the compression code corresponding to the y ₂ sub-vectors, that is, q ₂ (y ₂ ). The compression encoding of the y ₃ to y ₈ sub-vectors is analogous. Finally, the 128-dimensional original vector can be compressed into a combination of 8-bit compression codes of 8 sub-vectors, that is, 64-bit compression codes.

It can be understood that the use of the product quantization algorithm to compress the original vector is only an example, and does not constitute a limitation of the algorithm used to compress the original vector. Other algorithms that can compress the original vector such as Scalar Quantization can also be used. , SQ), additive quantization (Additive Quantization, AQ), etc., which are not specifically limited in this embodiment of the present application.

In some embodiments, the original vectors corresponding to each representative vector are stored in different inverted files respectively, and the compressed vectors obtained by compressing the original vectors can be stored in another inverted file corresponding to the representative vector respectively. , the inverted file is used to store the compressed vector corresponding to the representative file.

In addition, the maximum radius of the vector space, the graph index, the compressed vector of the original vector, and the multiple sets of center point vectors and their numbers used for product quantization are persistently stored, and used for range retrieval.

In the embodiment of the present application, by establishing a graph index as a secondary index on the basis of the center point vector of the vector space as a primary index, the retrieval efficiency during vector range retrieval can be improved, and the original vector corresponding to the center point vector can be compressed at the same time. The compressed vector is obtained, so that the query vector can be retrieved in the compressed vector for the first time when the vector range is retrieved, and the compressed vector that does not meet the preset retrieval radius can be excluded, and the subsequent retrieval range of the query vector can be narrowed, so as not to reduce the accuracy Improve retrieval efficiency on the basis of rate.

It can be understood that in other embodiments of the present application, the center point vector can be compressed to reduce the occupied storage space, but the accuracy of vector range retrieval will be reduced. , the center point vector can be compressed on devices with limited storage space.

The above embodiment introduces the process of establishing an index suitable for vector range retrieval for a vector in the vector space. The following embodiment provides an explanation of the process of performing vector range retrieval according to the established index.

FIG. 8 shows a schematic flowchart of a method for vector range retrieval implemented by an electronic device according to the present application. The following description takes the server 100 as the query component and the vector database as the data storage device as an example for description. As shown in Figure 8, the vector range retrieval based on the query vector and retrieval radius may include the following steps:

Step S801: Obtain a query vector and a retrieval radius.

Here, the server 100 may first obtain a query vector and a retrieval radius used to limit the range of retrieval results, the retrieval radius is usually represented by a numerical value representing the similarity difference between vectors, and the query vector is usually a vector with the same dimension as the original vector in the vector space .

In some embodiments, the server 100 may receive unstructured data, and then transform the unstructured data to obtain corresponding query vectors. The unstructured data used for range retrieval can be one or more of text data, picture data, audio data and video data. For example, the unstructured data can be only pictures, or can include both text and pictures.

Specifically, the server 100 may check the type of the received unstructured data, and then use different vector transformation methods to convert according to the type of the unstructured data. For example, if the inspection result of the unstructured data by the server 100 is an image, the image is converted into a vector using the method of converting image to vector; if the inspection result of the unstructured data is text, the text into vector method is used to convert the text into a vector. Convert to vector. Here, the method of converting a picture into a vector may be, for example, a method of extracting a feature vector of a picture through a deep neural network, and the method of converting a text to a vector may be, for example, a method of firstly segmenting words and then converting the segmented words into corresponding vectors.

In some embodiments, the server 100 may directly receive a query vector, where the query vector is obtained by converting the unstructured data submitted by the user by the client 300. Specifically, the client 300 checks the type of unstructured data and obtains it. The query vector is obtained by vector conversion according to the corresponding type.

It can be understood that the retrieval radius obtained by the server 100 may be specified by the user through the client terminal 300, or may be determined by a preset value. For example, the client 300 only provides the query vector to the server and does not provide the retrieval radius, and the server can obtain the retrieval radius by reading the default value of the retrieval radius.

Step S802: Load the graph index and the compressed vector from the disk into the memory.

Here, the graph index and the compressed vector are stored on the disk of the data storage device 200. To use the graph index and the compressed vector for range retrieval, the graph index and the compressed vector need to be loaded from the disk into the memory. The memory capacity is usually small but the access speed is fast, and the disk capacity is usually large but the access speed is slow. The graph index and the compressed vector are loaded into the memory only when the range retrieval is required, which can make full use of the respective characteristics of the memory and the disk.

It can be understood that in addition to loading the graph index and compressed vector from disk to memory, the graph index and compressed vector can also be loaded from memory to a device with a faster access speed than memory, such as a graphics processor (Graphics Processing Unit, GPU), etc., This embodiment of the present application does not specifically limit this.

In some embodiments, the server 100 may load the graph index and the compressed vector from the disk of the data storage device 200 into the memory of the server 100 to perform range retrieval on the server 100 .

In some embodiments, the compressed vector is stored in the inverted file, and the server 100 may sequentially read the compressed vector in the inverted file when loading the compressed vector, and load the read compressed vector into the memory.

FIG. 9 shows a schematic diagram of the server 100 loading a graph index and a compressed vector. As shown in FIG. 9 , after loading, the memory 910 of the server 100 includes a graph index 911 composed of a center point vector and a plurality of inverted files 912 that store the compressed vectors, and the disk 920 stores a plurality of files that store the original vectors. Invert file 921. It can be understood that the disk 920 may be a disk on the server 100 or a disk of the data storage device 200 .

Step S803: Search in the graph index according to the query vector, and determine the target center point vector.

Here, the server 100 also needs to load the maximum radius of the vector space stored in the process of constructing the index of the vector space into the memory or the cache, where the maximum radius is used to describe the distance between the center point vector in the vector space and the corresponding original vector. maximum distance.

In some embodiments, the server 100 searches the graph index according to the query vector and the search radius, and determines the target center point vector that satisfies the range search condition. Specifically, the node in the graph index is the center point vector, and the edge in the graph index indicates that the two center point vectors connected by an edge are relatively similar. In the embodiment of the present application, the similarity between the center point vectors is measured by the distance between them. Calculate the similarity between the query vector and the nodes in the graph index, and determine whether the similarity difference between the two satisfies the conditions for range retrieval. In the case of retrieval conditions, the node is determined as the target center point vector, and then the adjacent nodes of the node, that is, other nodes that are edge-connected to the node, perform similarity calculation to determine whether there is a target center point vector in the adjacent nodes. , and perform a breadth-first search until the similarity difference between the query node and the nodes in the graph index is greater than the retrieval radius.

The following description takes the graph index constructed by the hierarchical navigable small world algorithm as an example. As shown in Figure 6, the graph index established by the hierarchical navigable small world algorithm is 3 layers, the 0th layer includes 8 center point vectors, the first layer includes 4 center point vectors, and the second layer includes a center point vector . When searching, the query vector Q starts from the top layer, that is, the second layer. Since the second layer has only one center point vector A ₁ , the center point vector with the smallest distance from the query vector Q is A ₁ , and A ₁ is used as the target center. Point vector; then search in the next layer, that is, the first layer, starting from the center point vector B ₁ , B ₁ is the exact same center point vector as A ₁ , and B ₁ has 1 adjacent node B ₂ , calculate the distance between the query vector Q and the center point vector B ₂ , and at the same time calculate the distance between the adjacent nodes of B ₂ and the query vector Q, B ₂ has two other adjacent nodes B ₃ and B ₄ , that is, again Calculate the distances between the query vector Q and the center point vectors B ₃ and B ₄ respectively. Comparing these three distances, it can be seen that the center point vector B ₃ has the smallest distance from the query vector Q, and B ₃ is used as the latest target center point vector; Next, the search is carried out in the lowest layer, the 0th layer, starting from the center point vector C ₃ , which is the exact same center point vector as B ₃ , and C ₃ has ₂ adjacent nodes C ₅ and C ₇ , Calculate the distance between the query vector Q and C ₅ and C ₇ respectively, and then calculate the distance of the query vector Q for the adjacent nodes of C ₅ and C _7. C ₅ has another adjacent node C ₆ , and C ₇ has another phase. Adjacent node C ₈ , so the distance between query vector Q and C ₆ and C ₈ is calculated again. Comparing these calculated distances, it can be seen that C ₆ is the closest to the query vector Q and the distance is less than the sum of the retrieval radius and the maximum radius of the vector space. center point vector, so C ₆ is determined as the latest target center point vector. _In addition, by calculating the distance between the query vector Q and the adjacent nodes of _C6 and C8, it can be seen that the obtained distance is greater than the sum of the retrieval radius and the maximum radius of the vector space, so stop the breadth-first retrieval, and the obtained _C6 is the final Target center point vector.

In some embodiments, when performing range retrieval in a graph index constructed by a hierarchical navigable small world algorithm, the distance between the target center point vector and the query vector is less than the sum of the retrieval radius and the maximum radius of the vector space. By expanding the distance between the target center point vector and the query vector to the range of the sum of the retrieval radius and the maximum radius of the vector space, it is possible to avoid missing the target center point vector, thereby avoiding missing possible retrieval results.

In some embodiments, when performing range retrieval in the graph index constructed by the hierarchical navigable small world algorithm, the distance between the query vector and the center point vector obtained by breadth first is greater than the retrieval radius and the maximum radius of the vector space. The sum is used as the condition to stop the retrieval. Using the above conditions to determine the time to stop the retrieval in the graph index can avoid expanding the scope of the range retrieval, reduce the calculation amount of the query vector and the center point vector, improve the efficiency of the range retrieval, and also ensure the accuracy of the retrieval results. Missing possible search results.

It can be understood that there may be one or more target center point vectors, which are not specifically limited in this embodiment of the present application.

Step S804: Obtain the compressed vector corresponding to the target center point vector, and determine the target compressed vector that satisfies the range retrieval condition.

In some embodiments, a distance calculation may be performed between the query vector and the compressed vector, and a compressed vector satisfying a preset distance threshold condition is determined as the target compressed vector. Here, the preset distance threshold can be alpha times the retrieval radius, and alpha is an empirical value that can be set based on experience in a production environment.

Specifically, the product quantization distance is calculated between the query vector and the compressed vector obtained by the product quantization algorithm, and the compressed vector that satisfies the product quantization distance less than the distance threshold related to the retrieval radius is used as the target compressed vector.

Through the above method, the compressed vectors can be screened, and the compressed vectors that may be within the retrieval range of the range retrieval can be selected, thereby reducing the retrieval scope of the subsequent retrieval and improving the efficiency of the scope retrieval.

In some embodiments, the query vector and the compressed vector obtained by the product quantization algorithm may be directly used for product quantization distance calculation.

For example, divide a 128-dimensional original vector into 8 16-dimensional sub-vectors, cluster the sub-vectors at the same position in multiple original vectors to obtain 256 16-dimensional center point vectors, and divide the 8 sub-vectors of the original vector into The vectors are respectively replaced with the identifier of the center point vector with the closest distance to obtain the compressed vector. The compressed vector includes the identifiers of 8 center point vectors. When the query vector and the compressed vector are multiplied and quantized for distance calculation, the compressed vector is calculated according to the center point vector. The identification of the point vector is restored to a vector consisting of 8 center point vectors, and finally the distance between the vector and the query vector is calculated. Here, since the center point vector has been determined before the range query is performed according to the query vector, the distance between the center point vectors can be pre-calculated, and the distance table can be queried to speed up the related distance calculation when performing the range query.

In other embodiments, the query vector may be multiplied and quantized according to parameters such as the number of sub-vectors consistent with the compressed vector, the number of center point vectors, and the corresponding number, and then the quantized query vector and the compressed vector may be multiplied to quantize the distance. calculate. The specific calculation method is similar to the above-mentioned method of directly calculating the product quantization distance between the query vector and the compressed vector.

Step S805: Obtain the original vector corresponding to the target compressed vector, and determine the target original vector that satisfies the range retrieval condition.

Here, after determining the target compression vector, the server 100 loads the original vector corresponding to the target compressed vector from the disk, so as to avoid preloading the original vector that occupies a large storage space and reduce excessive memory usage.

In some embodiments, the server 100 obtains the original vector corresponding to the compressed vector, and the original vector corresponding to the compressed vector may be determined by the center point vector corresponding to the compressed vector. For example, the center point vector has two corresponding inversions file, one inverted file stores the compressed vector, and the other inverted file stores the original vector. According to the sequence number of the compressed vector in the inverted file, the original vector with the same sequence number in the other inverted file is determined as the corresponding compressed vector. the original vector.

In some embodiments, the distance between the query vector and the original vector is calculated, and the original vector whose distance is smaller than the retrieval radius is determined as the target original vector. The range retrieval condition here is that the distance between the query vector and the original vector is less than the retrieval radius. Here, the distance calculation between the query vector and the original vector that may be within the retrieval radius of the range retrieval can directly determine whether the original vector meets the retrieval radius requirement of the range retrieval, which can improve the accuracy of the range retrieval and avoid the possibility of not being in the retrieval radius. The original vector within is used as the retrieval result.

Step S806: Return to the original target vector. Here, the target original vector is returned to the client 300 as the retrieval result of the range retrieval.

It can be understood that the server 100 can directly return the target original vector to the client 300, or can convert the target original vector into unstructured data, and return the unstructured data to the client 300, which is not specifically described in this embodiment of the present application. limit.

In some embodiments, the server 100 can convert the target original vector into the type of unstructured data submitted by the client 300. For example, if the type of unstructured data submitted by the user through the client 300 is a picture, the server 100 converts the target The original vector is converted into a picture, that is, the conversion from vector to picture is realized; the type of unstructured data submitted by the user through the client 300 is video, then the server 100 converts the target original vector into a video, that is, realizes the conversion from vector to video.

In some embodiments, the user can specify the type of the returned range retrieval result through the client 300. After the server 100 obtains the target original vector, it converts the target original vector according to the type of the returned retrieval result specified by the user. 300 specifies that the type of the returned retrieval result is an image. Even if the type of unstructured data submitted by the user is text, the server 100 will still convert the target original vector into an image and return it to the client 300 .

It can be understood that the returned retrieval result specified by the user can be of various types, and the server 100 converts the target original vector into corresponding various types of unstructured data and returns it to the client 300 .

It can be understood that the server 100 directly returns the target original vector to the client 300, and the client 300 can complete the above processing work of converting the target original vector into corresponding unstructured data.

According to an embodiment of the present application, an apparatus for vector range retrieval is also provided. As shown in Figure 10, the apparatus 1000 for vector range retrieval includes:

an acquisition module 1001, used to acquire a query vector and a retrieval radius;

The loading module 1002 is used to load the graph index and the compressed vector from the first storage area to the second storage area, and the read/write speed of the first storage area is lower than that of the second storage area;

The target representative vector determination module 1003 is used to determine, in the second storage area, at least one target representative vector whose distance is closest to the query vector in the graph index at least according to the query vector and the retrieval radius;

The target compressed vector determination module 1004 is used to obtain the compressed vector corresponding to at least one target representative vector in the second storage area, and determine the target compressed vector according to the distance between the query vector and the compressed vector;

The target original vector determination module 1005 is configured to obtain the original vector corresponding to the target compressed vector from the first storage area according to the target compressed vector, and determine the target original vector according to the distance between the query vector and the original vector.

According to an embodiment of the present application, an apparatus for constructing a vector index is also provided. As shown in FIG. 11, the apparatus 1100 for constructing a vector index includes:

an acquisition module 1101, used to acquire a vector data set;

Clustering module 1102, configured to determine a plurality of clusters and representative vectors of clusters according to the vector data set;

The graph index creation module 1103 is used for establishing graph index based on the representative vector;

The compression module 1104 is configured to obtain the original vector corresponding to the representative vector, and compress the original vector to obtain a compressed vector.

Embodiments of the mechanisms disclosed herein may be implemented in hardware, software, firmware, or a combination of these implementation methods. Embodiments of the present application may be implemented as a computer program or program code executing on a programmable system including at least one processor, a storage system (including volatile and nonvolatile memory and/or storage elements) , at least one input device, and at least one output device.

Program code may be applied to input instructions to perform the functions described herein and to generate output information. The output information can be applied to one or more output devices in a known manner. For the purposes of this application, a processing system includes any processor having a processor such as, for example, a Digital Signal Processor (DSP), a microcontroller, an Application Specific Integrated Circuit (ASIC), or a microprocessor system.

The program code may be implemented in a high-level procedural language or an object-oriented programming language to communicate with the processing system. The program code may also be implemented in assembly or machine language, if desired. In fact, the mechanisms described in this application are not limited in scope to any particular programming language. In either case, the language may be a compiled language or an interpreted language.

One or more aspects of at least one embodiment may be implemented by representative instructions stored on a computer-readable storage medium, the instructions representing various logic in a processor, the instructions, when read by a machine, cause the machine to make Logic that implements the techniques described herein. These representations, referred to as "IP cores," may be stored on tangible computer-readable storage media and provided to multiple customers or production facilities for loading into the manufacturing machines that actually manufacture the logic or processors.

In some cases, the disclosed embodiments may be implemented in hardware, firmware, software, or any combination thereof. The disclosed embodiments can also be implemented as instructions carried by or stored on one or more transitory or non-transitory machine-readable (eg, computer-readable) storage media, which can be executed by one or more processors read and execute. For example, the instructions may be distributed over a network or over other computer-readable media. Thus, a machine-readable medium can include any mechanism for storing or transmitting information in a form readable by a machine (eg, a computer), including, but not limited to, floppy disks, optical disks, optical disks, read only memories (CD-ROMs), magnetic Optical disc, Read Only Memory (ROM), Random Access Memory (RAM), Erasable Programmable Read Only Memory (EPROM), Electrically Erasable Programmable Read Only Memory (Electrically Erasable Programmable Read-Only Memory, EEPROM), magnetic or optical cards, flash memory, or devices used to transmit information (eg, carrier waves, infrared digital signals, etc.) using the Internet in electrical, optical, acoustic, or other forms of propagation signals Tangible machine-readable storage. Thus, machine-readable media includes any type of machine-readable media suitable for storing or transmitting electronic instructions or information in a form readable by a machine (eg, a computer).

In the drawings, some structural or method features may be shown in specific arrangements and/or sequences. It should be understood, however, that such specific arrangements and/or orderings may not be required. Rather, in some embodiments, the features may be arranged in a manner and/or order different from that shown in the illustrative figures. Additionally, the inclusion of structural or method features in a particular figure is not meant to imply that such features are required in all embodiments, and in some embodiments such features may not be included or may be combined with other features.

It should be noted that each unit/module mentioned in each device embodiment of this application is a logical unit/module. Physically, a logical unit/module may be a physical unit/module or a physical unit/module. A part of a module can also be implemented by a combination of multiple physical units/modules. The physical implementation of these logical units/modules is not the most important, and the combination of functions implemented by these logical units/modules is the solution to the problem of this application. The crux of the technical question raised. In addition, in order to highlight the innovative part of the present application, the above-mentioned device embodiments of the present application do not introduce units/modules that are not closely related to solving the technical problems raised in the present application, which does not mean that the above-mentioned device embodiments do not exist. other units/modules.

It should be noted that, in the examples and specification of this patent, relational terms such as first and second, etc. are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply that Any such actual relationship or sequence exists between these entities or operations. Moreover, the terms "comprising", "comprising" or any other variation thereof are intended to encompass a non-exclusive inclusion such that a process, method, article or device that includes a list of elements includes not only those elements, but also includes not explicitly listed or other elements inherent to such a process, method, article or apparatus. Without further limitation, an element qualified by the phrase "comprising a" does not preclude the presence of additional identical elements in a process, method, article, or device that includes the element.

Although the present application has been illustrated and described with reference to certain preferred embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and detail may be made therein without departing from the present disclosure The spirit and scope of the application.

Claims (14)

1. a method for vector range retrieval, for electronic equipment, is characterized in that, the method comprises: Get the query vector and retrieval radius; Loading the graph index and the compressed vector from the first storage area to the second storage area, wherein the read/write speed of the first storage area is lower than that of the second storage area; In the second storage area, at least one target representative vector whose distance is closest to the query vector in the graph index is determined according to at least the query vector and the retrieval radius; Obtain the compressed vector corresponding to the at least one target representative vector in the second storage area, and determine the target compressed vector at least according to the distance between the query vector and the compressed vector; According to the target compressed vector, the original vector corresponding to the target compressed vector is obtained from the first storage area, and the target original vector is determined according to the distance between the query vector and the original vector. 2. The method according to claim 1, wherein, at least according to the query vector and the retrieval radius, determining at least one target representative vector that is closest to the query vector distance in the graph index, comprising: determining the query vector and the retrieval radius, and further determining the maximum radius of the vector data set; The representative vector in the graph index is acquired in a breadth-first manner, and at least one target representative vector whose distance from the query vector is smaller than the sum of the retrieval radius and the maximum radius of the vector data set is determined. 3. The method according to claim 1, wherein determining the target compressed vector at least according to the distance between the query vector and the compressed vector, comprising: calculating the product quantized distance between the query vector and the compressed vector; A target compressed vector whose product quantization distance is smaller than a preset multiple of the retrieval radius is determined. 4. The method according to claim 1, wherein determining the target original vector according to the distance between the query vector and the original vector, comprising: calculating the distance between the query vector and the original vector; A target raw vector whose distance is less than the retrieval radius is determined. 5. The method according to claim 1, wherein the method further comprises: Convert the target raw vector to unstructured data, and return the unstructured data. 6. A method for constructing a vector index for electronic equipment, characterized in that the method comprises: get vector dataset; Determine a plurality of clusters and representative vectors of the clusters according to the vector data set; establishing a graph index based on the representative vector; Obtain the original vector corresponding to the representative vector, and compress the original vector to obtain a compressed vector. 7. The method according to claim 6, wherein after determining a plurality of clusters and representative vectors of the clusters according to the vector data set, the method further comprises: The clustering radii of a plurality of the clusters in the vector data set are obtained, and the maximum value of the clustering radii is used as the maximum radius of the vector data set. 8. The method according to claim 7, wherein obtaining the cluster radius of a plurality of the clusters in the vector data set comprises: The distances between the representative vector of the cluster and the plurality of original vectors in the cluster are respectively calculated, and the maximum value among the plurality of distances is used as the cluster radius. 9. The method according to claim 6, wherein the compressed vector is obtained by compressing the original vector, comprising: obtaining a plurality of first sub-vectors of a plurality of the original vectors in the vector data set; Determine a plurality of sub-vector clusters and sub-center point vectors corresponding to the sub-vector clusters according to the plurality of first sub-vectors; Determine the first sub-center point vector with the closest distance to the first sub-vector of the original vector, and determine the number of the first sub-center point vector as the compressed vector corresponding to the first sub-vector; A combination of compressed vectors corresponding to each sub-vector in the original vector is determined as a compressed vector corresponding to the original vector. 10. A device for vector range retrieval, characterized in that the device comprises: The acquisition module is used to obtain the query vector and retrieval radius; a loading module for loading the graph index and the compressed vector from the first storage area to the second storage area, wherein the read/write speed of the first storage area is lower than that of the second storage area; a target representative vector determination module, configured to determine, in the second storage area, at least one target representative vector that is closest to the query vector in the graph index according to at least the query vector and the retrieval radius; A target compressed vector determination module, configured to obtain the compressed vector corresponding to the at least one target representative vector in the second storage area, and determine the compressed target according to the distance between the query vector and the compressed vector vector; A target original vector determination module, configured to obtain the original vector corresponding to the target compressed vector from the first storage area according to the target compressed vector, and according to the distance between the query vector and the original vector Determine the target original vector. 11. A device for constructing a vector index, characterized in that the device comprises: The acquisition module is used to acquire the vector dataset; a clustering module for determining a plurality of clusters and representative vectors of the clusters according to the vector data set; A graph index creation module for establishing graph indexes based on the representative vector; A compression module, configured to obtain an original vector corresponding to the representative vector, and compress the original vector to obtain a compressed vector. 12. An electronic device, characterized in that, comprising: memory for storing instructions for execution by one or more processors of the electronic device, and The processor is one of the processors of the electronic device, and is used to execute the method for vector range retrieval described in any one of claims 1-5 or the method for constructing a vector index according to any one of claims 6-9 . 13. A readable storage medium, wherein an instruction is stored on the readable storage medium, and when the instruction is executed on an electronic device, the electronic device executes the vector range described in any one of claims 1-5 The method of retrieval or the method of constructing a vector index according to any one of claims 6-9. 14. A computer program product, comprising a computer program/instruction, characterized in that, when the computer program/instruction is executed by a processor, the method for vector range retrieval described in any one of claims 1-5 or claim 6 is implemented The method for constructing a vector index according to any one of -9.

Images