JP2024155177A - Information processing device, information processing method, and information processing program - Google Patents

Abstract

[Problem] Executing a search process appropriately according to a group. [Solution] The information processing device according to the present application has an acquisition unit that acquires group information indicating a plurality of first groups into which a plurality of objects to be the subject of a data search are classified and one or more second groups into which each of the plurality of first groups is classified into a group of objects belonging to each of the plurality of first groups, and a search query for the plurality of objects, and a search processing procedure that selects one first group from a target first group group selected from the plurality of first groups, selects one second group from among the second groups belonging to the selected one first group in order of the shortest distance between a second representative object and the search query, calculates the distance between the search query and an object belonging to the selected one second group as a target object, and executes a search process to extract a nearby object corresponding to the search query based on the distance between each of the target object and the search query. [Selected Figure] Fig. 47

Description

The present invention relates to an information processing device, an information processing method, and an information processing program.

Conventionally, techniques have been provided for searching (finding) various types of information. For example, a technique has been provided for generating a graph in which nodes corresponding to the search target are connected by edges, and performing a search using the generated graph. Such techniques are also used, for example, in image searches.

Patent No. 6293335 Patent No. 6300982 Patent No. 6311000

Masajiro Iwasaki, "Neighborhood Search Using Approximate k-Nearest Neighbor Graph with Tree-Structured Index", Transactions of Information Processing Society of Japan, 2011/2, Vol. 52, No. 2. pp.817-828.

However, the above conventional technology has room for improvement in terms of the efficiency of search processing. For example, the above conventional technology improves efficiency by reducing the time required for search processing by adjusting the number of edges in the graph, etc., and changing the graph to one that allows for efficient searches, but there is a limit to how much the efficiency of search processing can be improved by changing the graph. For this reason, it is desirable to introduce the concept of groups that classify objects to be searched, and to execute search processing appropriately according to the group, in order to generate information that can be used for efficient search processing, such as speeding up search processing.

The present application has been made in consideration of the above, and aims to provide an information processing device, an information processing method, and an information processing program that perform search processing appropriately according to the group.

The information processing device according to the present application is characterized by comprising: an acquisition unit that acquires group information indicating a plurality of first groups into which a plurality of objects to be subjected to a data search are classified, and one or more second groups into which each of the object groups belonging to each of the plurality of first groups is classified, and a search query for the plurality of objects; and a search processing unit that selects one first group from a target first group group selected from the plurality of first groups in order of the shortest distance between a first representative object of each of the target first group groups and the search query, selects one second group from the second groups belonging to the selected one first group in order of the shortest distance between a second representative object and the search query, performs a calculation process to calculate the distance between the search query and an object belonging to the selected one second group as a target object, and performs a search process to extract a nearby object corresponding to the search query based on the distance between each of the target objects and the search query calculated by the calculation process.

According to one aspect of the embodiment, it is possible to perform search processing appropriately according to the group.

FIG. 1 is a diagram illustrating an example of information processing according to the first embodiment. FIG. 2 is a diagram illustrating an example of data according to the first embodiment. FIG. 3 is a diagram illustrating an example of data according to the first embodiment. FIG. 4 is a diagram illustrating an example of the configuration of an information processing system according to the first embodiment. FIG. 5 is a diagram illustrating an example of the configuration of the information processing apparatus according to the first embodiment. FIG. 6 is a diagram illustrating an example of an object information storage unit according to the first embodiment. FIG. 7 is a diagram illustrating an example of a graph information storage unit according to the first embodiment. FIG. 8 is a diagram illustrating an example of a quantization information storage unit according to the first embodiment. FIG. 9 is a diagram illustrating an example of a codebook information storage unit according to the first embodiment. FIG. 10 is a flowchart illustrating an example of information processing according to the first embodiment. FIG. 11 is a flowchart illustrating an example of a search process according to the first embodiment. FIG. 12 is a diagram illustrating an example of information processing according to the second embodiment. FIG. 13 is a diagram illustrating an example of the configuration of an information processing apparatus according to the second embodiment. FIG. 14 is a diagram illustrating an example of a quantization information storage unit according to the second embodiment. FIG. 15 is a diagram illustrating an example of a blob information storage unit according to the second embodiment. FIG. 16 is a flowchart illustrating an example of a search process according to the second embodiment. FIG. 17 is a diagram illustrating an example of information processing according to the modified example. FIG. 18 is a diagram illustrating an example of a graph information storage unit according to a modified example. FIG. 19 is a flowchart showing an example of a search process according to the modified example. FIG. 20 is a diagram showing another example of information processing according to the modified example. FIG. 21 is a diagram illustrating an example of a process for generating blob information. FIG. 22 is a flowchart showing an example of information processing according to the modified example. FIG. 23 is a diagram illustrating an example of information processing according to the third embodiment. FIG. 24 is a diagram illustrating an example of the configuration of an information processing device according to the third embodiment. FIG. 25 is a diagram illustrating an example of a blob connection graph information storage unit according to the third embodiment. FIG. 26 is a flowchart illustrating an example of information processing according to the third embodiment. FIG. 27 is a flowchart showing an example of a search process according to the third embodiment. FIG. 28 is a flowchart showing an example of a search process according to the third embodiment. FIG. 29 is a diagram showing an example of blob connection graph information according to a modified example. FIG. 30 is a diagram illustrating an example of a blob information storage unit according to a modified example. FIG. 31 is a diagram illustrating an example of a blob connection graph information storage unit according to a modified example. FIG. 32 is a diagram illustrating an example of information processing according to the fourth embodiment. FIG. 33 is a diagram illustrating an example of the configuration of an information processing device according to the fourth embodiment. As shown in FIG. FIG. 34 is a conceptual diagram regarding quantization according to the fourth embodiment. FIG. 35 is a diagram illustrating an example of an inverted index according to the fourth embodiment. FIG. 36 is a diagram illustrating a specific example of an inverted index according to the fourth embodiment. FIG. 37 is a flowchart showing an example of information processing according to the fourth embodiment. FIG. 38 is a flowchart showing an example of information processing according to the fourth embodiment. FIG. 39 is a diagram illustrating an example of information processing according to the fifth embodiment. FIG. 40 is a diagram illustrating an example of information processing according to the fifth embodiment. FIG. 41 is a diagram illustrating an example of the configuration of an information processing device according to the fifth embodiment. FIG. 42 is a flowchart showing an example of information processing according to the fifth embodiment. FIG. 43 is a flowchart showing an example of a search process according to the fifth embodiment. FIG. 44 is a diagram illustrating an example of information processing according to the sixth embodiment. FIG. 45 is a diagram illustrating an example of the configuration of an information processing device according to the sixth embodiment. FIG. 46 is a flowchart showing an example of information processing according to the sixth embodiment. FIG. 47 is a diagram illustrating an example of information processing according to the seventh embodiment. FIG. 48 is a diagram illustrating an example of the configuration of an information processing device according to the seventh embodiment. FIG. 49 is a flowchart showing an example of information processing according to the seventh embodiment. FIG. 50 is a hardware configuration diagram showing an example of a computer that realizes the functions of the information processing device.

Below, the information processing device, information processing method, and information processing program according to the present application will be described in detail with reference to the drawings. Note that the information processing device, information processing method, and information processing program according to the present application are not limited to these embodiments. In addition, the same parts in the following embodiments will be denoted by the same reference numerals, and duplicated descriptions will be omitted.

(Embodiment)
1. First embodiment
[1-1. Information Processing]
An example of information processing according to the first embodiment will be described with reference to FIG. 1. FIG. 1 is a diagram showing an example of information processing according to the first embodiment. The information processing device 100 executes a search process using a graph index (also simply called a "graph") in which a plurality of objects to be the target of data search are graph-structured. FIG. 1 shows a part of the search process in which the information processing device 100 performs a neighborhood search using a graph in which nodes corresponding to each vector in which an object to be searched is vectorized are connected by edges. The information processing device 100 searches for nodes in the vicinity of a given search query (vector) by tracing each node of the graph as an object to be searched. The information processing device 100 extracts a predetermined number of nodes (hereinafter also referred to as "search count") designated as the number of nearby nodes to be extracted by the search process as nodes in the vicinity of the search query. In the following, a case in which image information is the target of data search will be described as an example, but the target of data search may be various objects such as video information and audio information.

The information processing device 100 performs search processing on nodes corresponding to vast amounts of image information in the units of millions to hundreds of millions, but only a portion of them (dozens such as node N1 in FIG. 1) are shown in the drawings. For example, as shown in the spatial information SP1 in FIG. 1, the information processing device 100 acquires information on multiple nodes (vectors) such as nodes N1, N7, N9, etc. When "node N* (* is an arbitrary numerical value)" is written in this way, it indicates that the node is identified by the node ID "N*". For example, when "node N1" is written, the node is identified by the node ID "N1". Each white circle (◯) in the spatial information SP1 indicates a node.

In the spatial information SP1 in FIG. 1, nodes mainly related to the explanation are labeled, but each of the unlabeled white circles (◯) is also a node, and many other nodes are included in addition to the nodes shown in the figure. Also, each node corresponds to an object (search target). For example, each of multiple local features extracted from an image may be an object. Also, for example, various data in which the distance between objects is defined may be an object.

For example, the spatial information SP1 in FIG. 1 may be a Euclidean space. For example, the spatial information SP1 corresponds to the number of dimensions of the object's vector, and is a multidimensional space of 100 dimensions, 1000 dimensions, etc. Note that FIG. 1 conceptually illustrates a state in which the vector (space) is divided into four partial regions (subspaces) by direct product quantization as shown in the spatial information SP1, but the direct product quantization will be described later.

The dotted lines connecting the white circles (◯) that are nodes in the spatial information SP1 indicate edges that connect the nodes. In the example of FIG. 1, for the sake of simplicity, the nodes are connected by undirected (bidirectional) edges (hereinafter also simply referred to as "edges"). Note that an undirected edge here means an edge that allows data to be traced in both directions between the connected nodes. For example, a dotted line connects the white circle (◯) representing node N1 and the white circle (◯) representing node N4, indicating that node N1 and node N4 are connected by an edge. In other words, in the graph shown in the spatial information SP1, it is possible to trace between node N1 and node N4 in both directions. Specifically, in the spatial information SP1, it is possible to trace from node N1 to node N4, and from node N4 to node N1.

In the example of FIG. 1, for ease of illustration, only the edges connecting the illustrated nodes are shown, but many other edges are included in addition to the edges shown. Thus, in the spatial information SP1 in FIG. 1, only a portion of the edges is shown, but it is assumed to be, for example, a k-nearest neighbor graph. Note that the spatial information SP1 may be various graphs.

In addition, the edges of a graph are not limited to undirected edges, and may be directed edges. In the case of a directed edge, it is only possible to trace from the node that is the reference source of the directed edge to the referenced node. For example, if two nodes are connected by two directed edges, a first edge with one as the reference source and the other as the reference destination, and a second edge with one as the reference destination and the other as the reference source, the state is the same as if the two nodes were connected by an undirected (bidirectional) edge.

From here, the search process will be described with reference to FIG. 1. In the example of FIG. 1, it is assumed that the information processing device 100 has already acquired a graph GR1 as shown in the spatial information SP1. Note that the information processing device 100 may generate the graph GR1 by appropriately using various conventional techniques. First, prior to describing the search process, the direct product quantization of vectors (space) will be described.

Figure 1 conceptually illustrates a state in which a vector (space) is divided into four subspaces AR11 to AR14 by direct product quantization, as shown in spatial information SP1. The subspaces AR11 to AR14 shown in Figure 1 are shown in a conceptual diagram to explain the distance between vectors of each node (object), etc., but each of the subspaces AR11 to AR14 is a multidimensional space. For example, the subspace AR11 shown in Figure 1 is shown in a two-dimensional form in order to be illustrated on a plane, but it is assumed to be a multidimensional space with, for example, 100 dimensions or 1000 dimensions.

Each of the subspaces AR11 to AR14 indicates a space corresponding to each division (partial vector) of the vector divided into four. Note that, for example, a 100-dimensional vector may be divided into 100 parts. For example, the subspace AR11 indicates a dimensional space (also referred to as the "first subspace") corresponding to the first partial vector (also referred to as the "first subvector") of the four partial vectors (also referred to as "subvectors") obtained by dividing a vector into four. The subspace AR11 indicates a subspace (first subspace) corresponding to the first division position of the vector. In the case of the search query QE1, the subspace AR11 is a space corresponding to the first partial query QE1-1, which is the first partial vector (first subvector).

Furthermore, subspace AR12 indicates a dimensional space (also referred to as the "second subspace") corresponding to the second-first partial vector (also referred to as the "second subvector") out of the four partial vectors obtained by dividing a vector into four. Subspace AR12 indicates a subspace (second subspace) corresponding to the second-first division position of the vector. In the case of search query QE1, subspace AR12 is a space corresponding to the second-first partial query QE1-2, which is the second-first partial vector (second subvector).

Furthermore, subspace AR13 indicates a dimensional space (also referred to as the "third subspace") corresponding to the third partial vector from the top (also referred to as the "third subvector") out of the four partial vectors obtained by dividing a vector into four. Subspace AR13 indicates the subspace (third subspace) corresponding to the third division position from the top of the vector. In the case of search query QE1, subspace AR13 is a space corresponding to the third partial query QE1-3, which is the third partial vector (third subvector) from the top.

Furthermore, subspace AR14 indicates a dimensional space (also referred to as the "fourth subspace") corresponding to the fourth (i.e., last) partial vector from the beginning (also referred to as the "fourth subvector") of the four partial vectors obtained by dividing a vector into four. Subspace AR14 indicates the subspace (fourth subspace) corresponding to the fourth division position from the beginning of the vector. In the case of search query QE1, subspace AR14 is a space corresponding to the fourth partial query QE1-4, which is the fourth partial vector (fourth subvector) from the beginning.

In the example of Figure 1, the subspaces AR11 to AR14 are shown with similar shapes, but the shapes of the subspaces AR11 to AR14 may be different, and the division of the areas in each of the subspaces AR11 to AR14 may also be different. Also, the connection relationships between nodes via edges are assumed to be common to the subspaces AR11 to AR14. In other words, the graph GR1 is a graph that corresponds to the spatial information SP1, and is common to the subspaces AR11 to AR14.

In the example of FIG. 1, a lookup table is generated for each divided partial vector (subvector). For example, the first subvector, the second subvector, the third subvector, and the fourth subvector are clustered, and a lookup table (codebook information) is generated for each subvector.

In FIG. 1, the first subvectors are clustered into nine groups corresponding to codebooks CD11 to CD19 as shown in subspace AR11, and vectors corresponding to each of the codebooks CD11 to CD19 are calculated as representative vectors (centroids). For example, the first subvectors of nodes N7, N9, etc. are shown to be clustered into a group corresponding to codebook CD11. In this case, in distance calculation, the first subvectors of nodes N7, N9, etc. are vector quantized into vectors of codebook CD11 using codebook information (also referred to as "first codebook information") corresponding to the first subvectors.

The second subvectors are clustered into a number of groups corresponding to the codebooks CD21 to CD24 (see Figures 2 and 9), and a vector corresponding to each of the codebooks CD21 to CD24 is calculated as a representative vector (centroid). In this case, the second subvectors of each node are vector quantized into a vector of the corresponding codebook using the codebook information (also called "second codebook information") corresponding to the second subvector in the distance calculation.

The third subvectors are clustered into a number of groups corresponding to the codebooks CD31 to CD34 (see Figures 2 and 9), and the vectors corresponding to each of the codebooks CD31 to CD34 are calculated as representative vectors (centroids). In this case, in the distance calculation, the third subvectors of each node are vector quantized into vectors of the corresponding codebooks using the codebook information (also called "third codebook information") corresponding to the third subvectors.

The fourth subvectors are clustered into multiple groups corresponding to the codebooks CD41 to CD44 (see Figures 2 and 9), and the vectors corresponding to each of the codebooks CD24 to CD44 are calculated as representative vectors (centroids). In this case, in the distance calculation, the fourth subvectors of each node are vector quantized into vectors of the corresponding codebooks using the codebook information (also called "fourth codebook information") corresponding to the fourth subvector.

The codebook information, including the process of determining the representative vector, is generated using various techniques as appropriate. The generation of the codebook information is a conventional technique, so a detailed explanation is omitted. The lookup table is not limited to the above, and for example, one lookup table (codebook information) may be used for all the divided partial vectors (sub-vectors), but this will be discussed later.

Now, the search process targeting the search query QE1 will be described. First, the information processing device 100 acquires the search query QE1 (step S11). For example, the information processing device 100 acquires the search query QE1 from the terminal device 10 (see FIG. 4) used by the user.

Then, the information processing device 100 divides the vector that is the search query QE1 into four. That is, the information processing device 100 divides the search query QE1 into four partial queries. In FIG. 1, the information processing device 100 divides the search query QE1 into four sub-vectors: a first partial query QE1-1 that is a first sub-vector, a second partial query QE1-2 that is a second sub-vector, a third partial query QE1-3 that is a third sub-vector, and a fourth partial query QE1-4 that is a fourth sub-vector. Specifically, the information processing device 100 sets "45, 23, 2..." as the first partial query QE1-1, "127, 34, 5..." as the second partial query QE1-2, "20, 98, 110..." as the third partial query QE1-3, and "12, 45, 4..." as the fourth partial query QE1-4.

Then, the information processing device 100 calculates the distance between each sub-vector of the search query QE1 and the vector in the code book corresponding to that sub-vector. The information processing device 100 calculates the distance (difference) between each sub-vector of the search query QE1 and each vector in the code book, as shown in the code book information TB1 to TB4 in FIG. 2. FIG. 2 is a diagram showing an example of data according to the first embodiment.

Codebook information TB1 indicates the first codebook information corresponding to the first subvector, and the information processing device 100 calculates the distance between each vector of codebooks CD11 to CD19 corresponding to the first subvector and the first partial query QE1-1. In FIG. 2, the information processing device 100 calculates the distance between codebook CD11 and the first partial query QE1-1 as distance DS11, as shown in codebook information TB1. Similarly, the information processing device 100 calculates the distance between each of codebooks CD12 to CD14, etc., and the first partial query QE1-1 as distance DS12 to DS14, etc.

Similarly, each of the codebook information TB2 to TB4 indicates second to fourth codebook information corresponding to each of the second to fourth subvectors. As shown in the codebook information TB2, the information processing device 100 calculates the distance between each of the codebooks CD21 to CD24, etc. and the second partial query QE1-2 as distances DS21 to DS24, etc. As shown in the codebook information TB3, the information processing device 100 calculates the distance between each of the codebooks CD31 to CD34, etc. and the third partial query QE1-3 as distances DS31 to DS34, etc. As shown in the codebook information TB4, the information processing device 100 calculates the distance between each of the codebooks CD41 to CD44, etc. and the fourth partial query QE1-4 as distances DS41 to DS44, etc.

Note that, although FIG. 2 shows the distances abstractly for the sake of explanation, the distances DS11 to DS44 are concrete values. The distances are values expressed as floating point numbers, but may be compressed to 1-byte integer type by scale-offset-compression (see, for example, "https://www.unidata.ucar.edu/blogs/developer/entry/compression_by_scaling_and_offfset") for speedup using SIMD (Single Instruction, Multiple Data) described later. The information processing device 100 may calculate the distance between each codebook and the query when the search query QE1 is acquired, or when the information becomes necessary. In the search process, the information processing device 100 uses the codebook information TB1 to TB4 as a lookup table to calculate the distance between each node and the search query QE1, that is, the approximate distance (also called the "first distance"). In this way, when searching a graph in a search process, the information processing device 100 calculates and processes an approximate distance (first distance) rather than the true distance (also called the "second distance") between each node and the search query, thereby enabling efficient search processing.

The information processing device 100 executes a search process targeting the search query QE1 (step S12). The information processing device 100 performs a search process as shown in FIG. 11 using the graph GR1 targeting the search query QE1, thereby obtaining search results for the search query QE1. The search process shown in FIG. 11 will be described in detail later. The information processing device 100 performs a search process targeting the search query QE1, thereby extracting the number of search nodes as nodes in the vicinity of the search query QE1.

In a search process targeting search query QE1, information processing device 100 selects a specific node from among the nodes as a node (hereinafter also referred to as "start node") that will be the starting point (origin) of the search of graph GR1. For example, information processing device 100 selects the start node using a specific index such as a tree structure index. In the example of FIG. 1, information processing device 100 selects node N7 as the start node. Note that, for simplicity of explanation, FIG. 1 shows a case where only node N7 is selected as the start node using a specific index, but information processing device 100 may select multiple nodes as the start node, or may select the start node using various methods such as random.

Here, in the search process targeting the search query QE1, the information processing device 100 calculates in parallel the distance between the search query and a node connected by an edge from one node (hereinafter also referred to as a "connecting node") (step S13). In FIG. 1, as shown in the batch processing information LT1, the information processing device 100 calculates in parallel the distance between the search query QE1 and nodes N9, N12, N54, N85, etc., which are nodes connected by edges from node N7 (connecting nodes).

For example, as shown in the node information INF1, the node N9 indicates that the first subvector corresponds to the codebook CD12, the second subvector corresponds to the codebook CD23, the third subvector corresponds to the codebook CD35, and the fourth subvector corresponds to the codebook CD47. Note that the size of the variable CD is determined by the size of the codebook, so if the codebook size is 16, for example, the variable CD can be 4 bits, which allows for significant data compression. Therefore, the information processing device 100 calculates the distance between the node N9 and the search query QE1 using the distance DS12 of the codebook CD12, the distance DS23 of the codebook CD23, the distance DS35 of the codebook CD35, and the distance DS47 of the codebook CD47. For example, the information processing device 100 calculates the total of the distance DS12 of the codebook CD12, the distance DS23 of the codebook CD23, the distance DS35 of the codebook CD35, and the distance DS47 of the codebook CD47 as the distance between the node N9 and the search query QE1.

For example, as shown in node information INF2, node N12 indicates that the first subvector corresponds to codebook CD14, the second subvector corresponds to codebook CD29, the third subvector corresponds to codebook CD31, and the fourth subvector corresponds to codebook CD45. For example, the information processing device 100 calculates the sum of distance DS14 of codebook CD14, distance DS29 of codebook CD29, distance DS31 of codebook CD31, and distance DS45 of codebook CD45 as the distance between node N12 and search query QE1. Similarly, the information processing device 100 calculates the distance between node N54 and search query QE1 using node information INF3 of node N54, and calculates the distance between node N85 and search query QE1 using node information INF4 of node N85.

For example, the information processing device 100 calculates the distance between each of nodes N9, N12, N54, and N85 and the search query QE1 all at once by parallelizing SIMD operations. In this way, the information processing device 100 can speed up distance calculations by parallelizing the distance calculations, enabling efficient search processing.

Note that, for the sake of simplicity, FIG. 1 shows a case where distances are calculated in parallel for four nodes, but the number of nodes to be parallelized is determined based on the specifications of the information processing device 100. For example, when the number of nodes that can be collectively processed by the information processing device 100 using SIMD (also called the "unit of collectively processable") is "4", the processing is the same as that shown in FIG. 1. However, when the number of nodes that can be collectively processed by the SIMD (unit of collectively processable) is "16", the information processing device 100 calculates the distances in parallel for 16 nodes. When the unit of collectively processable is "32", the information processing device 100 calculates the distances in parallel for 32 nodes. In this way, the information processing device 100 can perform efficient search processing by collectively calculating the distances of the number of nodes that corresponds to the number of nodes that can be collectively processed by SIMD (unit of collectively processable).

The information processing device 100 performs the distance calculations for multiple nodes in parallel as described above, while performing a search process as shown in FIG. 11 using the graph GR1 for the search query QE1, thereby extracting the number of searched nodes as nodes in the vicinity of the search query QE1.

As described above, the information processing device 100 can enable efficient search processing by calculating the approximate distance (first distance) between the vector of each vector-quantized node and the search query, and performing search processing using the first distance. Furthermore, the information processing device 100 can enable efficient search processing by collectively performing distance calculations for a number of nodes that can be parallelized. As described above, the information processing device 100 can increase speed by repeatedly using a limited memory area (lookup table) (stored in a memory cache) by collectively calculating the approximate distances between a graph node and multiple connecting nodes.

In the example of FIG. 1, the information processing device 100 performs a search process using a vector divided by direct product quantization, thereby enabling a more efficient search process compared to a case where the search process is performed without dividing the vector. For example, the information processing device 100 calculates the distance between short vectors by direct product quantization, and can reduce the size of the vector to be the target of the distance calculation. In addition, the information processing device 100 can limit the memory space accessed by the lookup table used in the distance calculation to the lookup table of the divided subvector. The information processing device 100 can reduce the vector size while suppressing a decrease in search accuracy by direct product quantization. Note that, in FIG. 1, the process when direct product quantization is performed is described, but the case where direct product quantization is performed is merely an example, and the information processing device 100 may perform a search process using a vector that has not been subjected to direct product quantization.

[1-1-1. Others]
The above-described process is merely an example, and the information processing device 100 may perform the search process using various information and methods for efficient search processing. Each aspect of this point will be described in detail below.

(Storage of edges (connection nodes))
Regarding information on edges (connecting nodes) connected to each node, there are two possible storage modes (storage methods) for the edges (connecting nodes) at the node, for example, a first storage mode and a second storage mode as described below, and the storage mode may be selected depending on the usage pattern.

For example, in a first storage mode, each node may be stored in association with the ID of the connecting node (object), and information on the object that has been subjected to the Cartesian product quantization may be stored in a separate table. For example, the data storage modes shown in Figures 7 and 8 correspond to the first storage mode. With the first storage mode, memory usage can be reduced.

In addition, for example, in the second storage mode, each node has a quantized object directly. In the case of the second storage mode, a connection node (object) of a certain node stores quantized information in association with each node. For example, the second storage mode corresponds to a data storage mode in which the quantized information (node information INF1 to INF4 in FIG. 2) of each of nodes N9, N12, N54, and N85, which are connection nodes of node N7, is stored in association with node N7. In the case of the second storage mode, objects are accessed sequentially during a search, so speed reduction can be suppressed.

(Lookup table)
In the above example, clustering is performed for each divided sub-vector, and a lookup table (codebook information) is generated for each sub-vector. However, this is not limited to the above case, and the lookup table may take any form.

For example, all subvectors may be clustered and one lookup table may be generated. In the above example, all four subvectors, the first subvector, the second subvector, the third subvector, and the fourth subvector, may be clustered and one lookup table may be generated.

Also, individual subvectors may be partially merged to generate a lookup table for each of multiple classes. For example, subvectors with similar variances may be merged to form multiple classes, and a lookup table may be generated for each of the multiple classes. In the above example, for example, if the variances of two subvectors, the first subvector and the third subvector, are similar, and the variances of two subvectors, the second subvector and the fourth subvector, are similar, the first subvector and the third subvector may be merged to form the first class, and the second subvector and the fourth subvector may be merged to form the second class. In this case, two lookup tables may be generated: a lookup table (codebook information) for the first class and a lookup table (codebook information) for the second class.

(Transpose)
The above-mentioned data storage is merely an example, and the information processing device 100 may store data in various forms so as to enable efficient data reference, etc. For example, the information processing device 100 may store transposed data. This point will be described with reference to Fig. 3. Fig. 3 is a diagram showing an example of data according to the first embodiment.

For example, if data is stored as shown in the node information INF1 to INF4 and the node information INF1 to INF4 is processed sequentially, the codebook information TB1 to TB4, which are lookup tables, will be repeatedly referenced as shown in step S14 of FIG. 2.

Therefore, as shown in step S15, transposed data TR1 to TR4 are generated by transposing the node information INF1 to INF4. For example, the information processing device 100 generates transposed data TR1 to TR4 by transposing the node information INF1 to INF4.

In FIG. 3, first data TR1 is generated, which is a list of codebooks corresponding to the first subvectors of nodes N9, N12, N54, and N85 from among the node information INF1 to INF4. Specifically, first data TR1 is generated, which is a list of codebooks CD12 corresponding to the first subvector of node N9, codebook CD14 corresponding to the first subvector of node N12, codebook CD13 corresponding to the first subvector of node N54, and codebook CD18 corresponding to the first subvector of node N85.

Similarly, second data TR2 is generated which is a list of codebooks corresponding to the second subvectors of nodes N9, N12, N54, and N85 from among the node information INF1 to INF4. Third data TR3 is generated which is a list of codebooks corresponding to the third subvectors of nodes N9, N12, N54, and N85 from among the node information INF1 to INF4. Fourth data TR4 is generated which is a list of codebooks corresponding to the fourth subvectors of nodes N9, N12, N54, and N85 from among the node information INF1 to INF4.

In addition, correspondence information is generated that indicates which data in the list of each of the transposed data TR1 to TR4 corresponds to which node. In the example of FIG. 3, correspondence information is generated that indicates that the first (initial) data in the list of each of the transposed data TR1 to TR4 corresponds to node N9, the second data corresponds to node N12, the third data corresponds to node N54, and the fourth (last) data corresponds to node N85. By referring to the correspondence information, the information processing device 100 can specify which node each data in the list of each of the transposed data TR1 to TR4 corresponds to. For example, the information processing device 100 generates the correspondence information.

The information processing device 100 performs processing using transposed data TR1 to TR4 obtained by transposing the node information INF1 to INF4. For example, when the information processing device 100 refers to a lookup table using the transposed data TR1, it refers only to the codebook information TB1, and thus refers to only one piece of codebook information TB1. Similarly, when the information processing device 100 refers to a lookup table using the transposed data TR2, it refers only to the codebook information TB2, and thus refers to only one piece of codebook information TB2. Similarly, for the transposed data TR3 and TR4, it refers to only one piece of codebook information. This allows the information processing device 100 to efficiently refer to data, thereby enabling efficient search processing.

In this way, just as a lookup table for each subclass (subvector, etc.) is referenced when calculating distances in bulk, the data of the node's neighboring objects (connecting nodes) is transposed, and the nodes store the data in the order in which they were compiled for each subclass, further improving the locality of reference and enabling faster calculations.

Note that, for the sake of simplicity, FIG. 3 shows a case where transposed data is generated for four nodes, but the unit (number of nodes) for generating the transposed data is determined based on the specifications of the information processing device 100. For example, when the batch processable unit of the information processing device 100 is "4", the same process as in FIG. 3 is performed, but when the batch processable unit is "16", the transposed data is generated with 16 nodes as one unit. When the batch processable unit is "32", the transposed data is generated with 32 nodes as one unit. In this way, by using the transposed data generated according to the number that the information processing device 100 can process in a batch by SIMD (batch processable unit), the information processing device 100 can efficiently refer to data, thereby enabling efficient search processing.

For example, most of the time during search processing as described above is taken up by distance calculation, but distance calculation can be sped up by parallel calculation using SIMD as described above. When distance calculation is parallelized in this way, the time spent fetching object data takes up the majority of the search processing. If this fetch time can be reduced, further speedups can be achieved. Note that prefetching can be used to reduce the time spent fetching data, but this has limitations.

On the other hand, the information processing device 100 can suppress data fetching and achieve further speedup by increasing the locality of reference as described above and enabling efficient data reference.

(Search results)
When returning search results based on the above-mentioned second distance (true distance), the following two methods, a first method and a second method, can be considered.

For example, as a first method, a search number greater than the specified search number may be searched, and when the search is completed, true distance calculation is performed to sort by distance, and the specified search number of objects may be used as the search result. In this case, the information processing device 100 sets the extended search number (also called the "second number") as the search number so as to extract a number of nodes (also called the "extended search number") greater than the specified search number (also called the "first number"), and performs a search process as shown in FIG. 11 to extract the nodes of the extended search number, i.e., the number of nodes greater than the specified search number, as neighboring candidate nodes. Then, the information processing device 100 calculates the second distance (true distance) for the neighboring candidate nodes, and extracts the first number of nodes from the neighboring candidate nodes with the shortest second distance as neighboring nodes of the search query.

Also, for example, as a second method, during a search, a second distance (true distance) may be calculated based on the first distance (approximate distance) only when a node (object) falls within the search range or the search range, and the approximate distance may be replaced with the true distance, thereby returning search results based on the true distance.

The search range here is the range defined by "r" in FIG. 11, and the search range is the range defined by "r(1+ε)" using the search range coefficient "ε" in FIG. 11. For example, when calculating the second distance (true distance) when the node is within the search range, the information processing device 100 calculates the second distance (true distance) of the node when the first distance (approximate distance) of the node is equal to or less than "r". Also, when calculating the second distance (true distance) when the node is within the search range, the information processing device 100 calculates the second distance (true distance) of the node when the first distance (approximate distance) of the node is equal to or less than "r(1+ε)".

For example, if accuracy is to be improved, the condition may be when the object falls within the search range. Also, if speed is required, the condition may be when the object falls within the search range. Note that the above is merely an example, and which of the conditions is used may be set appropriately depending on the value of the search range coefficient "ε" and the purpose of the processing.

(Vector quantization)
The information processing device 100 may perform two-stage vector quantization as disclosed in Patent Document 3. Then, the information processing device 100 may calculate the distance between the search query and each node by the following formula (1).

Here, the value on the left side of the above formula (1) indicates, for example, the squared distance between the search query and the node. Also, for example, "x" in the above formula (1) corresponds to the query. Also, for example, "y" in the above formula (1) corresponds to the node. Also, for example, "q _c (y)" on the right side of the above formula (1) indicates the representative vector (centroid) of "y". For example, when the information processing device 100 does not have vector data of the node for "y" in the above formula (1), it may use the numerical value of the centroid of the partial area to which each node belongs. Also, for example, "y-q _c (y)" indicates a residual vector. Also, for example, "q _p " on the right side of the above formula (1) indicates a predetermined quantizer (function).

Also, for example, "j" on the right side of the above formula (1) may be the number of divided spaces. For example, in the example of FIG. 1, "j" on the right side of the above formula (1) may be the number of divided spaces, "4". Also, for example, "u _j ()" on the right side of the above formula (1) indicates a partial residual vector between the vectors in parentheses. For example, the information processing device 100 may use the above formula (1) to calculate the squared distance between the query and the node in each subspace and add them up to calculate the distance between the query and the node.

1-2. Configuration of information processing system
As shown in Fig. 4, the information processing system 1 includes a terminal device 10, an information providing device 50, and an information processing device 100. The terminal device 10, the information providing device 50, and the information processing device 100 are connected to each other via a predetermined network N so as to be able to communicate with each other by wire or wirelessly. Fig. 4 is a diagram showing an example of the configuration of the information processing system according to the first embodiment. Note that the information processing system 1 shown in Fig. 4 may include a plurality of terminal devices 10, a plurality of information providing devices 50, and a plurality of information processing devices 100.

The terminal device 10 is an information processing device used by a user. The terminal device 10 accepts various operations by the user. In the following, the terminal device 10 may be referred to as a user. In other words, in the following, the user can also be read as the terminal device 10. The above-mentioned terminal device 10 is realized, for example, by a smartphone, a tablet terminal, a notebook PC (Personal Computer), a desktop PC, a mobile phone, a PDA (Personal Digital Assistant), etc.

The information providing device 50 is an information processing device that stores information for providing various information to users, etc. For example, the information providing device 50 stores object IDs based on character information, etc. collected from various external devices such as web servers. For example, the information providing device 50 is an information processing device that provides an image search service to users, etc. For example, the information providing device 50 stores various pieces of information for providing the image search service. For example, the information providing device 50 provides the information processing device 100 with vector information corresponding to an image that is the target of the image search service. In addition, the information providing device 50 transmits a query to the information processing device 100, and receives an object ID, etc. indicating an image corresponding to the query from the information processing device 100.

The information processing device 100 is a computer that provides a search service. The information processing device 100 provides a specified number of objects corresponding to a search query as search results. The information processing device 100 uses a graph in which nodes (objects) to be searched are connected by edges to provide nodes (objects) near the search query as search results. In a search process in which nodes corresponding to each of a plurality of objects are connected by edges, the information processing device 100 calculates the distance between the search query and a plurality of nodes selected according to a predetermined criterion using vector information of the plurality of nodes that have been vector quantized.

For example, when the information processing device 100 receives a query (search query) from the terminal device 10, it searches for targets (objects) similar to the search query and provides the search results to the terminal device. Also, for example, the data that the information processing device 100 provides to the terminal device may be the data itself, such as image information, or may be information for referencing corresponding data, such as a uniform resource locator (URL). Also, the search query and search target (object) may be any type of data, such as image, audio, or text data.

1-3. Configuration of information processing device
Next, the configuration of the information processing device 100 according to the first embodiment will be described with reference to Fig. 5. Fig. 5 is a diagram showing an example of the configuration of the information processing device 100 according to the first embodiment. As shown in Fig. 5, the information processing device 100 has a communication unit 110, a storage unit 120, and a control unit 130. Note that the information processing device 100 may have an input unit (e.g., a keyboard, a mouse, etc.) that accepts various operations from an administrator of the information processing device 100, and a display unit (e.g., a liquid crystal display, etc.) that displays various information.

(Communication unit 110)
The communication unit 110 is realized by, for example, a network interface card (NIC) etc. The communication unit 110 is connected to a network (for example, network N in FIG. 4 ) by wire or wirelessly, and transmits and receives information between the terminal device 10 and the information providing device 50.

(Memory unit 120)
The storage unit 120 is realized by, for example, a semiconductor memory element such as a random access memory (RAM) or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 5, the storage unit 120 according to the first embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123, and a codebook information storage unit 124.

(Object information storage unit 121)
The object information storage unit 121 according to the first embodiment stores various information related to objects. For example, the object information storage unit 121 stores an object ID and vector data. Fig. 6 is a diagram showing an example of the object information storage unit according to the first embodiment. The object information storage unit 121 shown in Fig. 6 includes items such as "object ID" and "vector information".

"Object ID" indicates identification information for identifying an object. Furthermore, "vector information" indicates vector information corresponding to an object identified by an object ID. That is, in the example of FIG. 6, vector data (vector information) corresponding to an object is registered in association with an object ID that identifies the object.

For example, in the example of Figure 6, the object (target) identified by the object ID "OB1" is associated with multi-dimensional vector information of "10, 24, 51, 2...".

The object information storage unit 121 may store various types of information depending on the purpose, not limited to the above.

(Graph information storage unit 122)
The graph information storage unit 122 according to the first embodiment stores various information related to a graph. For example, the graph information storage unit 122 stores a generated graph. Fig. 7 is a diagram illustrating an example of the graph information storage unit according to the first embodiment. The graph information storage unit 122 illustrated in Fig. 7 has items such as "node ID", "object ID", and "connection node information".

"Node ID" indicates identification information for identifying each node (object) in the graph. Also, "object ID" indicates identification information for identifying an object. Note that if the node ID and object ID are the same, the object ID is stored in "node ID", and the graph information storage unit 122 does not need to include an "object ID" item. For example, if used as an object ID and node ID, the object ID is stored in "node ID", and the graph information storage unit 122 does not need to include an "object ID" item.

Furthermore, "connection node information" indicates information about nodes (reference nodes) that can be traced from the corresponding node. For example, "connection node information" includes information such as "reference destination." "Reference destination" indicates information for identifying a reference destination (node) that is connected by an edge and can be traced from that node. That is, in the example of Figure 7, a node ID (object ID) that identifies a node is associated with a reference destination (node) that can be traced from that node by an edge and is registered. Note that "connection node information" may also include information (edge ID) for identifying an edge connected to a reference destination.

In the example of Figure 7, the node (node N1) identified by the node ID "N1" corresponds to the object (target) identified by the object ID "OB1". In addition, an edge is connected from node N1 to the node (node N4) identified by the node ID "N4", indicating that it is possible to trace from node N1 to node N4.

This also indicates that the node identified by the node ID "N2" (node N2) corresponds to the object (target) identified by the object ID "OB2". In addition, an edge is connected from node N2 to the node identified by the node ID "N6" (node N6), indicating that it is possible to trace from node N2 to node N6.

This also indicates that the node identified by the node ID "N7" (node N7) corresponds to the object (target) identified by the object ID "OB7". In addition, edges are connected from node N7 to nodes N9, N12, N54, and N85, indicating that it is possible to trace from node N2 to each of nodes N9, N12, N54, and N85.

The graph information storage unit 122 is not limited to the above, and may store various kinds of information according to the purpose. For example, the graph information storage unit 122 may store the length of the edge connecting each node (vector). In other words, the graph information storage unit 122 may store information indicating the distance between each node (vector). The graph information storage unit 122 is not limited to the above, and may store graph information using various data structures.

The graph may also include a program module that takes a query as input, searches for nodes by tracing edges in the graph, and extracts and outputs nodes similar to the query. That is, the graph may be intended to be used as a program module that performs search processing using the graph. For example, the graph GR1 may be a program that, when vector data is input as a query, extracts from the graph nodes corresponding to vector data similar to the vector data, and outputs the nodes. For example, the graph GR1 may be data used as a program module that searches for similar images corresponding to a query image. For example, the graph GR1 causes a computer to function to extract and output nodes in the graph that are similar to the query, based on the input query.

(Quantization information storage unit 123)
The quantization information storage unit 123 according to the first embodiment stores various information related to the allocation process. FIG. 8 is a diagram illustrating an example of the quantization information storage unit according to the first embodiment. In this example, the quantization information storage unit 123 has items such as "node ID", "object ID", and "quantization information".

"Node ID" indicates identification information for identifying each node (object) in the graph. Also, "object ID" indicates identification information for identifying an object. Note that if the node ID and object ID are the same, the object ID is stored in "node ID", and the quantization information storage unit 123 does not need to include an "object ID" item.

The "quantization information" indicates information on the quantized vector of each node (object). For example, the "quantization information" includes information such as "element" and "codebook ID". "Element" indicates the arrangement of the vector of the corresponding object. In the example of FIG. 8, "element" includes "#1", "#2", "#3", and "#4". In this case, the vector of each node (object) is divided into four, and each divided partial vector is quantized by the codebook. Note that the number of divisions is not limited to four, and for example, if the number of divisions is six, "element" includes "#1", "#2", "#3", "#4", "#5", and "#6". "Codebook ID" indicates information for identifying the codebook corresponding to each element (partial vector).

In the example of FIG. 8, the vector of node N9 (object OB9) indicates that of the four divided partial vectors, the first partial vector is quantized by a codebook (codebook CD12) identified by a codebook ID "CD12". Also, the vector of node N9 (object OB9) indicates that of the four divided partial vectors, the second from the top is quantized by a codebook (codebook CD23) identified by a codebook ID "CD23".

The vector of node N9 (object OB9) indicates that the third partial vector from the top of the four partial vectors is quantized by a codebook (codebook CD35) identified by a codebook ID "CD35". The vector of node N9 (object OB9) indicates that the fourth partial vector from the top (i.e., the last partial vector) of the four partial vectors is quantized by a codebook (codebook CD47) identified by a codebook ID "CD47".

The quantization information storage unit 123 may store various types of information depending on the purpose, not limited to the above.

(Codebook Information Storage Unit 124)
The codebook information storage unit 124 according to the first embodiment stores various information related to the codebook. For example, the codebook information storage unit 124 stores a codebook ID and vector information of each codebook. Fig. 9 is a diagram illustrating an example of the codebook information storage unit according to the first embodiment. In the example of Fig. 9, the codebook information storage unit 124 stores a lookup table indicating the correspondence between each codebook and a vector.

The codebook information storage unit 124 stores codebook information TB1 used to quantize the first partial vector of the four partial vectors, and codebook information TB2 used to quantize the second partial vector from the top of the four partial vectors. The codebook information storage unit 124 also stores codebook information TB3 used to quantize the third partial vector from the top of the four partial vectors, and codebook information TB4 used to quantize the fourth partial vector from the top (i.e., the last) of the four partial vectors.

In the example of FIG. 9, codebook information TB1 stores codebook information such as a codebook identified by a codebook ID "CD11" (codebook CD11) and a codebook identified by a codebook ID "CD12" (codebook CD12). For example, codebook CD11 indicates that it is associated with multidimensional vector information of "5, 13...". Also, codebook CD12 indicates that it is associated with multidimensional vector information of "27, 51...".

The codebook information storage unit 124 may store various types of information according to the purpose, not limited to the above. For example, the codebook information storage unit 124 may store information indicating the difference (distance) between each codebook and the search query.

(Control unit 130)
Returning to the explanation of Fig. 5, the control unit 130 is a controller, and is realized, for example, by a CPU (Central Processing Unit), an MPU (Micro Processing Unit), a GPU (Graphics Processing Unit), or the like, executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100 using a RAM as a working area. The control unit 130 is also a controller, and is realized, for example, by an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array).

As shown in FIG. 5, the control unit 130 has an acquisition unit 131, a generation unit 132, a search processing unit 133, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130 is not limited to the configuration shown in FIG. 5, and may be other configurations as long as they perform the information processing described below.

(Acquisition unit 131)
The acquisition unit 131 acquires various information. For example, the acquisition unit 131 acquires various information from the storage unit 120. For example, the acquisition unit 131 acquires various information from the object information storage unit 121, the graph information storage unit 122, the quantization information storage unit 123, the codebook information storage unit 124, etc. In addition, the acquisition unit 131 acquires various information from an external information processing device. The acquisition unit 131 acquires various information from the terminal device 10 and the information providing device 50.

The acquisition unit 131 acquires a graph. For example, the information processing device 100 may acquire spatial information SP1 in FIG. 1. For example, the information processing device 100 may acquire a graph from an external device such as an information providing device 50.

The acquisition unit 131 acquires a search query for multiple objects that are the target of a data search. For example, the acquisition unit 131 acquires information related to a search query QE1. For example, the acquisition unit 131 acquires a search query related to an image search. For example, the acquisition unit 131 acquires a query from the terminal device 10 used. For example, the acquisition unit 131 acquires a query from an information providing device 50 that has accepted a query from the terminal device 10 used.

(Generation unit 132)
The generating unit 132 generates various information. For example, the generating unit 132 generates various information (data) from information (data) stored in the storage unit 120. For example, the generating unit 132 generates various information from information (data) stored in the object information storage unit 121, the graph information storage unit 122, the quantization information storage unit 123, the codebook information storage unit 124, etc.

The generating unit 132 may generate a graph as shown in the graph information storage unit 122. For example, the generating unit 132 generates spatial information SP1. The generating unit 132 may also generate information on vector quantization as shown in the quantization information storage unit 123. For example, the generating unit 132 generates information on vector quantization of each object such as node N1 (object OB1). The generating unit 132 may also generate information on a codebook as shown in the codebook information storage unit 124. The generating unit 132 may generate a lookup table of the codebook. For example, the generating unit 132 generates information on a codebook such as codebook information TB1 to TB4. Note that when the information processing device 100 acquires the information shown in the graph information storage unit 122, the quantization information storage unit 123, and the codebook information storage unit 124 from an external device such as the information providing device 50, the information processing device 100 may not have the generating unit 132.

(Search Processing Unit 133)
The search processing unit 133 provides a search service related to objects. The search processing unit 133 searches for various information. The search processing unit 133 searches for various information. For example, the search processing unit 133 searches for an object by searching a graph. For example, when a query is acquired by the acquisition unit 131, the search processing unit 133 searches for an object similar to the query by searching a graph. For example, the search processing unit 133 extracts an object similar to the query by searching a graph. For example, the search processing unit 133 extracts an object similar to the query by searching a graph based on a processing procedure as shown in FIG. 11. Note that, when the information processing device 100 does not provide a search service, it does not need to have the search processing unit 133.

The search processing unit 133 selects various pieces of information in the search process. The search processing unit 133 extracts various pieces of information in the search process. The search processing unit 133 judges various pieces of information in the search process. The search processing unit 133 determines various pieces of information in the search process. The search processing unit 133 changes various pieces of information in the search process. The search processing unit 133 updates various pieces of information in the search process.

In a search process in which a group of nodes corresponding to each of a plurality of objects are connected by edges to search for nodes near the search query, the search processing unit 133 calculates the distance between the search query and a plurality of nodes selected according to a predetermined criterion using vector information of the plurality of vector-quantized nodes. The search processing unit 133 performs the calculation of the distance between the plurality of nodes and the search query in parallel and in a batch. The search processing unit 133 performs the calculation of the distance between the search query and a plurality of nodes in parallel for a batch processing number determined based on the specifications of the information processing device 100.

The search processing unit 133 calculates the distance between the multiple nodes and the search query using a codebook in which each of the multiple nodes is associated with a corresponding representative vector. The search processing unit 133 calculates the distance between the multiple nodes connected by edges from one node and the search query. The search processing unit 133 calculates the distance between the multiple nodes and the search query using node information in which reference information indicating the multiple nodes and the representative vectors associated with each of the multiple nodes is stored in association with one node.

The search processing unit 133 calculates the distance between the multiple nodes and the search query using vector information of multiple nodes, each of which is divided into multiple partial vectors by direct product quantization. The search processing unit 133 calculates the distance between the multiple nodes and the search query using multiple codebooks associated with representative vectors corresponding to vectors for each division position of the multiple partial vectors into which each of the multiple nodes is divided. The search processing unit 133 calculates the distance between the multiple nodes and the search query using node information in which reference information indicating the multiple nodes and the representative vectors associated with each of the multiple partial vectors of each of the multiple nodes is stored in association with one node.

The search processing unit 133 calculates the distance between the multiple nodes and the search query using reference information in which a list of representative vectors corresponding to each of the multiple partial vectors of each node is associated with each of the multiple nodes. The search processing unit 133 calculates the distance between the multiple nodes and the search query using reference information including transposition information in which representative vectors corresponding to each of the multiple partial vectors of each of the multiple nodes are arranged in a list for each division position, and association information indicating the corresponding position of each of the multiple nodes in the list. The search processing unit 133 calculates the distance between the multiple nodes and the search query using a codebook in which each of the multiple partial vectors of each of the multiple nodes is associated with a corresponding representative vector.

The search processing unit 133 calculates a second distance that is not vector quantized, unlike the first distance, which is a vector quantized distance, for a specific node among the nodes that are processed in the search process. The search processing unit 133 extracts a second number of nodes, which is a number greater than the first number of nodes to be extracted as nodes near the search query in the search process, as neighboring candidate nodes, and calculates the second distance for the neighboring candidate nodes. The search processing unit 133 extracts the first number of nodes from the neighboring candidate nodes with the shortest second distance as nodes near the search query.

The search processing unit 133 calculates the second distance for nodes whose first distance is within a predetermined threshold. The search processing unit 133 calculates the second distance for nodes within a search range that indicates the target range to be extracted as nearby nodes. The search processing unit 133 calculates the second distance for nodes within a search range that indicates the target range of the search process.

(Providing Unit 134)
The providing unit 134 provides various information. For example, the providing unit 134 transmits various information to the terminal device 10 or the information providing device 50. For example, the providing unit 134 provides an object ID corresponding to a search query as a search result. The providing unit 134 transmits the search result to the terminal device 10. The providing unit 134 provides the object ID searched for by the search processing unit 133 to the terminal device 10 as a search result corresponding to the search query.

The providing unit 134 may also provide the object ID searched for by the search processing unit 133 to the information providing device 50. For example, the providing unit 134 provides the object ID extracted by the search processing unit 133 through a search to the information providing device 50. The providing unit 134 provides the object ID extracted by the search processing unit 133 to the information providing device 50 as information indicating a vector corresponding to the query.

[1-4. Information processing flow]
Next, a procedure of information processing by the information processing system 1 according to the first embodiment will be described with reference to Fig. 10. Fig. 10 is a flowchart showing an example of information processing according to the first embodiment.

As shown in FIG. 10, the information processing device 100 acquires a search query for multiple objects to be subjected to a data search (step S101). In the example of FIG. 1, the information processing device 100 acquires a search query QE1.

Then, in a search process in which a group of nodes corresponding to each of a plurality of objects is connected by edges to search for nodes near the search query, the information processing device 100 calculates the distance between the search query and a plurality of nodes selected according to a predetermined criterion using vector information of the plurality of vector-quantized nodes (step S102). In the example of FIG. 1, the information processing device 100 calculates the distance between the plurality of nodes N9, N12, N54, and N85 and the search query QE1 using vector information of the plurality of vector-quantized nodes N9, N12, N54, and N85.

[1-5. Search processing example]
Here, an example of the search process according to the first embodiment will be described with reference to FIG. 11 as an example. FIG. 11 is a flowchart showing an example of the search process according to the first embodiment. The search process described below is performed by the search processing unit 133 of the information processing device 100. In addition, the object referred to below may be read as a node. Note that, in the following, the information processing device 100 (search processing unit 133) performs the search process. Note that, when a search service is not provided, the information processing device 100 does not need to have the search processing unit 133. The search query in the process described below may be an additional node, a target node, an object designated by a user, or the like.

Here, the neighborhood object set N(G, y) is a set of nearby objects associated with the edge attached to node y. "G" may be a predetermined graph data (e.g., graph GR1 shown in spatial information SP1). For example, the information processing device 100 executes a k-nearest neighbor search process.

For example, the information processing device 100 sets the radius r of the hypersphere to ∞ (infinity) (step S300) and extracts a subset S from the existing object set (step S301). For example, the information processing device 100 may extract an object (node) selected as the root node as the subset S. Also, for example, the hypersphere is a virtual sphere indicating the search range. Note that the objects included in the object set S extracted in step S301 are also included in the initial set of the object set R of the search result at the same time.

Next, the information processing device 100 extracts, from among the objects included in the object set S, an object that is the shortest distance from the search query object y, and sets the object as object s (step S302). For example, if the object (node) selected as the root node is the only element of S, the information processing device 100 extracts the root node as object s. Next, the information processing device 100 excludes object s from the object set S (step S303).

Next, the information processing device 100 determines whether the distance d(s, y) between object s and object y exceeds r(1+ε) (step S304). Here, ε is an extension factor, and r(1+ε) is a value indicating the radius of the search range (only nodes within this range are searched for. Accuracy can be improved by making it larger than the search range). If the distance d(s, y) between object s and object y exceeds r(1+ε) (step S304: Yes), the information processing device 100 outputs the object set R as a neighborhood object set of object y (step S305) and ends the process.

If the distance d(s, y) between object s and search query object y does not exceed r(1+ε) (step S304: No), the information processing device 100 selects one object that is not included in object set C from among the objects that are elements of the neighborhood object set N(G, s) of object s, and stores the selected object u in object set C (step S306). Object set C is provided for convenience in order to avoid duplicate searches, and is set to an empty set at the start of processing.

Next, the information processing device 100 determines whether the distance d(u, y) between the objects u and y is less than or equal to r(1+ε) (step S307). If the distance d(u, y) between the objects u and y is less than or equal to r(1+ε) (step S307: Yes), the information processing device 100 adds the object u to the object set S (step S308). If the distance d(u, y) between the objects u and y is not less than or equal to r(1+ε) (step S307: No), the information processing device 100 performs the determination (processing) of step S309.

Next, the information processing device 100 determines whether the distance d(u, y) between the objects u and y is less than or equal to r (step S309). If the distance d(u, y) between the objects u and y exceeds r (step S309: No), the information processing device 100 performs the determination (processing) of step S315. In other words, if the distance d(u, y) between the objects u and y is not less than or equal to r, the information processing device 100 performs the determination (processing) of step S315.

If the distance d(u, y) between object u and object y is equal to or less than r (step S309: Yes), the information processing device 100 adds object u to object set R (step S310). Then, the information processing device 100 determines whether the number of objects included in object set R exceeds ks (step S311). The predetermined number ks is a natural number that is determined arbitrarily. For example, ks may be the number of searches or the number of objects to be extracted. Also, for example, when no upper limit is set on the number of objects to be extracted in a range search or the like, ks may be set to infinity. For example, ks may be 4. If the number of objects included in object set R does not exceed ks (step S311: No), the information processing device 100 performs the determination (processing) of step S313.

If the number of objects included in object set R exceeds ks (step S311: Yes), the information processing device 100 excludes from object set R the object that is the longest (farthest) distance from object y among the objects included in object set R (step S312).

Next, the information processing device 100 determines whether the number of objects included in the object set R matches ks (step S313). If the number of objects included in the object set R does not match ks (step S313: No), the information processing device 100 performs the determination (processing) of step S315. If the number of objects included in the object set R matches ks (step S313: Yes), the information processing device 100 sets the distance between the object y and the object that is the longest (farthest) distance from the object y among the objects included in the object set R to a new r (step S314).

Then, the information processing device 100 determines whether or not all objects that are elements of the neighborhood object set N(G,s) of object s have been selected and stored in the object set C (step S315). If all objects that are elements of the neighborhood object set N(G,s) of object s have not been selected and stored in the object set C (step S315: No), the information processing device 100 returns to step S306 and repeats the process.

When all objects that are elements of the neighborhood object set N(G,s) of object s have been selected and stored in the object set C (step S315: Yes), the information processing device 100 determines whether the object set S is an empty set (step S316). If the object set S is not an empty set (step S316: No), the information processing device 100 returns to step S302 and repeats the process. Also, if the object set S is an empty set (step S316: Yes), the information processing device 100 outputs the object set R and ends the process (step S317). For example, the information processing device 100 may select an object (node) included in the object set R as a neighborhood node corresponding to the added node (input object y). For example, the information processing device 100 may extract (select) an object (node) included in the object set R as a neighborhood node corresponding to the target node (input object y). Also, for example, the information processing device 100 may provide the object (node) included in the object set R to the terminal device or the like that performed the search as a search result corresponding to the search query (input object y).

2. Second embodiment
From here, the second embodiment will be described. In the second embodiment, nearby objects are grouped by clustering or the like, and each group (hereinafter also referred to as "blob") is subjected to a collective distance calculation. That is, in the second embodiment, collective distance calculation is performed in units of blobs. Note that the description of the same points as in the first embodiment will be omitted as appropriate. In the second embodiment, the information processing system 1 has an information processing device 100A instead of the information processing device 100.

[2-1. Information Processing]
First, an overview of information processing according to the second embodiment will be described with reference to Fig. 12. Fig. 12 is a diagram showing an example of information processing according to the second embodiment.

In the example of FIG. 12, it is assumed that the information processing device 100A has already acquired a graph GR21 as shown in spatial information SP21. For example, the spatial information SP21 in FIG. 1 may be a Euclidean space. For example, the spatial information SP21 corresponds to the number of dimensions of the vector of the object, and is a multidimensional space of 100 dimensions, 1000 dimensions, etc. Note that, in the example of FIG. 12, for the sake of simplicity, the explanation will be based on a diagram in which direct product quantization has not been performed, but direct product quantization of vectors (space) may also be performed as in FIG. 1.

First, each piece of information shown in FIG. 12 will be explained. The dotted lines connecting the white circles (◯), which are nodes in the spatial information SP21 in FIG. 12, indicate edges that connect the nodes. As in FIG. 1, FIG. 12 shows an example of an undirected edge, but the edges of the graph GR21 are not limited to undirected edges and may be directed edges. Note that the nodes and edges are the same as in FIG. 1, so a detailed explanation will be omitted.

In the spatial information SP21 in Figure 12, the areas surrounded by straight lines are nearby objects grouped together by clustering or the like, and the areas are called blobs. In the example shown below, the blob is the processing unit for the batch distance calculation. Figure 12 shows a case where the objects are clustered into 10 areas (blobs), blobs BL1 to BL10. For example, blob BL1 indicates that it is a blob to which multiple nodes, such as nodes N7, N9, N85, and N126, belong. The black dots in blobs BL1 to BL10 indicate the centroids (representative vectors) of each blob.

Note that the blobs BL1 to BL10 are generated using various techniques related to clustering, etc., as appropriate. For example, the clustering for classifying into blobs may be k-means clustering. Also, for example, the clustering for classifying into blobs may be performed by replacing the centroids with the objects closest to each centroid before performing the next iteration, rather than using the centroids obtained from the center coordinates (average) of each cluster in one iteration (assignment) of k-means in the next iteration. In this case, the centroid of the final cluster obtained by k-means becomes an existing object, that is, a node. This increases the tendency for the clusters (blobs) and the edges (neighboring nodes) of each node to match, further improving search performance.

In the example of FIG. 12, the information processing device 100A performs search processing using information on multiple blobs BL1 to BL10 that have been classified by clustering multiple nodes (objects) as shown in the spatial information SP21.

Now, the search process targeting the search query QE2 will be described. First, the information processing device 100A acquires the search query QE2 (step S21). For example, the information processing device 100A acquires the search query QE2 from the terminal device 10 (see FIG. 4) used by the user.

Then, the information processing device 100A calculates the distance between the vector of the search query QE2 and the vector of the codebook. Although not shown, when the direct product quantization is not performed, the information processing device 100A calculates the distance (difference) between the vector of the search query QE2 and the vector of the codebook for quantizing the entire vector. Then, the information processing device 100A stores the distance (difference) between the vector of the search query QE2 and the vector of each codebook as the codebook information TB21 in association with information for identifying each codebook. Note that, when the direct product quantization is performed, the information processing device 100A calculates the distance (difference) between each sub-vector of the search query QE2 and the vector of each codebook, as shown in the codebook information TB1 to TB4 in FIG. 2, in the same manner as in FIG. 1. Note that the calculation of the distance between the vector of the search query and the vector of the codebook is the same as in FIG. 1, FIG. 2, etc., and therefore a detailed description is omitted.

The information processing device 100A executes a search process targeting the search query QE2 (step S22). The information processing device 100A performs a search process as shown in FIG. 16 using the graph GR21 targeting the search query QE2, thereby obtaining search results for the search query QE2. Details of the search process shown in FIG. 16 will be described later. The information processing device 100A performs a search process targeting the search query QE2, thereby extracting the number of search nodes as nodes in the vicinity of the search query QE2.

In a search process targeting search query QE2, information processing device 100A selects a specific node from among the nodes as a node (starting node) that will be the starting point of a search of graph GR21. In the example of FIG. 12, information processing device 100A selects node N9 as the starting node. In the example of FIG. 12, information processing device 100A starts a search process targeting node N9, for example.

Here, in the search process targeting the search query QE2, the information processing device 100A calculates in parallel the distance between the search query and multiple nodes belonging to the blob to which the node to be processed belongs (step S23). In FIG. 12, as shown in the batch processing information LT2, the information processing device 100A calculates in parallel the distance between the search query QE2 and nodes N7, N9, N85, N126, etc., which are nodes belonging to the blob BL1 to which the node N9 to be processed belongs.

The information processing device 100A calculates the distance between each of the nodes N7, N9, N85, and N126 and the search query QE2 by using the distance between each codebook indicated in the codebook information TB21 and the search query QE2. For example, the information processing device 100A refers to the codebook information TB21 and calculates the distance of the codebook corresponding to the vector of the node N7 as the distance between the node N7 and the search query QE2. Note that the distance calculation when direct product quantization is performed is similar to that in Figures 1 and 2, and therefore a detailed description will be omitted.

The batch processable unit is determined based on the specifications of the information processing device 100A, as in the case of the information processing device 100. For example, if the number of nodes that the information processing device 100A can process in a batch by SIMD (the batch processable unit) is "4", the distance is calculated in parallel for four nodes, as in FIG. 1. For example, the information processing device 100A calculates the distance between each of the nodes N7, N9, N85, and N126 and the search query QE2 in a batch by parallelizing the SIMD calculation. As a result, the information processing device 100A can speed up the distance calculation by parallelizing the distance calculation, and can enable efficient search processing. In addition, the information processing device 100A uses the graph GR21 to trace the nodes (e.g., nodes N12 and N64) to which the edges from the node N7 are connected, and performs a batch distance calculation for the blobs (e.g., blobs BL2 and BL3) to which these nodes belong, and performs search processing. In addition, the information processing device 100A prevents the same blob from being repeatedly subjected to batch distance calculations during search processing, as will be described in detail below.

For simplicity's sake, FIG. 12 shows a case where distances are calculated in parallel for four nodes, but the number of nodes to be parallelized is determined based on the specifications of the information processing device 100A. This is also the same as in FIG. 1, FIG. 2, etc., so a detailed description will be omitted. The information processing device 100A may also use transposed data, as in the example shown in FIG. 3.

As described above, the information processing device 100A can enable efficient search processing by calculating the approximate distance (second distance) between the vector of each vector-quantized node and the search query, and performing search processing using the second distance. Furthermore, the information processing device 100A can enable efficient search processing by collectively performing distance calculations for a number of nodes that can be parallelized. As described above, the information processing device 100A can enable efficient search processing by collectively calculating blobs as a unit of batch processing.

In the search process, the information processing device 100A traverses the graph GR21 and performs the above-mentioned process on the nodes to be processed, thereby extracting the number of searched nodes as nodes in the vicinity of the search query QE2. For example, the information processing device 100A, like the information processing device 100, obtains search results by either the first method or the second method described above.

The above-described process is merely an example, and the information processing device 100A may perform search processing using various information and methods for efficient search processing. Each item in this regard will be described in detail. For example, the information processing device 100A may perform clustering and generate blobs so that the number of nodes belonging to each blob is a number that the information processing device 100 can process collectively by SIMD (a unit that can be processed collectively).

The information processing device 100A may also use information about blobs to prevent duplicated processing. The information processing device 100A may have a blob distance calculation flag (hereinafter also simply referred to as a "flag") indicating whether or not a distance calculation has been performed for each blob, and a table indicating which blob each object belongs to. In this case, the information processing device 100A may use the flag to manage whether or not each blob has been processed. For example, the information processing device 100A may use a table to identify the blob to which the node belongs just before processing the neighboring nodes one by one, determine whether or not the blob has been subjected to a collective distance calculation using the flag, and if not, perform collective calculation and process each node. This point will also be described in FIG. 15 and FIG. 16. This allows the information processing device 100A to prevent duplicated processing.

2-2. Configuration of information processing device
Next, the configuration of the information processing device 100A according to the second embodiment will be described with reference to Fig. 13. Fig. 13 is a diagram showing an example of the configuration of the information processing device according to the second embodiment. As shown in Fig. 13, the information processing device 100A has a communication unit 110, a storage unit 120A, and a control unit 130A. Note that in the information processing device 100A, the description of the same points as those in the information processing device 100 will be omitted as appropriate.

(Memory unit 120A)
The storage unit 120A is realized by, for example, a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 13, the storage unit 120A according to the second embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123A, a codebook information storage unit 124, and a blob information storage unit 125.

(Quantization information storage unit 123A)
The quantization information storage unit 123A according to the second embodiment stores various information related to the allocation process. FIG. 14 is a diagram illustrating an example of the quantization information storage unit according to the second embodiment. In this example, the quantization information storage unit 123A has items such as "node ID", "object ID", "blob ID", and "quantization information".

"Node ID" indicates identification information for identifying each node (object) in the graph. Also, "object ID" indicates identification information for identifying an object. Note that if the node ID and object ID are the same, the object ID is stored in "node ID", and the quantization information storage unit 123A does not need to include an "object ID" item.

"Blob ID" indicates information for identifying the blob to which the node (object) belongs.

Furthermore, "quantization information" indicates information on the quantized vector of each node (object). For example, "quantization information" includes information such as "element" and "codebook ID". "Element" indicates the arrangement of the corresponding object in the vector. In the example of Figure 14, "element" indicates the case where "#1", "#2", "#3", and "#4" are included. In this case, the vector of each node (object) is divided into four, and each divided partial vector is quantized by the codebook.

In the example of FIG. 14, node N1 (object OB1) belongs to a blob (blob BL9) identified by blob ID "BL9". For example, if a vector is divided into four by product quantization, the quantization information of node N1 stores information similar to the four codebooks shown in the quantization information of node N1 shown in FIG. 8. Also, for example, if product quantization is not performed, the quantization information of node N1 stores information indicating one codebook for quantizing the vector of node N1.

The quantization information storage unit 123A may store various types of information depending on the purpose, not limited to the above.

(Blob information storage unit 125)
The blob information storage unit 125 according to the second embodiment stores information about blobs. For example, the blob information storage unit 125 stores various information for identifying objects associated with each blob. Fig. 15 is a diagram illustrating an example of the blob information storage unit according to the second embodiment. In the example of Fig. 15, the blob information storage unit 125 includes items such as "blob ID", "node ID", and "vector information".

"Blob ID" indicates identification information for identifying a blob. Furthermore, "Node ID" indicates a node (object) associated with the blob identified by the blob ID. "Vector information" indicates vector information of the blob. For example, "vector information" indicates a vector corresponding to the centroid of the blob.

In the example shown in FIG. 15, the nodes (objects) associated with the blob (blob BL1) identified by the blob ID "BL1" are nodes N7, N9, N85, N126, etc. This indicates that multi-dimensional vector information of "51, 4, 102, 33..." is associated with blob BL1.

It also indicates that the nodes (objects) associated with the blob (blob BL9) identified by the blob ID "BL9" are nodes N1, N4, N5, etc. It indicates that multi-dimensional vector information of "12, 55, 12, 6..." is associated with blob BL9.

The blob information storage unit 125 may store various information according to the purpose, without being limited to the above. The blob information storage unit 125 may store a flag indicating whether each blob has been processed for distance calculation. For example, the blob information storage unit 125 sets the flag value of each blob to either a value indicating that it has not been processed as a target for distance calculation (also called an "unprocessed flag value") or a value indicating that it has been processed as a target for distance calculation (also called a "processed flag value"). For example, at the start of the search process, the blob information storage unit 125 sets the flag value of each blob to a value indicating that distance calculation for that blob has not been processed (e.g., 0), and changes the flag value of the blob that has been the target of the distance calculation to a value indicating that distance calculation has been processed (e.g., 1).

For example, information processing device 100A refers to the flag value of the blob being processed and determines whether or not to perform a batch distance calculation process for that blob. Information processing device 100A refers to the flag value of each blob, and if the flag value of that blob is an unprocessed flag value, it determines that the blob has not yet been subjected to batch distance calculation and performs a batch distance calculation for the nodes belonging to that blob. On the other hand, if the flag value of that blob is a processed flag value, information processing device 100A determines that the blob has already been subjected to batch distance calculation and does not perform a batch distance calculation for the nodes belonging to that blob.

(Control unit 130A)
Returning to the explanation of Fig. 13, the control unit 130A is a controller, and is realized, for example, by a CPU, an MPU, a GPU, etc., executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100A using a RAM as a working area. The control unit 130A is also a controller, and is realized, for example, by an integrated circuit such as an ASIC or an FPGA.

As shown in FIG. 13, the control unit 130A has an acquisition unit 131, a generation unit 132A, a search processing unit 133A, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130A is not limited to the configuration shown in FIG. 13, and may be other configurations as long as they perform the information processing described below.

(Generation unit 132A)
The generating unit 132A generates various types of information in the same manner as the generating unit 132.

The generating unit 132A may generate information related to vector quantization as shown in the quantization information storage unit 123. For example, the generating unit 132 generates information indicating that node N1 (object OB1) belongs to blob BL9. The generating unit 132 may also generate information related to blobs as shown in the blob information storage unit 125. For example, the generating unit 132 generates information indicating that nodes N7, N9, N85, N126, etc. belong to blob BL1. Note that when the information processing device 100 acquires the information shown in the graph information storage unit 122, the quantization information storage unit 123A, the codebook information storage unit 124, and the blob information storage unit 125 from an external device such as the information providing device 50, the information processing device 100 does not need to have the generating unit 132A.

(Search processing unit 133A)
The search processing unit 133A performs various processes related to the search process, similar to the search processing unit 133.

In a search process that searches for nodes near the search query, the search processing unit 133A uses information on multiple blobs into which multiple objects are classified to calculate the distance between the search query and multiple nodes belonging to one blob, using vector information of multiple vector-quantized nodes. The search processing unit 133A calculates the distance between the multiple nodes and the search query in parallel and performs it all at once. The search processing unit 133A performs parallel calculations of the distance between the search query and multiple nodes for a batch processing number determined based on the specifications of the information processing device 100A.

The search processing unit 133A calculates the distance between the search query and multiple nodes that belong to a blob adjacent to the blob to which the search query applies. The search processing unit 133A calculates the distance between the search query and multiple nodes in a search process that searches for nodes near the search query using a graph in which multiple nodes are connected by edges. The search processing unit 133A calculates the distance between the search query and multiple nodes that belong to a blob to which a connecting node connected by an edge from a target node that is the processing target in the search process belongs.

The search processing unit 133A calculates the distance between the search query and multiple nodes that belong to a blob other than the blob to which the target node belongs. The search processing unit 133A calculates the distance between the search query and multiple nodes in a search process that searches for nodes near the search query using a blob graph in which each of the multiple nodes is connected to a blob other than the blob to which each of the multiple nodes belongs. The search processing unit 133A calculates the distance between the search query and multiple nodes in a search process that searches for nodes near the search query using a blob graph that is a converted graph generated by connecting an edge from one node to a blob other than the blob to which the one node belongs, which is a blob to which a node connected by an edge from one of the multiple nodes belongs in a graph before conversion in which multiple nodes are connected by edges.

The search processing unit 133A calculates the distance between the search query and multiple nodes belonging to a blob, which is a blob connected by edges from a target node to be processed in the search process. The search processing unit 133A determines whether to process a blob using information indicating a processed blob, which is a blob that has already been processed. If the blob is a processed blob, the search processing unit 133A determines that the blob is not to be processed.

The search processing unit 133A calculates a second distance that is not vector quantized, unlike the first distance, which is a vector quantized distance, for a specific node among the nodes that are processed in the search process. The search processing unit 133A extracts a second number of nodes, which is a number greater than the first number of nodes to be extracted as nodes near the search query in the search process, as neighboring candidate nodes, and calculates the second distance for the neighboring candidate nodes. The search processing unit 133A extracts the first number of nodes from the neighboring candidate nodes with the shortest second distance as nodes near the search query.

The search processing unit 133A calculates the second distance for nodes whose first distance is within a predetermined threshold. The search processing unit 133A calculates the second distance for nodes within a search range that indicates the target range to be extracted as nearby nodes. The search processing unit 133A calculates the second distance for nodes within a search range that indicates the target range of the search process.

[2-3. Search processing example]
Here, an example of the search process according to the second embodiment will be described with reference to FIG. 16. FIG. 16 is a flowchart showing an example of the search process according to the second embodiment. The search process described below is performed by the search processing unit 133A of the information processing device 100A. Note that the description of the same points as those in the first embodiment, such as FIG. 11, will be omitted as appropriate. For example, in FIG. 16, the same step numbers are used to denote the same points as those in FIG. 11, and the description will be omitted as appropriate.

Here, the neighborhood object set N(G, y) is a set of nearby objects associated by edges attached to node y. "G" may be a predetermined graph data (e.g., graph GR21 shown in spatial information SP21). For example, the information processing device 100A executes a k-nearest neighbor search process.

For example, the search process shown in FIG. 16 differs from the search process shown in FIG. 11 in that the process shown in step S304a is performed after step S304. In this way, when the search process shown in FIG. 16 reaches a blob that has not yet been accessed in a normal graph search, it calculates the distance between the query and the objects (nodes) in that blob all at once, and processes each node.

Specifically, in the search process of FIG. 16, if the information processing device 100A has not yet performed distance calculation for the blob to which the object s belongs, it executes all of the following (four processes shown following the "-" in step S304a in FIG. 16, hereinafter referred to as "first process" to "fourth process") (step S304a). In step S304a, the information processing device 100A executes a process of calculating the distance of the objects in the blob at once (first process). Also, in step S304a, the information processing device 100A executes a process of setting the distance calculation flag of the blob (second process). Also, in step S304a, the information processing device 100A executes a process of storing all objects in the blob for which the collective distance calculation has been performed in C (third process). Also, in step S304a, the information processing device 100A executes a process of performing the processes from step S307 to step S314 one by one, with all objects in the blob as u (fourth process). After that, the information processing device 100A performs the processes from step S306 onwards.

2-4. Modified Examples
From here, a modified example will be described. In the modified example of the second embodiment, a graph including the concept of blobs may be used. For example, in the modified example of the second embodiment, a graph in which the reference destination of an edge from a node is a blob may be used. Note that the description of the same points as in the first and second embodiments will be omitted as appropriate. The information processing device 100A according to the modified example has a graph information storage unit 122A instead of the graph information storage unit 122.

[2-4-1. Information processing]
First, an overview of information processing according to the modified example will be described with reference to Fig. 17. Fig. 17 is a diagram showing an example of information processing according to the modified example.

The information processing device 100A converts the graph GR21, in which nodes are connected by edges, into a graph GR31 in which the reference destinations of the edges from the nodes are blobs (step S31). That is, as shown in FIG. 17, the information processing device 100A generates the graph GR31, which is a graph in which the concept of blobs has been introduced (a graph for blobs), from the graph GR21, which is a normal graph.

In the example of FIG. 17, the information processing device 100A generates a graph GR31 including directed edges from nodes to blobs as shown in the spatial information SP31. Note that in graph GR31, edges between each node are deleted, and graph GR31 includes directed edges from nodes to blobs, but does not include edges between nodes. The arrow line shown in FIG. 17 indicates a directed edge from the node at the origin of the arrow to the blob at the end of the arrow. In other words, the arrow line shown in FIG. 17 indicates a directed edge with the node at the origin of the arrow as the reference source and the blob at the end of the arrow as the reference destination. For example, FIG. 17 indicates that edges are connected from node N1 to two blobs, blob BL8 and blob BL10.

For example, the information processing device 100A converts the edges of each node from edges to connecting nodes (nearby nodes) to edges to the blobs to which the connecting nodes belong. The information processing device 100A does not generate edges to the blobs to which each node itself belongs. In the example of FIG. 17, the information processing device 100A does not generate an edge from node N9 to blob BL1 and an edge from node N126 to blob BL1 because node N9 and node N126 belong to the same blob BL1. On the other hand, in the example of FIG. 17, the information processing device 100A generates an edge from node N9 to blob BL4 and an edge from node N18 to blob BL1 because node N9 and node N18 belong to different blobs BL1 and BL4.

In the example of FIG. 17, the information processing device 100A performs search processing using a graph GR31 including directed edges from nodes (objects) to blobs, as shown in the spatial information SP31. For example, the information processing device 100A performs search processing as shown in FIG. 19 using the graph GR21 for the search query QE2, thereby obtaining search results for the search query QE2. Details of the search processing shown in FIG. 19 will be described later. Note that the search processing in FIG. 17 is common to FIG. 12 in that it performs search processing using the concept of blobs, and is similar to the search processing shown in FIG. 12 except for the processing related to edges.

2-4-2. Graph
Next, an overview of a graph according to a modified example will be described with reference to FIG. 18. FIG. 18 is a diagram showing an example of a graph information storage unit according to a modified example. For example, the graph information storage unit 122A shown in FIG. 18 stores a graph in which the concept of blobs is introduced (a graph for blobs). The graph information storage unit 122A shown in FIG. 18 has items such as "node ID", "object ID", and "blob information". Thus, the graph information storage unit 122A according to the modified example differs from the graph information storage unit 122 in FIG. 7 in that it has "blob information" instead of "connection node information". Note that the description of the same points as those of the graph information storage unit 122 in FIG. 7 will be omitted as appropriate.

Furthermore, "blob information" indicates information about blobs (reference blobs) that can be traced from the corresponding node. For example, "blob information" includes information such as "reference." "Reference" indicates information for identifying a reference (blob) that is connected by an edge and can be traced from the node. That is, in the example of Figure 18, a node ID (object ID) that identifies a node is associated with a reference (blob) that can be traced from the node by an edge and is registered. Note that "blob information" may also include information for identifying an edge connected to a reference (edge ID), etc.

In the example of FIG. 18, a node (node N1) identified by node ID "N1" corresponds to an object (target) identified by object ID "OB1". In addition, an edge is connected from node N1 to a blob (blob BL8) identified by blob ID "BL8", indicating that blob BL8 can be traced from node N1. In addition, an edge is connected from node N1 to a blob (blob BL10) identified by blob ID "BL10", indicating that blob BL10 can be traced from node N1.

This also shows that the node identified by node ID "N2" (node N2) corresponds to the object (target) identified by object ID "OB2". In addition, an edge is connected from node N2 to a blob identified by blob ID "BL5" (blob BL5), indicating that blob BL5 can be traced from node N1.

The graph information storage unit 122A may store various types of information depending on the purpose, not limited to the above.

The graph may also include a program module that takes a query as input, searches for nodes by tracing edges in the graph, and extracts and outputs nodes similar to the query. That is, the graph may be intended to be used as a program module that performs search processing using the graph. For example, the graph GR31 may be a program that, when vector data is input as a query, extracts from the graph nodes corresponding to vector data similar to the vector data, and outputs the nodes. For example, the graph GR31 may be data used as a program module that searches for similar images corresponding to a query image. For example, the graph GR31 causes a computer to function to extract and output nodes in the graph that are similar to the query, based on the input query.

[2-4-3. Search processing example]
From here, an example of a search process according to the modified example will be described with reference to FIG. 19. FIG. 19 is a flowchart showing an example of a search process according to the modified example. The search process described below is performed by the search processing unit 133A of the information processing device 100A. Note that the description of the same points as those in the first embodiment or the second embodiment, such as those in FIG. 11 and FIG. 16, will be omitted as appropriate. For example, in FIG. 19, the same step numbers will be used to denote the same points as those in FIG. 11, and the description will be omitted as appropriate.

19, set N(G,y) is a set of blobs associated with node y by an edge, which is different from the search process in FIG. 11 and FIG. 16. In FIG. 19, N(G,s) and C are blob sets. That is, the "nearby object set N" in FIG. 11 is replaced with "blob set N" in FIG. 19, and the "object set C" in FIG. 11 is replaced with "blob set C" in FIG. 19. In addition, the word "object" in the process related to the above change to blobs is replaced with "blob" as appropriate. "G" may be graph (blob graph) data in which the concept of blobs is introduced (for example, graph GR31 shown in spatial information SP31, etc.). For example, the information processing device 100A executes k-nearest neighbor search processing.

For example, in the search process shown in Figure 19, the process of step S306 is changed from Figure 11 as follows. In the search process of Figure 19, the information processing device 100A selects one blob from N(G, s) that is not included in blob set C, stores the selected blob in blob set C, calculates the objects in the blob all at once, and sets this set to B (also called "set B of objects in target blob") (step S306).

The search process shown in FIG. 19 also differs from the search process shown in FIG. 11 in that the process shown in step S306a is performed after step S306. Specifically, in the search process in FIG. 19, the information processing device 100A selects one object u from the object set B in the target blob (step S306a). Thereafter, the information processing device 100A performs the processes from step S307 onwards.

The search process shown in FIG. 19 also differs from the search process shown in FIG. 11 in that the process shown in step S314a is performed before step S315. Specifically, in the search process in FIG. 19, the information processing device 100A determines whether or not all objects have been selected from the object set B within the target blob (step S314a).

If all objects have been selected from set B of objects in the target blob (step S314a: Yes), the information processing device 100A performs the process of step S315. On the other hand, if all objects have not been selected from set B of objects in the target blob (step S314a: No), the information processing device 100A returns to step S306a and repeats the process.

2-4-4. Other examples of generation processing
In the above example, a case has been shown in which the edge of each node is converted from an edge to a connecting node to an edge to a blob to which the connecting node belongs to generate a blob graph, but the information processing device 100A may generate a blob graph using various information as appropriate. For example, the information processing device 100A may generate a blob graph using a neighborhood search index (also simply called an "index") that searches multiple objects. Note that explanations of points similar to those described above will be omitted as appropriate.

An example of generating a graph for blobs will be described with reference to FIG. 20. FIG. 20 is a diagram showing another example of information processing according to a modified example. Note that, although a graph is used as an example of an index below, the index may be any type of index as long as it searches multiple objects. For example, the index may be an index that uses a description related to hash such as a hash table (hash index), an index that has a tree structure (tree index), etc.

In addition, information indicating an object or a node corresponding to that object (also called an "object node") may be referred to as first information, and information used to classify multiple objects may be referred to as second information.In addition, information indicating a blob may be referred to as third information, and a graph in which object nodes are connected by edges may be referred to as fourth information. For example, graph GR21 in FIG. 20 corresponds to fourth information, in which object nodes such as node N1 are connected by edges.In addition, graph GR31 in FIG. 17 and graph GR32 in FIG. 20 are blob graphs (also called "group graphs") in which object nodes and blobs are connected by edges, unlike fourth information.In other words, a group graph is a graph in which edges are connected from object nodes to blobs, and the object nodes are the reference source and the blobs (groups) are the reference destination.

The information processing device 100A uses the graph GR21 in which object nodes are connected by edges as an index (fourth information) to generate a graph GR32, which is a group graph in which the reference destination of an edge from an object node is a blob (step S41). In FIG. 20, the information processing device 100A generates a graph GR32 that includes directed edges from nodes to blobs, as shown in the spatial information SP32.

For example, the information processing device 100A selects one object from a plurality of objects, searches for nearby objects of the one object using the graph GR21, and generates the graph GR32 by a connection process that connects edges from one object node corresponding to the one object to other groups to which the nearby objects belong. For example, the information processing device 100A randomly selects one object from a plurality of objects, and performs a connection process on the selected one object to generate the graph GR32.

For example, the information processing device 100A performs the following processes (1-1) to (1-4) to generate the graph GR32. Note that the term "object" may be interpreted as a node corresponding to the object.

(1-1): Get Object NX at random (select)
(1-2): Search for k neighboring objects of object NX. (1-3): Obtain the blob to which each neighboring object belongs. (1-4): Generate an edge from object NX to the obtained blob.

For example, in process (1-1), the information processing device 100A randomly acquires one object NX from multiple objects stored in the object information storage unit 121.

For example, in process (1-2), the information processing device 100A performs a search process as shown in FIG. 11 using the graph GR21 with the object NX as the target (query), thereby extracting k objects as objects near the object NX.

For example, in process (1-3), the information processing device 100A refers to the blob information stored in the blob information storage unit 125 and obtains the blob associated with the nearby object (node) of object NX.

For example, in process (1-4), the information processing device 100A generates an edge from the object NX to the acquired blob. For example, the information processing device 100A generates the graph GR32 by associating information indicating the acquired blob with the object NX in the quantization information storage unit 123A.

For example, the information processing device 100A repeats the above processes (1-1) to (1-4) until there are no more objects to be processed, and generates the graph GR32. Note that, if the blobs indicated in the spatial information SP21 are generated by search, the search results when generating the blobs may be reused to generate the graph GR32. Note that an example of generating blobs by search will be described later.

For example, the information processing device 100A performs search processing using a graph GR32 that includes directed edges from nodes (objects) to blobs, as shown in the spatial information SP32. For example, the information processing device 100A performs search processing as shown in FIG. 19 using the graph GR32 for the search query QE2, thereby obtaining search results for the search query QE2.

In addition, in the above example, a case where blobs are generated by clustering has been shown, but blobs may be generated by various methods other than clustering. For example, the information processing device 100A may generate information indicating a blob (third information) using second information such as an index.

The information processing device 100A generates third information indicating a blob using a graph GR21 as an index, as shown in FIG. 21. FIG. 21 is a diagram showing an example of a process for generating blob information. Spatial information SP20 in FIG. 21 shows the state before the blob information in the spatial information SP21 is generated, and the graph GR21 in FIG. 21 is the same as the graph GR21 in FIG. 20. Note that the process shown in FIG. 21 shows part of a first method, which will be described later, and details of which will be described later.

For example, the information processing device 100A generates third information that classifies multiple objects into multiple blobs by searching using the graph GR21. For example, the information processing device 100A selects one node (also called a "processing target node") from multiple nodes in the graph GR21, and generates the third information by a classification process that classifies the classification target nodes, which are at least some of the neighboring nodes that are nodes connected to the processing target node by edges, and the object groups corresponding to each of the processing target nodes into one group. For example, the information processing device 100A selects the processing target nodes from multiple nodes by a predetermined process, performs classification processing on the selected processing target nodes, and generates the third information.

For example, the information processing device 100A may select a processing target node based on the number of nearby nodes (connection nodes) connected to the node by an edge. For example, the information processing device 100A may select processing target nodes in descending order of the number of nearby nodes. The method of selecting processing target nodes in descending order of the number of nearby nodes and generating third information indicating a blob is also referred to as the "first method". Also, for example, the information processing device 100A may select processing target nodes in descending order of the number of nearby nodes (connection nodes). The method of selecting processing target nodes in descending order of the number of nearby nodes and generating a blob is also referred to as the "second method". Also, for example, the information processing device 100A may randomly select a processing target node. The method of randomly selecting a processing target node and generating third information indicating a blob is also referred to as the "third method". Below, an overview of the processing procedures of each of the first method, the second method, and the third method will be described.

[2-4-4-1. 1st method]
First, the first method will be described. For example, in the first method, the information processing device 100A performs the following processes (2-1) to (2-3) to generate third information indicating a blob. do.

(2-1): Obtain the node ND with the largest number of neighboring nodes (number of edges) for each node. (2-2): Set the neighboring nodes of node ND and node ND as one blob. (2-3): Delete the node and its edges that have been set as blobs.

For example, the information processing device 100A performs processes (2-1) to (2-3) on all nodes.

For example, in process (2-1), the information processing device 100A refers to the graph GR21 and sequentially acquires one node ND. The information processing device 100A may acquire one node ND using list information of nodes arranged in descending order of the number of neighboring nodes.

For example, in process (2-2), the information processing device 100A refers to the graph being processed (such as graph GR21) and generates information that treats the neighboring nodes of node ND and node ND as one blob. Note that the information processing device 100A may treat neighboring nodes up to a constant K as blobs, rather than treating all neighboring nodes as blobs. For example, the information processing device 100A may treat K of the neighboring nodes and node ND as one blob, rather than treating all neighboring nodes of node ND together with node ND as blobs.

For example, in process (2-3), the information processing device 100A deletes the node that was set as a blob in process (2-2) and the edge of that node so that the node is not selected in duplicate. For example, if the node that was set as a blob is a neighboring node of another node, the information processing device 100A deletes the node (edge and) the node. Note that the above method is merely an example, and process (2-3) is not limited to a method of deleting edges, etc., and may be any method that can generate a blob. For example, the information processing device 100A may generate a blob by a method of holding a list of nodes that already belong to the blob and managing nodes to be excluded. For example, the information processing device 100A may manage nodes that already belong to the blob by setting a predetermined flag (deletion flag, etc.) on the node that was set as a blob. In this way, when using flags, the information processing device 100A refers to the flag of each node during processing to determine whether the node is to be processed.

A specific example of the first method described above will be described with reference to FIG. 21. In FIG. 21, the information processing device 100A acquires node N7 from graph GR21, which has the maximum number of neighboring nodes (four) (step S51). In FIG. 21, node N1 from graph GR21 also has four neighboring nodes, but the information processing device 100A acquires node N7. Note that when there are multiple nodes with the same number of neighboring nodes, the information processing device 100A may randomly acquire a node from the multiple nodes.

Then, the information processing device 100A sets the four nodes N9, N12, N54, and N126, which are neighboring nodes of node N7, and the five nodes of node N7, as one blob BL11 (step S52). The information processing device 100A generates third information BLT1 indicating that the five nodes N7, N9, N12, N54, and N126 belong to one blob BL11. The information processing device 100A then deletes the five nodes N7, N9, N12, N54, and N126 and the edges of each node from the graph GR21. As a result, the graph GR21 is updated to graph GR21-1, as shown in the spatial information SP20-1.

Then, the information processing device 100A acquires node N1, which has four neighboring nodes, from graph GR21 (step S53). Then, the information processing device 100A sets the four neighboring nodes of node N1, nodes N4, N5, N88, and N99, and the five nodes of node N1, as one blob BL12 (step S54). The information processing device 100A generates third information BLT2 indicating that the five nodes, nodes N1, N4, N5, N88, and N99, belong to one blob BL12. Then, the information processing device 100A deletes the five nodes, nodes N1, N4, N5, N88, and N99, and the edges of each node from graph GR21-1.

The information processing device 100A repeats the above-described process until there are no more nodes to process, and generates third information indicating multiple blobs.

[2-4-4-2. Second method]
Next, the second method will be described. For example, in the case of the second method, the information processing device 100A performs the following processes (3-1) to (3-3) to generate third information indicating a blob. Generate.

(3-1): Obtain the node ND with the smallest number of neighboring nodes (number of edges) for each node. (3-2): Set the neighboring nodes of node ND and node ND as one blob. (3-3): Delete the node and its edges that have been set as blobs.

For example, the information processing device 100A performs processes (3-1) to (3-3) on all nodes.

For example, in process (3-1), the information processing device 100A refers to the graph GR21 and sequentially acquires one node ND. The information processing device 100A may acquire one node ND using list information of nodes arranged in ascending order of the number of neighboring nodes.

For example, in process (3-2), the information processing device 100A refers to the graph being processed (such as graph GR21) and generates information that treats the neighboring nodes of node ND and node ND as one blob. Note that the information processing device 100A may treat neighboring nodes up to a constant K as blobs, rather than treating all neighboring nodes as blobs. For example, the information processing device 100A may treat K of the neighboring nodes and node ND as one blob, rather than treating all neighboring nodes of node ND together with node ND as blobs.

For example, in process (3-3), the information processing device 100A deletes the node that was selected as a blob in process (3-2) and the edge of that node so that the node is not selected in duplicate. For example, if the node that was selected as a blob is a neighboring node of another node, the information processing device 100A deletes that node (and its edge). Note that the second method is similar to the first method except that the order in which the nodes are acquired is from the node with the smallest number of neighboring nodes (number of edges), and therefore a description of specific examples is omitted. For example, like the first method, process (3-3) is not limited to a method of deleting edges, etc., and may be any method that can generate a blob. For example, like the first method, the information processing device 100A may generate a blob by a method of holding a list of nodes that already belong to the blob and managing the nodes to be excluded.

[2-4-4-3. Third method]
Next, the third method will be described. For example, in the third method, the information processing device 100A performs the following processes (4-1) to (4-3) to generate third information indicating a blob. Generate.

(4-1): Randomly acquire nodes ND in sequence. (4-2): The neighboring nodes of node ND and node ND are treated as one blob. (4-3): The node treated as a blob and its edges are deleted.

For example, the information processing device 100A performs processes (4-1) to (4-3) on all nodes. Note that the third method is similar to the first and second methods except that the order in which the nodes are acquired is random, and detailed explanations are omitted. For example, the information processing device 100A may generate the third information in a random order (third method) if all the edges are the same.

[2-4-4-4. Fourth method]
The above-described first to third methods are merely examples, and the information processing device 100A may generate blobs by various processes. For example, the information processing device 100A may search for a plurality of objects. Alternatively, the blob may be generated by searching using a proximity search index (index) that searches the blob. The method of generating the blob by searching using the index is also referred to as a "fourth method."

The fourth method will be described below. Note that the same points as those described above will not be described as appropriate. Below, an example will be described in which a graph is used as an index, but as described above, the index may be any type of index as long as it searches multiple objects. For example, the index may be any type of index, such as a hash index or a tree index.

Now, a case will be described in which the information processing device 100A generates third information indicating a blob by performing a search using the graph GR21 as shown in FIG. 21 as an index. For example, the information processing device 100A performs the following processes (5-1) to (5-4) to generate the graph GR32.

(5-1): Get Object NX at random (select)
(5-2): Search for k neighboring objects of object NX. (5-3): Treat the neighboring objects of object NX and object NX as one blob. (5-4): Execute a process to avoid duplicate processing.

For example, in process (5-1), the information processing device 100A randomly obtains one object NX from the graph GR21.

For example, in process (5-2), the information processing device 100A performs a search process as shown in FIG. 11 using the graph GR21 with the object NX as the target (query) to extract k objects as objects near the object NX. Note that the information processing device 100A may also scan (search) all objects to extract objects near the object NX.

For example, in process (5-3), the information processing device 100A generates information that treats the neighboring nodes of the neighboring objects of object NX and object NX as one blob.

For example, in process (5-4), the information processing device 100A executes a process to avoid duplicate processing so that a single object does not belong to multiple blobs due to duplicate searches, etc. For example, the information processing device 100A deletes the object that has been set as a blob from the index. For example, the information processing device 100A deletes the object that has been set as a blob from the graph GR21.

The information processing device 100A may use any method to avoid duplicate processing as long as an object does not belong to multiple blobs, and is not limited to the above. For example, the information processing device 100A may prevent objects that already belong to a blob from being processed by setting a specified flag (such as a deletion flag) on the object that has been made a blob. In this way, when using flags, the information processing device 100A refers to the flag of each object during processing to determine whether the object should be processed. For example, when the information processing device 100A uses search results to generate the above-mentioned group graph, the information processing device 100A may use a method that uses flags to avoid duplicate processing.

2-4-5. Information processing device according to modified example
In the information processing device 100A according to the modified example of the second embodiment, the acquisition unit 131 also performs the following processes. The acquisition unit 131 acquires first information indicating a plurality of objects to be the targets of data search, and second information used to classify the plurality of objects. The acquisition unit 131 acquires the second information which is an index for searching a plurality of objects. The acquisition unit 131 acquires the second information which is a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges. The acquisition unit 131 acquires fourth information which is an index for searching a plurality of objects. The acquisition unit 131 acquires the fourth information which is a graph in which a plurality of object nodes corresponding to each of the plurality of objects are connected by edges.

In addition, in the information processing device 100A according to the modified example of the second embodiment, the generation unit 132A also performs the following processing. The generation unit 132A uses the second information acquired by the acquisition unit 131 to classify the multiple objects indicated by the first information, and generates third information indicating multiple groups used for performing batch processing in a search process targeting multiple objects. The generation unit 132A uses the second information to generate third information that classifies the multiple objects into multiple groups. The generation unit 132A generates third information that classifies the multiple objects into multiple groups by a search using the second information.

The generation unit 132A generates third information by a classification process that selects one node from among multiple nodes in the graph, and classifies into one group the classification target nodes, which are at least some of the neighboring nodes that are nodes connected to the one node by edges, and the object group corresponding to each of the one node. The generation unit 132A generates third information by a classification process that classifies into one group the classification target nodes, which are a predetermined number of the neighboring nodes of the one node, and the object group corresponding to each of the one node. The generation unit 132A generates third information by a classification process that classifies into one group the classification target nodes, which are all of the neighboring nodes of the one node, and the object group corresponding to each of the one node.

The generation unit 132A selects one node from the plurality of nodes based on the number of neighboring nodes that are nodes connected to each of the plurality of nodes by edges, and generates the third information by a classification process that classifies the classification target node of the one node and the object group corresponding to each of the one nodes into one group. The generation unit 132A selects one node in descending order of the number of neighboring nodes, and generates the third information by a classification process that classifies the classification target node of the one node and the object group corresponding to each of the one nodes into one group. The generation unit 132A selects one node in descending order of the number of neighboring nodes, and generates the third information by a classification process that classifies the classification target node of the one node and the object group corresponding to each of the one nodes into one group.

The generation unit 132A randomly selects one node from the multiple nodes, and generates the third information by a classification process that classifies the classification target node of the one node and the object group corresponding to each of the one node into one group. The generation unit 132A removes the classification target node of the one node classified into one group and the processed node group that is the one node from the graph, and generates the third information by repeating the classification process using the graph after removing the processed node group. The generation unit 132A generates the third information by repeating the classification process using the graph after removing the processed node group until the multiple objects are classified into one of the groups. The generation unit 132A generates the third information indicating multiple groups whose objects belong to each group mutually exclusive.

The generation unit 132A uses the fourth information to generate a group graph in which edges are connected from an object node, which is a node corresponding to at least some of the multiple objects, to other groups among the multiple groups other than the group to which the object node belongs. The generation unit 132A selects one object from the multiple objects, searches for neighboring objects of the one object among the multiple objects using the fourth information, and generates a group graph by a connection process that connects edges from the one object node corresponding to the one object to other groups to which the neighboring objects belong. The generation unit 132A randomly selects one object from the multiple objects, searches for neighboring objects of the one object, and generates a group graph by a connection process that connects edges from the one object node corresponding to the one object to other groups to which the neighboring objects belong. The generation unit 132A uses the fourth information to generate a group graph.

[2-4-6. Information processing flow]
Next, a procedure of information processing according to the modified example will be described with reference to Fig. 22. Fig. 22 is a flowchart showing an example of information processing according to the modified example.

22, the information processing device 100A acquires first information indicating multiple objects to be subjected to data search (step S401). For example, the information processing device 100A acquires the first information indicating multiple objects from the object information storage unit 121.

In addition, the information processing device 100A acquires second information used to classify the multiple objects (step S402). For example, the information processing device 100A acquires a graph from the graph information storage unit 122A as the second information.

Then, the information processing device 100A uses the second information to classify the multiple objects indicated by the first information, and generates third information indicating multiple groups used for performing batch processing in a search process targeting multiple objects (step S403). For example, the information processing device 100A generates third information indicating multiple blobs whose objects are mutually exclusive.

3. Third embodiment
In the above example, two types of graphs are used: a graph in which nodes corresponding to objects (object nodes) are connected by edges (also called an "object graph"), and a graph in which object nodes and groups (blobs) are connected by edges (a graph for blobs), but the information processing system 1 may use various types of graphs. For example, the information processing system 1 may generate a graph in which groups (blobs) are connected (hereinafter also called a "group connection graph" or "blob connection graph"), different from the object graph and the graph for blobs, and use the blob connection graph for searching.

This point will be described below as the third embodiment. In the third embodiment, the information processing system 1 has an information processing device 100B instead of the information processing device 100 or the information processing device 100A. Note that the description of the same points as those described above in the first and second embodiments will be omitted as appropriate.

The information processing device 100B uses the index (index information) to generate a group connection graph in which edges are connected from a first group (first blob) to which an object belongs to a second group (second blob) to which a neighboring object of the object belongs. In the following, a case where a graph is used as an example of an index will be described as an example, but as described above, the index may be any type of index as long as it searches multiple objects. For example, the index may be any type of index, such as a hash index or a tree index.

[3-1. Information Processing]
First, an overview of information processing according to the third embodiment will be described with reference to Fig. 23. Fig. 23 is a diagram showing an example of information processing according to the third embodiment.

In the example of FIG. 23, it is assumed that the information processing device 100B has already acquired a graph GR21 as shown in the spatial information SP21. Note that the information processing device 100B may generate the graph GR21 by appropriately using various graph generation techniques. The graph GR21 is similar to the graph GR21 shown in FIG. 12 etc., and therefore description thereof will be omitted.

The information processing device 100B generates information indicating blobs BL1 to BL10, etc., by any method. The information processing device 100B may classify each node into one of blobs BL1 to BL10 by any clustering method such as k-means. Note that the information processing device 100B may generate blobs by any method as long as it is possible to generate blobs. For example, the information processing device 100B may generate information indicating blobs BL1 to BL10, etc., by any of the first to fourth methods described above.

The information processing device 100B generates a blob connection graph using the graph GR21 and blob information as shown in the spatial information SP21 (step S61). In the example of FIG. 23, the information processing device 100B generates a graph GR41, which is a blob connection graph in which a blob (first blob) and another blob (second blob) are connected by edges as shown in the spatial information SP41. The arrow line shown in FIG. 23 indicates a directed edge from the blob at the origin of the arrow (first blob) to the blob at the tip of the arrow (second blob). In other words, the arrow line shown in FIG. 23 indicates a directed edge with the blob at the origin of the arrow as the reference source and the blob at the tip of the arrow as the reference destination. For example, FIG. 23 indicates that edges are connected from blob BL1 to five blobs, blob BL2, blob BL3, blob BL4, blob BL5, and blob BL8.

For example, the information processing device 100B searches the graph GR21 and generates a graph GR41 based on the search results. For example, the information processing device 100B performs the following processes (6-1) to (6-4) to generate the graph GR41, which is a blob-connected graph. Note that the following objects may be read as nodes corresponding to the objects.

(6-1): Get Object NX at random (select)
(6-2): Search for k neighboring objects of object NX. (6-3): Obtain the blob to which each neighboring object belongs. (6-4): Generate an edge from the blob to which object NX belongs to the obtained blob.

For example, in process (6-1), the information processing device 100B randomly acquires one object NX from multiple objects stored in the object information storage unit 121.

For example, in process (6-2), the information processing device 100B performs a search process as shown in FIG. 11 using the graph GR21 with the object NX as the target (query), thereby extracting k objects as objects near the object NX.

For example, in process (6-3), the information processing device 100B refers to the blob information stored in the blob information storage unit 125 and obtains the blob associated with the nearby object (node) of object NX.

For example, in process (6-4), the information processing device 100B generates an edge from the blob to which the object NX belongs to the acquired blob. The information processing device 100B generates edges from the blob to which the object NX belongs to the blobs to which all nearby objects belong. For example, the information processing device 100B generates graph GR41 by registering information (blob ID) indicating the blob acquired as a reference destination of the blob to which the object NX belongs, in association with information (blob ID) indicating the blob to which the object NX belongs, in the blob connection graph information storage unit 126.

For example, the information processing device 100B repeats the above processes (6-1) to (6-4) until there are no more objects to be processed, and generates the graph GR41. Note that when blob Y has already been registered as a reference destination of blob X, even if an object belonging to blob Y is searched (extracted) again as a neighboring object of an object belonging to blob X, the information processing device 100B may skip the registration and prevent the same blob from being registered as a reference destination of each blob more than once.

For example, the information processing device 100B performs search processing using a graph GR41 that connects blobs with edges, as shown in the spatial information SP41. For example, the information processing device 100B performs search processing as shown in Figures 27 and 28 using the graph GR41, which is a blob-connected graph, for the search query QE2, thereby obtaining search results for the search query QE2.

The above-described method of generating a blob connection graph is merely one example, and the information processing device 100B may generate a blob connection graph using various methods. For example, the information processing device 100B may generate a blob connection graph without searching a graph. If the blobs shown in the spatial information SP21 are generated by searching, the search results from the generation of the blobs may be reused to generate a blob connection graph such as graph GR41.

For example, the information processing device 100B may convert the connection relationships of the object nodes in the graph GR21 into the connection relationships of the blobs to which the object nodes belong, to generate a blob connection graph. For example, an edge connects node N1 belonging to blob BL9 to node N88 belonging to blob BL8 and a node belonging to blob BL10, and an edge connects node N4 belonging to blob BL9 to a node belonging to blob BL7. Therefore, the information processing device 100B generates a blob connection graph in which edges are connected from blob BL9 to the three blobs BL7, blob BL8, and blob BL10. In this way, the information processing device 100B may generate a blob connection graph in which blobs are connected by edges based on edges connecting object nodes.

3-2. Configuration of information processing device
Next, the configuration of the information processing device 100B according to the third embodiment will be described with reference to Fig. 24. Fig. 24 is a diagram showing an example of the configuration of the information processing device according to the third embodiment. As shown in Fig. 24, the information processing device 100B has a communication unit 110, a storage unit 120B, and a control unit 130B. Note that in the information processing device 100B, the description of the same points as those of the information processing device 100 or the information processing device 100A will be omitted as appropriate.

(Memory unit 120B)
The storage unit 120B is realized by, for example, a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 24, the storage unit 120B according to the third embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123, a codebook information storage unit 124, a blob information storage unit 125, and a blob connection graph information storage unit 126.

(Blob connection graph information storage unit 126)
The blob connection graph information storage unit 126 according to the third embodiment stores various information related to the blob connection graph. For example, the blob connection graph information storage unit 126 stores the generated blob connection graph. Fig. 25 is a diagram showing an example of the blob connection graph information storage unit according to the third embodiment. The blob connection graph information storage unit 126 shown in Fig. 25 has items such as "blob ID" and "connected blob information".

"Blob ID" indicates identification information for identifying each blob (group) in the graph. "Connected blob information" indicates information about blobs (reference blobs) that can be traced from the corresponding blob. For example, "connected blob information" includes information such as "reference." "Reference" indicates information for identifying a reference (blob) that is connected by an edge and can be traced from that blob. That is, in the example of Figure 25, a reference (blob) that can be traced from that blob by an edge is registered in correspondence with a blob ID that identifies a blob. Note that "connected blob information" may also include information (edge ID) for identifying an edge connected to a reference.

The example in FIG. 25 shows that edges connect the blob (blob BL1) identified by the blob ID "BL1" to five blobs identified by the blob IDs "BL2," "BL3," "BL4," "BL5," and "BL8." In other words, it shows that it is possible to trace from blob BL1 to each of the five blobs BL2, BL3, BL4, BL5, and BL8.

The blob connection graph information storage unit 126 may store various information according to the purpose, without being limited to the above. The blob connection graph may include a program module that takes a query as an input, searches for objects (object nodes) by tracing edges in the blob connection graph, and extracts and outputs objects similar to the query. That is, the blob connection graph may be used as a program module that performs search processing using the blob connection graph. For example, the graph GR41, which is a blob connection graph, may be a program that, when vector data is input as a query, extracts objects corresponding to vector data similar to the vector data using the blob connection graph and outputs the objects. For example, the graph GR41 may be data used as a program module that searches for similar images corresponding to a query image. For example, the graph GR41 causes a computer to function so as to extract and output objects similar to the query in the blob connection graph based on the input query.

(Control unit 130B)
Returning to the explanation of Fig. 24, the control unit 130B is a controller, and is realized, for example, by a CPU, an MPU, a GPU, etc., executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100B using a RAM as a working area. The control unit 130B is also a controller, and is realized, for example, by an integrated circuit such as an ASIC or an FPGA.

As shown in FIG. 24, the control unit 130B has an acquisition unit 131, a generation unit 132B, a search processing unit 133B, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130B is not limited to the configuration shown in FIG. 24, and may be other configurations as long as they perform the information processing described below.

The acquisition unit 131 according to the third embodiment acquires blob information indicating multiple blobs into which multiple objects to be the target of data search are classified, and index information indicating an index in which multiple objects are the search targets. The acquisition unit 131 acquires index information indicating a graph in which multiple nodes corresponding to each of the multiple objects are connected by edges. The acquisition unit 131 acquires blob information indicating multiple blobs into which multiple objects are classified by a clustering process. The acquisition unit 131 acquires blob information indicating multiple blobs in which objects belonging to each blob are mutually exclusive. The acquisition unit 131 acquires a query.

(Generation unit 132B)
The generating unit 132B generates various types of information in the same manner as the generating unit 132 or the generating unit 132A.

The generating unit 132B uses the index information acquired by the acquiring unit 131 to generate a blob connection graph in which an edge is connected from a first blob to which one of the multiple objects belongs to a second blob that is a blob to which a neighboring object of the one object belongs. The generating unit 132B selects one object from the multiple objects, searches the multiple objects for a previous neighboring object of the one object using the index information, and generates a blob connection graph by connecting an edge from the first blob to which the one object belongs to to the second blob to which the neighboring object belongs.

The generation unit 132B randomly selects one object from the multiple objects, searches for nearby objects of the one object, and generates a blob connection graph by connecting edges from a first blob to which the one object belongs to a second blob to which the nearby object belongs. The generation unit 132B uses the graph to generate a blob connection graph in which edges are connected from the first blob to the second blob.

The generation unit 132B uses the graph to search for nearby objects of an object, and generates a blob connection graph by connecting an edge from a first blob to which the object belongs to a second blob to which the nearby object belongs. The generation unit 132B generates a blob connection graph by connecting an edge from the first blob to a second blob to which a nearby object belongs that corresponds to a nearby node that is a node connected by an edge to a node corresponding to the object in the graph.

The generation unit 132B generates a blob connection graph by connecting, from the first blob, a first representative point that is a representative point of the first blob and a second representative point that is a representative point of the second blob with an edge. The generation unit 132B generates a blob connection graph by connecting, from the first blob, a first representative point that is a centroid of the first blob and a second representative point that is a centroid of the second blob with an edge. The generation unit 132B generates a blob connection graph by connecting, from the first representative point that is a center point calculated based on objects belonging to the first blob and the second representative point that is a center point calculated based on objects belonging to the second blob with an edge.

(Search processing unit 133B)
The search processing unit 133B performs various processes related to the search process in the same manner as the search processing unit 133 or the search processing unit 133A.

The search processing unit 133B performs a search process using the blob connection graph generated by the generation unit 132B. The search processing unit 133B performs a search process to search for nearby objects of the search query using the blob connection graph. The search processing unit 133B performs a search process to search for nearby objects of the search query by tracing edges that connect blobs in the blob connection graph.

In the search process, the search processing unit 133B uses blob information indicating multiple blobs to calculate the distance between a target object, which is an object belonging to one blob, and the search query, using vector information of the vector-quantized target object. The search processing unit 133B performs the calculation of the distance between the target object and the search query in parallel and in a batch. The search processing unit 133B performs the calculation of the distance between the search query and the target objects of the batch processing number determined based on the specifications of the information processing device in parallel.

[3-3. Information processing flow]
Next, a procedure of information processing according to the third embodiment will be described with reference to Fig. 26. Fig. 26 is a flowchart showing an example of information processing according to the third embodiment.

As shown in FIG. 26, the information processing device 100B acquires group information indicating a plurality of groups into which a plurality of objects to be the subject of the data search are classified (step S501). For example, the information processing device 100B acquires blob information indicating a plurality of blobs into which nodes (object nodes) corresponding to a plurality of objects to be the subject of the data search are classified.

The information processing device 100B acquires index information indicating an index for searching multiple objects (step S502). For example, the information processing device 100B acquires, as an index, a graph in which nodes (object nodes) corresponding to multiple objects are connected by edges.

The information processing device 100B uses the index information to generate a group connection graph in which edges are connected from a first group to which one of the multiple objects belongs to a second group to which a neighboring object of the one object belongs (step S503). For example, the information processing device 100B uses the index information to generate a blob connection graph in which edges are connected from a first blob to which one of the multiple objects belongs to a second blob to which a neighboring object of the one object belongs.

[3-4. Search processing example]
Here, an example of the search process according to the third embodiment will be described with reference to Figs. 27 and 28. Figs. 27 and 28 are flowcharts showing an example of the search process according to the third embodiment. The search process described below is performed by the search processing unit 133B of the information processing device 100B. Note that the description of the same points as those of the search process described in the first and second embodiments will be omitted as appropriate.

In Figures 27 and 28, N(G,s) and C are a set of blobs (blob set). "G" may also be graph (blob connection graph) data in which blobs are connected by edges (for example, graph GR41 shown in spatial information SP41). For example, information processing device 100B executes k-nearest neighbor search processing.

First, the process (main process) shown in FIG. 27 will be described. For example, the information processing device 100B sets the radius r of the hypersphere to ∞ (infinity) and sets the blob set C to an empty set (Φ) (step S601). Then, the information processing device 100B extracts a partial blob set B from the existing blob set (all blobs) (step S602). For example, the information processing device 100B may extract a blob to which an object (node) selected as the root node belongs as the partial blob set B. Also, for example, the information processing device 100B may randomly extract blobs as the partial blob set B.

Then, the information processing device 100B executes a determination process (step S603). The information processing device 100B executes the determination process of steps S701 to S717 shown in FIG. 28. Details of the determination process shown in FIG. 28 will be described later.

Then, the information processing device 100B sets the partial blob set B to the blob set S (step S604).

The information processing device 100B selects a blob s with the smallest query distance d from among the blobs included in the blob set S (step S605). Note that the "query distance" here is the shortest distance between all objects in the blob and the query object (query). For example, if an object that is a query (search query) is y, the information processing device 100B selects a blob s from the blob set S with the shortest query distance to object y. Note that the query distance is not limited to the above, and may be, for example, the distance between the query and the representative point (centroid, etc.) of the blob. Then, the information processing device 100B excludes the blob s from the blob set S (step S606).

Then, the information processing device 100B determines whether the query distance d of the blob s exceeds r(1+ε) (step S607). If the query distance d of the blob s exceeds r(1+ε) (step S607: Yes), the information processing device 100B outputs the object set R as a neighborhood object set of the object y (step S608) and ends the process.

If the query distance d of blob s does not exceed r(1+ε) (step S607: No), the information processing device 100B determines whether blob s is included in the blob set C (step S609).

If blob s is included in blob set C (step S609: Yes), information processing device 100B returns to step S605 and repeats the process.

If blob s is not included in blob set C (step S609: No), the information processing device 100B adds blob s to blob set C (step S610).

Then, the information processing device 100B sets a neighborhood blob set N(G,s) of blob s in the partial blob set B (step S611). The neighborhood blob set N(G,s) is, for example, a set of blobs (neighboring blobs) associated with blob s. For example, the neighborhood blob set N(G,s) is a set of blobs (neighboring blobs) connected by edges from blob s. The information processing device 100B then executes a determination process (step S612). Details will be described later, but for example, the information processing device 100B executes the determination process of steps S701 to S717 shown in FIG. 28, similar to step S603 described above.

Then, the information processing device 100B determines whether the blob set S is an empty set (Φ) (step S613). If the blob set S is not an empty set (step S613: No), the information processing device 100B returns to step S605 and repeats the process. Also, if the blob set S is an empty set (step S613: Yes), the information processing device 100B outputs the object set R and ends the process (step S614). For example, the information processing device 100B may select an object (node) included in the object set R as a nearby node corresponding to the added node (input object y). For example, the information processing device 100B may extract (select) an object (node) included in the object set R as a nearby node corresponding to the target node (input object y). Also, for example, the information processing device 100B may provide the object (node) included in the object set R to the terminal device that performed the search as a search result corresponding to the search query (input object y).

Now, the process (determination process) shown in FIG. 28 will be described. First, the information processing device 100B sets a partial blob set B in the blob set T (step S701).

Then, the information processing device 100B acquires one blob b from the blob set T, and deletes the blob b from the blob set T (step S702). Then, the information processing device 100B sets the variable min used in the determination process to ∞ (infinity) (step S703).

Then, the information processing device 100B obtains one object u from blob b and deletes object u from blob b (step S704).

Then, the information processing device 100B determines whether the distance d(u, y) between objects u and y is less than min (step S705).

If the distance d(u, y) between objects u and y is less than min (step S705: Yes), the information processing device 100B sets (updates) the value of min to the distance d(u, y) (step S706) and performs processing of step S707.

If the distance d(u, y) between object u and object y is not less than min (step S705: No), the information processing device 100B does not perform the process of step S706, but performs the process of step S707.

The information processing device 100B determines whether the distance d(u, y) between objects u and y is less than or equal to r(1+ε) (step S707).

If the distance d(u, y) between objects u and y is less than or equal to r(1+ε) (step S707: Yes), the information processing device 100B adds the blob b to the blob set S (step S708) and performs the processing of step S709.

If the distance d(u, y) between object u and object y is not less than r(1+ε) (step S707: No), the information processing device 100B does not perform the process of step S708, but performs the process of step S709.

The information processing device 100B determines whether the distance d(u, y) between objects u and y is less than or equal to r (step S709).

If the distance d(u, y) between object u and object y is less than or equal to r (step S709: Yes), the information processing device 100B adds object u to object set R (step S710) and performs processing of step S711.

If the distance d(u, y) between object u and object y is not less than r (step S709: No), the information processing device 100B does not perform the process of step S710, but performs the process of step S711.

The information processing device 100B determines whether the number of objects included in the object set R exceeds ks (step S711). The predetermined number ks is a natural number that is determined arbitrarily. For example, ks may be the number of searches or the number of objects to be extracted. Furthermore, for example, when no upper limit is set on the number of objects to be extracted in a range search or the like, ks may be set to infinity. For example, ks may be 4, etc.

If the number of objects included in object set R exceeds ks (step S711: Yes), information processing device 100B excludes from object set R the object that is farthest from object y among the objects included in object set R (step S712), and performs processing of step S713.

If the number of objects included in object set R does not exceed ks (step S711: No), information processing device 100B does not perform processing in step S712, but performs processing in step S713.

The information processing device 100B determines whether the number of objects included in the object set R matches ks (step S713).

If the number of objects included in object set R matches ks (step S713: Yes), information processing device 100B sets the distance between object y and the object farthest from object y among the objects included in object set R to r (step S714), and performs processing of step S715.

If the number of objects included in the object set R does not match ks (step S713: No), the information processing device 100B does not perform the process of step S714, but performs the process of step S715.

The information processing device 100B determines whether or not the blob b is an empty set (Φ) (step S715). If the blob b is not an empty set (step S715: No), the information processing device 100B returns to step S704 and repeats the process.

Also, if blob b is an empty set (step S715: Yes), the information processing device 100B sets min as the query distance of blob b in the partial blob set B (step S716). For example, the information processing device 100B sets min as the query distance, which is the shortest distance between all objects of blob b and the query.

The information processing device 100B determines whether the blob set T is an empty set (Φ) (step S717). If the blob set T is not an empty set (step S717: No), the information processing device 100B returns to step S702 and repeats the process.

Also, if the blob set T is an empty set (step S717: Yes), the determination process ends.

3-5. Modified Examples
The blob connection graph may be configured in various ways, not limited to the above-mentioned example. For example, the blob connection graph may be a graph in which the representative points of each group (blob) are connected by edges. This point will be described below as a modified example of the third embodiment. Note that the description of the same points as the first, second, and third embodiments will be omitted as appropriate. The information processing device 100B according to the modified example of the third embodiment has a blob information storage unit 125A and a blob connection graph information storage unit 126A instead of the blob information storage unit 125 and the blob connection graph information storage unit 126.

[3-5-1. Information Processing]
First, an overview of information processing according to the modified example will be described with reference to Fig. 29. Fig. 29 is a diagram showing an example of blob connection graph information according to the modified example. The example of Fig. 29 shows a case where blobs are generated by clustering.

In the example of FIG. 29, the information processing device 100B generates a blob connection graph that connects the centroids of each blob. The information processing device 100B generates graph GR42, which is a blob connection graph that connects the centroids C1 to C10 corresponding to each of the blobs BL1 to BL10 with edges, as shown in the spatial information SP41. The information processing device 100B generates graph GR42 by appropriately using various conventional techniques related to graph generation.

For example, the information processing device 100B generates a graph GR42 in which the centroid C1 of blob BL1 is connected by edges to five centroids: the centroid C2 of blob BL2, the centroid C3 of blob BL3, the centroid C4 of blob BL4, the centroid C7 of blob BL7, and the centroid C8 of blob BL8. Also, for example, the information processing device 100B generates a graph GR42 in which the centroid C2 of blob BL2 is connected by edges to three centroids: the centroid C1 of blob BL1, the centroid C3 of blob BL3, and the centroid C4 of blob BL4.

The information processing device 100B may generate the graph GR42 by any method. The information processing device 100B may generate the graph GR42 by using various indexes. For example, the information processing device 100B may generate the graph GR42 by using the graph GR21 in which object nodes are linked. In this case, the information processing device 100B can generate the graph GR42 by the same process as the graph GR41 in FIG. 23, so a detailed description will be omitted. For example, the information processing device 100B may generate the graph GR42 by the same process as the example shown in FIG. 23. Note that although the graph GR42 shows an undirected (bidirectional) edge as an example, it may be a directed edge.

In this way, the information processing device 100B according to the modified example generates a centroid graph as a blob-linked graph. The information processing device 100B then performs a normal search with the centroids using the generated blob-linked graph, and performs distance calculations on a blob-by-blob basis. In this way, the information processing device 100B can simplify processing by representing blobs with centroids. Note that, when the blobs are not clustered, the information processing device 100B may calculate a center point based on the objects belonging to each blob, and use the calculated center point as the representative point.

In the example of FIG. 29, the information processing device 100B performs search processing using a graph GR42 in which centroids, which are representative points of blobs, are connected by edges, as shown in the spatial information SP42. For example, the information processing device 100B performs search processing as shown in FIG. 27 and FIG. 28 using the graph GR21 for the search query QE2, thereby obtaining search results for the search query QE2. This is similar to the example described above, and detailed description will be omitted.

3-5-2. Information
Next, an overview of information related to the modified example will be described with reference to Fig. 30 and Fig. 31. Fig. 30 is a diagram showing an example of a blob information storage unit related to the modified example. Fig. 31 is a diagram showing an example of a blob connection graph information storage unit related to the modified example.

First, the blob information storage unit 125A according to the modified example shown in FIG. 30 will be described. The blob information storage unit 125A according to the modified example shown in FIG. 30 includes items such as "blob ID," "node ID," "vector information," and "centroid ID." In this way, the blob information storage unit 125A according to the modified example differs from the blob information storage unit 125 of FIG. 15 in that it includes a "centroid ID." Note that descriptions of the points similar to those of the blob information storage unit 125 of FIG. 15 will be omitted as appropriate.

"Centroid ID" indicates identification information for identifying the centroid of each blob. "Vector information" indicates vector information of the centroid, which is the representative point of the blob.

In the example shown in FIG. 30, the centroid of blob BL1 identified by blob ID "BL1" is the centroid (centroid C1) identified by centroid ID "C1". The centroid of blob BL9 identified by blob ID "BL9" is the centroid (centroid C9) identified by centroid ID "C9".

The blob information storage unit 125A may store various types of information depending on the purpose, not limited to the above.

Next, the blob connection graph information storage unit 126A according to the modified example shown in FIG. 31 will be described. The blob connection graph information storage unit 126A according to the modified example shown in FIG. 30 has items such as "centroid ID" and "connection centroid information." Note that explanations of points similar to those of the blob connection graph information storage unit 126 in FIG. 25 will be omitted as appropriate.

"Centroid ID" indicates identification information for identifying a centroid, which is the representative point of each blob in the graph. "Connection centroid information" indicates information on a centroid (reference centroid) that can be traced from the corresponding centroid. For example, "connection centroid information" includes information such as "reference destination." "Reference destination" indicates information for identifying a reference destination (centroid) that is connected by an edge and can be traced from that centroid. That is, in the example of Figure 31, a centroid ID that identifies a centroid is associated with a reference destination (centroid) that can be traced from that centroid by an edge and is registered. Note that "connection centroid information" may also include information (edge ID) for identifying an edge connected to a reference destination.

The example in FIG. 31 shows that edges are connected from the centroid (centroid C1) identified by the centroid ID "C1" to five centroids identified by the centroid IDs "C2," "C3," "C4," "C7," and "C8." In other words, it shows that it is possible to trace from the centroid C1 to each of the five centroids, C2, C3, C4, C7, and C8.

The blob connection graph information storage unit 126A may store various information according to the purpose, not limited to the above. The blob connection graph may include a program module that takes a query as an input, searches for an object (object node) by tracing edges in the blob connection graph, and extracts and outputs an object similar to the query. That is, the blob connection graph may be used as a program module that performs search processing using the blob connection graph. For example, the graph GR42, which is a blob connection graph, may be a program that, when vector data is input as a query, extracts an object corresponding to vector data similar to the vector data using the blob connection graph and outputs it. For example, the graph GR42 may be data used as a program module that searches for a similar image corresponding to a query image. For example, the graph GR42 causes a computer to function so as to extract and output an object similar to the query in the blob connection graph based on the input query.

As described above, in each embodiment and modification, the information processing system 1 executes the following process. For example, the information processing system 1 generates blobs by vector clustering. For example, the information processing system 1 generates a graph index with the centroids of the blobs as nodes.

For example, the information processing system 1 acquires a certain number of arbitrary vectors and performs clustering using direct product quantization. In other words, the information processing system 1 divides the vectors into partial vectors, performs clustering on a partial vector basis, and generates a codebook.

For example, the information processing system 1 performs direct product quantization on objects belonging to a blob unit to generate a transposed index. For example, the information processing system 1 generates a graph (blob graph) including edges from objects to blobs. For example, the information processing system 1 searches for nearby objects using a general direct product quantization method. The general direct product quantization method may be, for example, calculating the distance between an object and all centroids of a blob to obtain a certain number of blobs, and then obtaining nearby objects by calculating the distance of objects in the blob using direct product quantization. Note that, as described above, if the information processing system 1 generates a centroid graph, it is possible to search for and obtain a certain number of blobs using the graph. Alternatively, the information processing system 1 may generate a graph (blob connection graph) in which blobs are connected by edges, instead of the graph (blob graph) including edges from objects to blobs described above.

4. Fourth embodiment
In the above example, a case where blobs are used as an example of groups for classifying objects has been shown, but groups for classifying objects are not limited to blobs, and various graphs for classifying objects may be used. For example, in addition to blobs (first group), clusters may be used as second groups that are units for quantizing objects.

This point will be described below as the fourth embodiment. In the fourth embodiment, the information processing system 1 has an information processing device 100C instead of the information processing device 100, the information processing device 100A, or the information processing device 100B. Note that the description of the same points as those described above in the first embodiment, the second embodiment, the third embodiment, etc. will be omitted as appropriate.

The information processing device 100C generates blob information (first group information) indicating multiple blobs that classify multiple objects, and cluster information (second group information) indicating clusters, which are groups that are classified differently from the blobs.

[4-1. Information Processing]
First, an overview of information processing according to the fourth embodiment will be described with reference to Fig. 32. Fig. 32 is a diagram showing an example of information processing according to the fourth embodiment. Fig. 32 shows a case where the information processing device 100C classifies objects into a plurality of blobs and classifies them into clusters based on the blobs, but it is also possible to classify objects into blobs after classifying them into clusters, which will be described later.

First, the information processing device 100C generates blob information that classifies a plurality of objects into a plurality of blobs (step S71). In the example of FIG. 32, the information processing device 100C generates blob information that classifies a plurality of objects into blobs BL1 to BL10, etc., by an arbitrary method. The information processing device 100C may classify each node into one of the blobs BL1 to BL10 by an arbitrary clustering method such as k-means. Note that the information processing device 100C may generate blobs by any method as long as it is possible to generate blobs. For example, the information processing device 100C may generate blobs using an index such as a graph. For example, the information processing device 100C may generate information indicating blobs BL1 to BL10, etc., by any of the above-mentioned first to fourth methods, etc.

In FIG. 32, the information processing device 100C generates a graph GR41, which is a blob-connected graph, as shown in the spatial information SP41, but it is not necessary to generate the graph GR41. For example, when generating the graph GR41, the information processing device 100C generates the graph GR41 by processing using the same information as in FIG. 23, but as this is the same as the explanation in FIG. 23, a detailed explanation will be omitted.

Then, the information processing device 100C generates cluster information that classifies the multiple blobs into multiple clusters (step S72). For example, the information processing device 100C generates cluster information indicating clusters into which the multiple blobs, such as blobs BL1 to BL10, are classified by an arbitrary method. The information processing device 100C may classify the blobs, such as blobs BL1 to BL10, into one of the multiple clusters by an arbitrary clustering method such as k-means. Note that the information processing device 100C may generate blobs by any method as long as it is possible to generate blobs. For example, the information processing device 100C may generate blobs using an index such as a graph.

In the example of FIG. 32, the information processing device 100C generates cluster information that classifies blobs BL1 to BL10 into clusters CL1 to CL4. For example, the information processing device 100C classifies blob BL1 and blob BL7 into cluster CL1. That is, the information processing device 100C classifies objects belonging to blob BL1 and objects belonging to blob BL7 into cluster CL1. Note that although the boundaries of blobs are illustrated as being on the boundaries of clusters in FIG. 32 and FIG. 34, they may not coincide depending on the division method, and the space is not necessarily divided by the boundaries depending on the method.

In addition, the information processing device 100C classifies blob BL2 and blob BL4 into cluster CL2. That is, the information processing device 100C classifies the objects belonging to blob BL2 and the objects belonging to blob BL4 into cluster CL2.

In addition, the information processing device 100C classifies blobs BL3, BL8, and BL10 into cluster CL3. That is, the information processing device 100C classifies objects belonging to blob BL3, objects belonging to blob BL8, and objects belonging to blob BL10 into cluster CL3.

In addition, the information processing device 100C classifies blobs BL5, BL6, and BL9 into cluster CL4. That is, the information processing device 100C classifies the objects belonging to blob BL5, the objects belonging to blob BL6, and the objects belonging to blob BL9 into cluster CL4.

For example, the information processing device 100C uses the cluster information to perform processing related to quantization. The information processing device 100C uses the cluster information to perform processing related to quantization of multiple objects. For example, the information processing device 100C performs quantization for each object belonging to each of the clusters CL1 to CL4, which will be described later.

As described above, the information processing device 100C generates blob information indicating a plurality of blobs that classify a plurality of objects that are the subject of a data search, and cluster information indicating a plurality of clusters that are classified differently from the plurality of blobs. This allows the information processing device 100C to generate two types of groups that classify a plurality of objects, and to generate groups that classify objects.

[4-1-1. Other processing examples]
Note that the process shown in FIG. 32 is merely an example, and the information processing device 100C may perform generation by any type of process as long as it is capable of generating blob information and cluster information.

For example, the information processing device 100C may generate cluster information for classifying objects into clusters, and then generate blob information for classifying objects into blobs. In this case, the information processing device 100C may generate cluster information for classifying each object into one of multiple clusters by clustering that classifies multiple objects into clusters. For example, the information processing device 100C may classify each object into one of clusters CL1 to CL4 by any clustering method such as k-means.

The information processing device 100C may then generate blob information indicating the blobs by dividing at least one of the clusters CL1 to CL4 and generating two or more blobs. For example, the information processing device 100C may cluster objects belonging to each cluster by any clustering method such as k-means, thereby dividing each cluster and generating blobs. For example, the information processing device 100C may generate blobs BL1 and BL7 by dividing cluster CL1 into two blobs. For example, the information processing device 100C may cluster objects belonging to cluster CL1 by k-means with the number of clusters being 2, divide cluster CL1, and generate blobs BL1 and BL7.

For example, the information processing device 100C may generate blob BL2 and blob BL4 by dividing cluster CL2 into two blobs. For example, the information processing device 100C may generate blob BL3, blob BL8, and blob BL10 by dividing cluster CL3 into three blobs. For example, the information processing device 100C may generate blob BL5, blob BL6, and blob BL9 by dividing cluster CL4 into three blobs.

4-2. Configuration of information processing device
Next, the configuration of an information processing device 100C according to the fourth embodiment will be described with reference to FIG. 33. FIG. 33 is a diagram showing an example of the configuration of an information processing device according to the fourth embodiment. As shown in FIG. 33, the information processing device 100C has a communication unit 110, a storage unit 120C, and a control unit 130B. Note that in the information processing device 100C, the description of the same points as those of the information processing device 100, the information processing device 100A, or the information processing device 100B will be omitted as appropriate.

(Memory unit 120C)
The storage unit 120C is realized by, for example, a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 33 , the storage unit 120C according to the fourth embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123, a codebook information storage unit 124, a blob information storage unit 125, a blob connection graph information storage unit 126, and a cluster information storage unit 127.

The cluster information storage unit 127 according to the fourth embodiment stores information about clusters that are the second group. The cluster information storage unit 127 stores information about clusters that are units of quantization. The cluster information storage unit 127 may store identification information (such as a cluster ID) that identifies each cluster in association with information (such as a blob ID) that indicates a blob that is the first group and that belongs to that cluster. The cluster information storage unit 127 may also store identification information (such as a cluster ID) that identifies each cluster in association with information (such as an object ID) that indicates an object that belongs to that cluster. The cluster information storage unit 127 may also store information (such as a base point ID) for identifying a base point such as a centroid of the cluster and its vector in association with the identification information (such as a cluster ID) that identifies each cluster.

(Control unit 130C)
The control unit 130C is a controller, and is realized, for example, by a CPU, an MPU, a GPU, etc., executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100C using a RAM as a working area. The control unit 130C is also a controller, and is realized, for example, by an integrated circuit such as an ASIC or an FPGA.

As shown in FIG. 33, the control unit 130C has an acquisition unit 131, a generation unit 132C, a search processing unit 133C, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130C is not limited to the configuration shown in FIG. 33, and may be other configurations as long as they perform the information processing described below.

The acquisition unit 131 according to the fourth embodiment acquires object information indicating a plurality of objects to be the target of a data search. The acquisition unit 131 acquires index information indicating an index for searching a plurality of objects.

The acquisition unit 131 acquires processing information indicating a plurality of blobs for classifying a plurality of objects to be the target of a data search, and a plurality of clusters, which are groups with classifications different from the plurality of blobs and which classify objects belonging to the same blob among the plurality of objects into the same group. The acquisition unit 131 acquires processing information indicating a first number of blobs for classifying the plurality of objects, and a cluster for classifying the plurality of objects into a second number smaller than the first number. The acquisition unit 131 acquires processing information indicating a plurality of clusters in which object groups belonging to each of two or more blobs among the plurality of blobs are classified into one cluster.

The acquisition unit 131 acquires processing information indicating a plurality of blobs used to perform a first process, which is a batch process in a search process targeting a plurality of objects. The acquisition unit 131 acquires processing information indicating a plurality of clusters used to perform a second process, which is a process related to quantization targeting a plurality of objects.

The acquisition unit 131 acquires processing information that associates a plurality of first identification information that identifies each of a plurality of blobs with a plurality of second identification information that identifies each of a plurality of clusters. The acquisition unit 131 acquires processing information in which one second identification information is associated with two or more first identification information.

The acquisition unit 131 acquires processing information associated with the first identification information of a blob to which each of the multiple objects belongs. The acquisition unit 131 acquires processing information in which quantized object information obtained by quantizing each of the multiple objects is associated with the first identification information. The acquisition unit 131 acquires processing information in which quantized object information generated by vector quantization, which quantizes each partial vector obtained by dividing a vector corresponding to each of the multiple objects by direct product quantization, is associated with the first identification information. The acquisition unit 131 acquires processing information in which quantized object information generated based on each partial centroid corresponding to each partial area of each centroid corresponding to the quantization is associated with the first identification information. The acquisition unit 131 acquires processing information in which quantized object information generated based on a residual vector generated by each centroid corresponding to the quantization and each partial centroid corresponding to each partial area of each centroid is associated with the first identification information.

(Generation unit 132C)
The generating unit 132C generates various types of information in the same manner as the generating unit 132, the generating unit 132A, or the generating unit 132B.

The generating unit 132C generates blob information indicating a plurality of blobs into which a plurality of objects are classified, based on the object information acquired by the acquiring unit 131. The generating unit 132C generates cluster information indicating a plurality of clusters, which are groups that are classified differently from the plurality of blobs, and which are groups that classify objects that belong to the same blob among the plurality of blobs, among the plurality of objects, into the same group.

The generation unit 132C generates blob information that classifies the multiple objects into a first number of blobs and cluster information that classifies the multiple objects into a second number of clusters that is less than the first number. The generation unit 132C generates cluster information that indicates multiple clusters in which a group of objects belonging to each of two or more blobs among the multiple blobs is classified into one cluster.

The generation unit 132C generates blob information indicating multiple blobs used for batch processing in search processing targeting multiple objects. The generation unit 132C generates blob information indicating multiple blobs used for batch calculation of distances related to multiple objects. The generation unit 132C generates blob information indicating multiple blobs used for parallel processing of calculation of distances between a search query and an object used in search processing.

The generation unit 132C generates cluster information indicating multiple clusters used to perform processing related to quantization of multiple objects. The generation unit 132C generates cluster information indicating multiple clusters that are units of quantization. The generation unit 132C generates cluster information indicating multiple clusters used to quantize vectors corresponding to each of the multiple objects.

After classifying the multiple blobs, the generation unit 132C classifies the multiple clusters. The generation unit 132C generates blob information indicating the multiple blobs by clustering the multiple objects. The generation unit 132C uses index information to generate blob information indicating the multiple blobs. The generation unit 132C uses blob information indicating the blobs to generate cluster information indicating the multiple clusters. The generation unit 132C generates cluster information indicating the multiple clusters by clustering the multiple blobs.

After classifying the multiple clusters, the generation unit 132C classifies the multiple blobs. The generation unit 132C generates cluster information indicating the multiple clusters by clustering the multiple objects. The generation unit 132C generates blob information indicating the multiple blobs using the cluster information indicating the clusters. The generation unit 132C divides at least one of the multiple clusters and generates two or more blobs, thereby generating blob information indicating the multiple blobs. The generation unit 132C generates first group information indicating the multiple first groups by clustering the objects belonging to each second group and dividing each second group into two or more first groups.

(Search processing unit 133C)
The search processing unit 133C functions as a processing unit that executes a first process for objects belonging to a blob and a second process for objects belonging to a cluster. The search processing unit 133C performs various processes related to the search process in the same manner as the search processing unit 133, the search processing unit 133A, or the search processing unit 133B. The search processing unit 133C performs a process using the information generated by the generation unit 132C.

The search processing unit 133C uses the processing information acquired by the acquisition unit 131 to execute a first process targeting objects belonging to a blob and a second process targeting objects belonging to a cluster. The search processing unit 133C executes the second process targeting a group of objects belonging to one cluster. The search processing unit 133C executes the first process targeting a group of objects belonging to one blob.

The search processing unit 133C executes a first process that collectively calculates the distance for a group of objects that belong to one blob. The search processing unit 133C executes a first process that is a parallel process that calculates the distance between each of the group of objects that belong to one blob and a search query used in the search process.

The search processing unit 133C executes a second process, which is quantization, on the group of objects belonging to one cluster. The search processing unit 133C executes a second process, which is quantization, on the group of objects belonging to one cluster. The search processing unit 133C executes a second process that quantizes vectors corresponding to each of the group of objects belonging to one cluster.

When two or more blobs belong to one cluster, the search processing unit 133C executes the second process on the group of objects belonging to the two or more blobs. When two or more blobs belong to one cluster, the search processing unit 133C executes quantization on all objects belonging to the two or more blobs.

The search processing unit 133C executes the first process and the second process by referring to the processing information. The search processing unit 133C identifies an object to be processed by referring to the processing information. In a search process targeting multiple objects, the search processing unit 133C performs the first process targeting a blob of one first identification information among two or more first identification information, and generates reference information to be referenced in the search process for a cluster of one second identification information, and then does not generate reference information when performing the first process targeting other blobs of other first identification information other than the one first identification information among the two or more first identification information.

The search processing unit 133C performs search processing using the blob connection graph. The search processing unit 133C performs search processing to search for nearby objects of the search query using the blob connection graph. The search processing unit 133C performs search processing to search for nearby objects of the search query by tracing edges that connect blobs in the blob connection graph.

In the search process, the search processing unit 133C uses blob information indicating multiple blobs to calculate the distance between a target object, which is an object belonging to one blob, and the search query, using vector information of the vector-quantized target object. The search processing unit 133C performs the calculation of the distance between the target object and the search query in parallel and in a batch. The search processing unit 133C performs the calculation of the distance between the search query and the target objects of the batch processing number determined based on the specifications of the information processing device in parallel.

The search processing unit 133C performs search processing using the processes shown in Figures 27 and 28, using a blob connection graph. For example, the search processing unit 133C performs search processing using graph GR41 that connects blobs with edges, as shown in spatial information SP51. For example, the search processing unit 133C obtains search results for search query QE3 by performing search processing as shown in Figures 27 and 28 using graph GR41, which is a blob connection graph, for search query QE3. For example, the search processing unit 133C performs a first process on the blob that is the processing target by tracing the blob connection graph.

If reference information has not been generated for the cluster to which the blob being processed belongs, the search processing unit 133C generates reference information. For example, the search processing unit 133C generates a distance lookup table (LUT) as reference information. For example, the search processing unit 133C generates a distance lookup table on a cluster-by-cluster basis in the search process. That is, the search processing unit 133C generates a distance lookup table on a cluster-by-cluster basis in the search process. This allows the information processing device 100C to suppress an increase in search time.

The search processing unit 133C uses the generated reference information to perform distance calculations collectively for objects belonging to the blob being processed. For example, if reference information has already been generated for the cluster to which the blob being processed belongs, the search processing unit 133C does not generate reference information. Then, the search processing unit 133C uses the already generated reference information to perform distance calculations collectively for objects belonging to the blob being processed.

[4-3. Examples of processing and information]
From here, examples of processing and information used in the processing in the fourth embodiment will be described.

First, the concept of quantization will be explained using FIG. 34. FIG. 34 is a conceptual diagram of quantization according to the fourth embodiment.

For example, base point CL1 indicates the base point used for quantizing cluster CL1. In this case, base point CL1 indicates the centroid of cluster CL1 that includes blobs BL1 and BL7. Also, for example, base point CL2 indicates the base point used for quantizing cluster CL2. In this case, base point CL2 indicates the centroid of cluster CL2 that includes blobs BL2 and BL4.

For example, base point CL3 indicates the base point used in quantizing cluster CL3. In this case, base point CL3 indicates the centroid of cluster CL3, which includes blobs BL3, BL8, and BL10. Also, for example, base point CL4 indicates the base point used in quantizing cluster CL4. In this case, base point CL4 indicates the centroid of cluster CL4, which includes blobs BL5, BL6, and BL9.

In this case, the information processing device 100C finds a residual vector in each of the four clusters CL1 to CL4. Then, the information processing device 100C performs quantization using the residual vector found in each of the four clusters CL1 to CL4. For example, the information processing device 100C performs quantization using a residual vector from the base point CL1 for objects belonging to cluster CL1. A detailed description of quantization using residual vectors will be omitted, but the information processing device 100C performs quantization using residual vectors by appropriately using, for example, the technology shown in Patent Document 3.

Note that in order to illustrate the invention, FIG. 34 shows a state in which the vector is not divided into partial vectors, but the information processing device 100C may derive a base point for each partial space divided by the Cartesian product quantization, and perform quantization using a residual vector based on the derived base point. For example, when the information processing device 100C divides a vector into four partial vectors and performs Cartesian product quantization, there is a base point for each subspace corresponding to each partial vector, and quantization is performed using a residual vector from the base point.

Below, an example of object quantization and quantization processing by the information processing device 100C will be described with reference to FIG. 34. In FIG. 34, a case where the query object (search query) is search query QE3 will be described as an example. Note that in the quantization and direct product quantization of objects (vectors) described below, detailed descriptions of points similar to those disclosed in Patent Document 3 will be omitted as appropriate.

As shown in the spatial information SP52 of FIG. 34, the distance between the search query QE3 and each vector corresponding to each object belonging to cluster CL1 such as node N7 is different, but the information processing device 100C does not use the vector corresponding to each object belonging to cluster CL1 such as node N7. In this case, the distance between the search query QE3 and each vector is regarded as, for example, the distance between the search query QE3 and the vector corresponding to the base point CL1 of cluster CL1. That is, the vector corresponding to each object belonging to cluster CL1 is quantized to a vector corresponding to the base point CL1. Specifically, the information processing device 100C obtains a residual vector, which is the difference between each vector from the base point CL1, and performs direct product quantization on the residual vector (further dividing into subspaces and quantizing).

For example, the information processing device 100C further divides each cluster into a plurality of partial regions, and generates partial centroids corresponding to the plurality of partial regions as a codebook. For example, the information processing device 100C may generate partial centroids corresponding to the plurality of partial regions into which each cluster is divided, based on information on the residual vector related to each cluster.

For example, the information processing device 100C may determine the number of partial regions of each cluster based on the number of objects included in each cluster, or may determine the number of partial regions based on a predetermined setting value. For example, the information processing device 100C may determine partial regions by appropriately using various conventional technologies related to clustering. For example, the information processing device 100C calculates a residual vector from the objects included in each partial region of the cluster CL1 and the base point CL1 of the cluster CL1, and generates a partial centroid of the partial region from the residual vector. For example, the information processing device 100C uses information on the residual vector between the base point of the cluster and the partial centroid of each partial region. For example, the information processing device 100C uses information on the residual vector between the base point CL1 of the cluster CL1 and the partial centroid of each partial region. For example, the information processing device 100C stores information on the partial centroid of the partial region to which the object belongs in association with each object.

For example, by using the above-mentioned information, the information processing device 100C can quantize the position of each object to the position of the centroid of the partial region to which the vector belongs. This allows the information processing device 100C to refine the distance between the search query QE3 and each object to the distance between the search query QE3 and the vector corresponding to the partial centroid of the partial region to which each object belongs.

For example, the information processing device 100C uses information indicating the vector of the base point of each cluster and the residual vector related to the partial centroid. This allows the information processing device 100C to calculate the distance to the partial centroid for, for example, search query QE3. Therefore, the information processing device 100C can determine the distance between, for example, search query QE3 and each object as the distance to a partial centroid that is even closer than the base point of the cluster.

The information processing device 100C may divide the vector of each object into multiple partial vectors for processing. That is, the information processing device 100C may perform processing using a technique related to so-called direct product quantization. This is similar to the first embodiment described above, and therefore redundant explanations will be omitted as appropriate.

For example, in the case of FIG. 34, the information processing device 100C divides the vector of search query QE3 into multiple partial vectors (also referred to as "partial vectors of search query QE3"). In this case, the spatial information SP52 is also divided into multiple subspaces (also referred to as "subspaces of spatial information SP52"). For example, the information processing device 100C may divide the vector of search query QE3 into four, as in FIG. 1. In this case, the spatial information SP52 is also divided into four subspaces, and each cluster is divided into multiple subspaces.

For example, the information processing device 100C stores information indicating a partial centroid (codebook) corresponding to the area to which each object belongs in the four subspaces in association with each object. For example, the information processing device 100C calculates the distance between each object and the search query QE3 by summing up the distances between the four codebooks corresponding to each object and the search query QE3.

Next, an overview of an inverted index will be described with reference to Figs. 35 and 36. Fig. 35 is a diagram showing an example of an inverted index according to the fourth embodiment. Fig. 36 is a diagram showing a specific example of an inverted index according to the fourth embodiment.

First, the transposed index IND1 shown in FIG. 35 will be described. The transposed index IND1 shown in FIG. 35 includes items such as "blob ID", "cluster ID", "number of quantized objects", "quantized object #1", "quantized object #2", "quantized object #3", and "quantized object #4". Note that FIG. 35 illustrates four objects, "quantized object #1" to "quantized object #4", but the transposed index IND1 includes items such as "quantized object #5", "quantized object #6", and so on, the number of which corresponds to the number of objects belonging to each blob.

"Blob ID" indicates identification information for identifying a blob, which is the first group. "Cluster ID" indicates identification information for identifying a cluster, which is the second group. "Number of quantized objects" indicates the number of objects belonging to a blob. "Quantized object #1" to "Quantized object #4" indicate quantized objects. For example, "Quantized object #1" to "Quantized object #4" store a list of information indicating the codebook corresponding to each partial vector after the objects are product quantized.

In the example of FIG. 35, a blob with blob ID "1" belongs to a cluster with cluster ID "2", and the number of objects belonging to the cluster is four. For a blob with blob ID "1", "quantization object #1" stores "4, 2, 8, 10", indicating that the object is composed of four partial vectors, which are quantized with codebooks "4", "2", "8", and "10". For example, for an object corresponding to "quantization object #1" with blob ID "1", the first partial vector of the four divided partial vectors is quantized with codebook "4", the second partial vector is quantized with codebook "2", the third partial vector is quantized with codebook "8", and the last partial vector is quantized with codebook "10".

The transposed index IND1 may store various information according to the purpose, not limited to the above. For example, the transposed index IND1 may store information indicating each quantized object (such as an object ID) in association with each quantized object.

Next, the transposed index IND2 shown in FIG. 36 will be described. FIG. 36 shows a specific example of a transposed index corresponding to the example shown in FIG. 32, etc. Note that the description of the same points as in the transposed index IND1 will be omitted as appropriate. The transposed index IND2 shown in FIG. 36 includes items such as "blob ID", "cluster ID", "number of quantized objects", "quantized object #1", etc. Note that while FIG. 36 only illustrates "quantized object #1", like the transposed index IND1, it includes items in the number corresponding to the number of objects belonging to each blob.

In the transposed index IND2, similar to the spatial information SP51 shown in FIG. 32, it is indicated that the blob BL1 identified by the blob ID "BL1" belongs to the cluster CL1, which has the cluster ID "CL1". It is also indicated that the number of objects belonging to the blob BL1 is "NM1". Note that although it is indicated by an abstract code such as "NM1" in FIG. 36, a value indicating a concrete number (e.g., 10 or 100) is stored in the "quantized object number" as in the transposed index IND1.

Blob BL1 also indicates that "Quantized Object #1" stores "CD51, CD64, CD77, CD82", and that the object is composed of four partial vectors, each of which has been quantized using the codebooks "CD51", "CD64", "CD77", and "CD82".

Furthermore, in the transposed index IND2, similar to the spatial information SP51 shown in FIG. 32, it is indicated that the blob BL2 identified by the blob ID "BL2" belongs to the cluster CL2 with the cluster ID "CL2". Further, in the transposed index IND2, similar to the spatial information SP51 shown in FIG. 32, it is indicated that the blob BL7 identified by the blob ID "BL7" belongs to the cluster CL1 with the cluster ID "CL1".

The transposed index IND2 is not limited to the above, and may store various information depending on the purpose. For example, the transposed index IND2 may store information indicating each quantized object (such as an object ID) in association with each quantized object. In this way, the transposed index is assigned information identifying a cluster (cluster ID), and the information processing device 100C calculates a residual vector using the transposed index. For example, the residual vector is used when generating and searching an index, but detailed description will be omitted as appropriate because it is similar to the processing in conventional techniques such as Patent Document 3.

[4-4. Information processing flow]
Next, a procedure of information processing according to the fourth embodiment will be described with reference to Fig. 37 and Fig. 38. Fig. 37 and Fig. 38 are flowcharts showing an example of information processing according to the fourth embodiment.

First, FIG. 37 will be described. For example, FIG. 37 is a flowchart showing an example of a group generation process. As shown in FIG. 37, the information processing device 100C acquires object information indicating multiple objects to be the target of data search (step S601). For example, the information processing device 100C acquires object information indicating multiple objects from the object information storage unit 121.

The information processing device 100C generates first group information indicating a plurality of first groups into which the plurality of objects are classified based on the object information (step S602). For example, the information processing device 100C generates blob information indicating a plurality of blobs into which the plurality of objects are classified based on the object information.

The information processing device 100C generates second group information indicating a plurality of second groups, which are groups classified differently from the plurality of first groups, and which classify, among the plurality of objects, objects that belong to the same first group in the plurality of first groups into the same group (step S603). For example, the information processing device 100C generates cluster information indicating a plurality of clusters, at least one of which includes two or more blobs. Note that the information processing device 100C may generate cluster information indicating clusters that correspond one-to-one to blobs.

Next, FIG. 38 will be described. For example, FIG. 38 is a flowchart showing an example of processing using groups. As shown in FIG. 38, the information processing device 100C acquires processing information indicating a plurality of first groups into which a plurality of objects to be subjected to data search are classified, and a plurality of second groups which are groups that are classified differently from the plurality of first groups and which classify objects belonging to the same first group among the plurality of objects into the same group (step S701). For example, the information processing device 100C acquires, as processing information, blob information stored in the blob information storage unit 125 and cluster information stored in the cluster information storage unit 127. For example, the information processing device 100C acquires the transposed index IND1 or the transposed index IND2.

The information processing device 100C uses the processing information to execute a first process targeting objects belonging to a first group and a second process targeting objects belonging to a second group (step S702). For example, the information processing device 100C executes a batch process targeting objects belonging to a blob, and executes quantization targeting objects belonging to a cluster.

5. Fifth embodiment
In addition, when performing a search process using a blob connection graph (also called a "blob graph") that connects blobs as described above, a search range from multiple perspectives may be used. This point will be described below as a fifth embodiment. In the fifth embodiment, the information processing system 1 has an information processing device 100D instead of the information processing device 100, the information processing device 100A, the information processing device 100B, or the information processing device 100C. Note that the same points as those described above in the first embodiment, the second embodiment, the third embodiment, the fourth embodiment, and the like will not be described as appropriate. For example, the blob BL* (* is an arbitrary number) in the following description is a group obtained by grouping objects similarly to the above-mentioned blob BL* (* is an arbitrary number), so a detailed description will be omitted. In addition, the centroid C* (* is an arbitrary number) in the following description is similar to the above-mentioned centroid C* (* is an arbitrary number), so a detailed description will be omitted. In the following description, cluster CL* (* is an arbitrary number) is a cluster for classifying blobs in the same manner as cluster CL* (* is an arbitrary number) described above, and therefore a detailed description thereof will be omitted.

In addition, in Figures 39 and 40, the representation is the same as in Figure 32, except that the distinction between clusters is indicated by thick solid lines and the connections between blobs are indicated by dotted lines connecting the centroids C of blobs BL. For example, among the solid lines, thick lines indicate the division correspondence of clusters and blobs, and thin lines indicate the division correspondence of blobs. For example, in Figures 39 and 40, among the solid lines, thin lines indicate the division correspondence of blobs within clusters. Also, in Figures 39 and 40, centroids CN11 to CN14 indicate the centroids of each of clusters CL11 to CL14. Cluster CL11 includes three blobs BL, BL11, BL12, and BL13. Blob BL11 includes nodes N31, N205, etc. Cluster CL12 includes two blobs BL, blobs BL14 and BL15. Cluster CL13 includes three blobs BL: blobs BL16, BL17, and BL18. Cluster CL14 includes two blobs BL: blobs BL19 and BL20. Note that the clusters CL, blobs BL, and nodes N shown in Figures 39 and 40 are only a partial list, and the clusters CL, blobs BL, and nodes N to be processed include many more clusters CL, blobs BL, and nodes N in addition to those shown. Also, the symbols for the blobs BL and clusters CL are shown only in Figure 39 and are omitted in Figure 40, but Figures 39 and 40 show the same spatial information (spatial information SP61).

The information processing device 100D executes a search process using a blob graph, which is a group connection graph in which multiple groups into which multiple objects to be searched for data are classified are connected by edges. The information processing device 100D also executes a search process using a range corresponding to a search for blobs, which are groups (hereinafter also referred to as a "first search range"), and a range corresponding to a search for multiple objects (hereinafter also referred to as a "second search range"). In this way, the information processing device 100D extracts nearby objects corresponding to the search query from the multiple objects.

5-1. Information Processing
First, an overview of the information processing according to the fifth embodiment will be described with reference to Figs. 39 and 40. Figs. 39 and 40 are diagrams showing an example of the information processing according to the fifth embodiment. Specifically, Fig. 39 shows an overall overview of the search processing performed by the information processing device 100D. Also, Fig. 40 shows the changes in the first search range and the second search range in the search processing performed by the information processing device 100D. Thus, Figs. 39 and 40 explain the changes in the first search range and the second search range and the overview of the search processing, and the specific flow of the search processing is shown in Fig. 43.

Graph GR61 shown in spatial information SP61 in Figure 39 is a blob graph connecting blobs, similar to graph GR41 shown in spatial information SP51 in Figure 32. For example, the dotted lines (edges) connecting the centroids C of blobs BL in graph GR61 are synonymous with the arrowed lines (edges) connecting blobs BL to each other in graph GR41. Graph GR61 in Figure 39 illustrates a portion of blobs BL11 to BL20. For example, information processing device 100D may generate information indicating blobs BL11 to BL10, etc. using the method described above, or may obtain information indicating blobs BL11 to BL10, etc. from another device. Note that the spatial information SP61-1 to SP61-4 in FIG. 40 are given different reference numbers for the convenience of explaining the changes in the first search range and the second search range, but they are similar to the spatial information SP61 in FIG. 39, and when explaining without distinction, they may be referred to as spatial information SP61.

Graph GR61 may be in a state where the graph GR41 illustrates the blobs BL11 to BL20. In this case, the spatial information SP51 and the spatial information SP61 target the same multiple objects, and the graph GR61 and the graph GR41 illustrate different parts of the same graph. For example, the graph GR41 in FIG. 32 may illustrate the blobs BL1 to BL10, and the graph GR61 may illustrate the blobs BL11 to BL20. The graph GR61 may also be a graph in which the centroids of each blob are connected, as in the graph GR42 in FIG. 29. In other words, the graph GR61 may be a graph in which the blobs are connected in any manner, as long as the search process described below can be executed.

Figure 39 shows an example of processing when the query is search query QE11 and the number of objects to be extracted as nearby objects (also called the "number of nearby objects extracted") is "5". Of the five circles centered on search query QE11, the dashed-dotted circle indicates blob search range SB, which is an example of the first search range. Note that in Figure 39, of the three dashed-dotted circles indicating the blob search range SB, only the circle with the largest radius is given the symbol "SB", but the three dashed-dotted circles indicate the blob search range SB that changes during the search process.

For example, blob search range SB is a first search range defined by a radius (blob search radius) centered on search query QE11. As indicated by the dashed dotted arrow in FIG. 39, the range (radius) of blob search range SB becomes wider as the search process progresses, but this point will be described later with reference to FIG. 40. Note that blob search ranges SB1, SB2, and SB3 shown in FIG. 40 correspond to the three blob search ranges SB in FIG. 39. When describing the blob search ranges SB1, SB2, and SB3 without distinguishing between them, they may be referred to as blob search ranges SB.

In addition, in FIG. 39, of the five circles centered on the search query QE11, the two-dot chain circle indicates the object search range SO, which is an example of the first search range. Note that in FIG. 39, of the two two-dot chain circles indicating the object search range SO, only the outer circle is marked with the symbol "SO", but the two two-dot chain circles indicate the object search range SO that changes during the search process.

For example, object search range SO is a second search range defined by a radius (object search radius) centered on search query QE11. As indicated by the two-dot dashed arrow in FIG. 39, the range (radius) of object search range SO becomes smaller as the search process progresses, but this point will be described later with reference to FIG. 40. Note that object search ranges SO1 and SO2 shown in FIG. 40 correspond to the two object search ranges SO in FIG. 39. When the object search ranges SO1 and SO2 are not to be distinguished from each other, they may be referred to as object search range SO.

First, the information processing device 100D starts the search process from the state shown in the spatial information SP61-1. Then, as shown in the spatial information SP61-2, the information processing device 100D determines the blob search range SB to be the blob search range SB1, and determines the object search range SO to be infinity "∞". That is, in FIG. 40, the information processing device 100D determines the blob search range SB to be the blob search range SB1, which is defined by a radius based on the distance between the nearest blob BL20 and the search query QE11. Also, in FIG. 40, the information processing device 100D extracts three of the nodes N2, N6, and N8 to which the blob BL20 belongs (objects corresponding to them) as candidates for nearby objects corresponding to the search query QE11, and adds them to the nearby object candidates. Note that there are three nearby object candidates, which is less than or equal to "5" in the nearby object extraction count, so the object search range SO is maintained at infinity "∞".

Then, as shown in the spatial information SP61-3, the information processing device 100D determines the blob search range SB to be the blob search range SB2, and determines the object search range SO to be the object search range SO1. That is, in FIG. 40, the information processing device 100D determines the blob search range SB to be the blob search range SB2, which is defined by a radius based on the distance between the search query QE11 and the blob BL11 that is the next closest to the blob BL20. Also, in FIG. 40, the information processing device 100D extracts three of the nodes N31, N205, and N312 to which the blob BL11 belongs (objects corresponding to the nodes), as candidates for nearby objects corresponding to the search query QE11, and adds them to the nearby object candidates. As a result, the nearby object candidates include six nodes N2, N6, N8, N31, N205, and N312, exceeding the nearby object extraction number "5". Therefore, the information processing device 100D keeps the five nearest neighboring object candidates from the search query QE11 and excludes the rest. In this case, the information processing device 100D excludes node N312, which is the furthest from the search query QE11, among the six nodes, and sets the number of neighboring object candidates to five. That is, the information processing device 100D sets the number of neighboring object candidates to five, namely nodes N2, N6, N8, N31, and N205. Because the number of neighboring object candidates has reached the number of neighboring object extractions "5", the information processing device 100D determines the object search range SO to be object search range SO1, which is defined by a radius based on the distance between the search query QE11 and node N205, which is the farthest from the search query QE11 among the neighboring object candidates.

Then, as shown in the spatial information SP61-4, the information processing device 100D determines the blob search range SB to be the blob search range SB3, and determines the object search range SO to be the object search range SO2. That is, in FIG. 40, the information processing device 100D determines the blob search range SB to be the blob search range SB3, which is defined by a radius based on the distance between the search query QE11 and the blob BL19, which is the next closest to the blob BL11. Also, in FIG. 40, the information processing device 100D extracts three of the nodes N3, N11, and N114 to which the blob BL19 belongs (objects corresponding to the nodes), as candidates for nearby objects corresponding to the search query QE11, and adds them to the nearby object candidates. As a result, the nearby object candidates include eight nodes N2, N6, N8, N31, N205, N3, N11, and N114, exceeding the nearby object extraction number "5". Therefore, the information processing device 100D keeps five of the nearby object candidates closest to the search query QE11 and excludes the rest. In this case, the information processing device 100D excludes three nodes N205, N3, and N114 from the farthest distance from the search query QE11, leaving the number of nearby object candidates at five. That is, the information processing device 100D leaves the nearby object candidates at five, namely nodes N2, N6, N8, N11, and N31. Then, the information processing device 100D determines the object search range SO to be an object search range SO2, which is defined by a radius based on the distance between the search query QE11 and node N11, which is the nearby object candidate farthest from the search query QE11.

The information processing device 100D repeats the above-described process until termination criteria #1 to #3 described below are met. For example, when termination criteria #1 to #3 are met, the information processing device 100D determines that the objects included in the nearby object candidates at that time are nearby objects of the search query QE11. Then, the information processing device 100D provides information indicating the objects determined to be nearby objects of the search query QE11 to the source of the search request that specified the search query QE11, etc.

As described above, the information processing device 100D performs search processing using search ranges from multiple perspectives, such as a first search range and a second search range, and can perform flexible search processing using graphs by changing each search range depending on the status of the search processing.

For example, in a blob graph, a large blob graph can slow down search speeds due to unnecessary blob references. In addition, a conventional method for Product Quantization (PQ) is to search a graph to identify nearby blobs and then calculate approximate distances for the identified blobs, but even in this case, unnecessary blob references slow down search speeds.

On the other hand, the information processing device 100D searches the blob graph and calculates the approximate distance of objects within each blob for which the ranking in order of proximity has been determined, and ends the search when a specified termination criterion is met, thereby reducing unnecessary object searches.

5-2. Configuration of information processing device
Next, the configuration of an information processing device 100D according to the fifth embodiment will be described with reference to FIG. 41. FIG. 41 is a diagram showing an example of the configuration of an information processing device according to the fifth embodiment. As shown in FIG. 41, the information processing device 100D has a communication unit 110, a storage unit 120C, and a control unit 130B. Note that in the information processing device 100D, the description of the same points as those of the information processing device 100, the information processing device 100A, the information processing device 100B, or the information processing device 100C will be omitted as appropriate.

(Memory unit 120C)
The storage unit 120C is realized by, for example, a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 41 , the storage unit 120C according to the fifth embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123, a codebook information storage unit 124, a blob information storage unit 125, a blob connection graph information storage unit 126, and a cluster information storage unit 127.

(Control unit 130D)
The control unit 130D is a controller, and is realized, for example, by a CPU, an MPU, a GPU, etc., executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100D using a RAM as a working area. The control unit 130D is also a controller, and is realized, for example, by an integrated circuit such as an ASIC or an FPGA.

As shown in FIG. 41, the control unit 130D has an acquisition unit 131, a generation unit 132C, a search processing unit 133D, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130D is not limited to the configuration shown in FIG. 41, and may be other configurations as long as they perform the information processing described below.

The acquisition unit 131 according to the fifth embodiment acquires various pieces of information from the storage unit 120C. For example, the acquisition unit 131 according to the fifth embodiment acquires various pieces of information used by the generation unit 132C, similar to the acquisition unit 131 according to the fourth embodiment.

The acquisition unit 131 acquires a group connection graph in which a plurality of groups into which a plurality of objects to be the subject of data search are classified are connected by edges. The acquisition unit 131 acquires a search query for a plurality of objects.

(Search processing unit 133D)
The search processing unit 133D executes the search process shown in Fig. 43. For example, the search processing unit 133D performs various processes related to the search process in the same manner as the search processing unit 133, the search processing unit 133A, the search processing unit 133B, or the search processing unit 133BC. The search processing unit 133D performs a process using the information stored in the storage unit 120C. The search processing unit 133D performs a process using the information generated by the generation unit 132C.

The search processing unit 133D executes a search process to extract nearby objects corresponding to a search query from multiple objects by searching the group connection graph using a first search range indicating a range corresponding to a search of multiple groups and a second search range indicating a range corresponding to a search of multiple objects. The search processing unit 133D executes a search process using the first search range and the second search range that is wider than the first search range.

The search processing unit 133D executes the search process using a first search range that expands as the search process progresses. The search processing unit 133D executes the search process using a first search range that is determined based on one of the multiple groups that is the target of the search process. The search processing unit 133D executes the search process using a first search range that is determined based on one group during the search process. The search processing unit 133D executes the search process using a first search range that is based on the distance between the search query and an object that is closest to the search query among the objects included in the one group, or the centroid of the one group.

The search processing unit 133D executes the search process using a second search range that narrows as the search process progresses. The search processing unit 133D executes the search process using a second search range that is determined based on one object that is the target of the search process among multiple objects. The search processing unit 133D executes the search process using a second search range that is determined based on one object that is the farthest from the search query among objects extracted during the search process as candidates for nearby objects corresponding to the search query. The search processing unit 133D executes the search process using the second search range that is based on the distance between the search query and the one object.

The search processing unit 133D ends the search process when a predetermined termination condition is met. The search processing unit 133D ends the search process when the number of groups targeted by the search process meets the condition. The search processing unit 133D ends the search process when the number of groups targeted by the search process exceeds a predetermined threshold.

The search processing unit 133D ends the search process when the distance for the specified group exceeds the second search range. The search processing unit 133D ends the search process when the distance for the specified group during the search process exceeds the second search range. The search processing unit 133D ends the search process when the distance between the search query and an object closest to the search query among the objects included in the specified group exceeds the second search range.

The search processing unit 133D ends the search process if the magnitude relationship between the first search range and the second search range satisfies the condition. The search processing unit 133D ends the search process if the first search range exceeds the second search range.

5-3. Information processing flow
Next, a procedure of information processing according to the fifth embodiment will be described with reference to Fig. 42. Fig. 42 is a flowchart showing an example of information processing according to the fifth embodiment.

First, FIG. 42 will be described. For example, FIG. 42 is a flowchart showing an example of a group generation process. As shown in FIG. 42, the information processing device 100D acquires a group connection graph in which a plurality of groups into which a plurality of objects to be the subject of data search are classified are connected by edges (step S801). For example, the information processing device 100D acquires a blob connection graph from the blob connection graph information storage unit 126 as the group connection graph.

The information processing device 100D acquires a search query for multiple objects (step S802). For example, the information processing device 100D acquires a search query from a terminal device 10 (see FIG. 4) used by the user.

The information processing device 100D executes a search process to extract nearby objects corresponding to the search query from the multiple objects by searching the group connection graph using a first search range indicating a range corresponding to a search of multiple groups and a second search range indicating a range corresponding to a search of multiple objects (step S803). For example, the information processing device 100D executes the search process shown in FIG. 43 using a blob search range, which is the first search range, and an object search range, which is the second search range.

5-4. Search processing example
Here, an example of the search process according to the fifth embodiment will be described with reference to FIG. 43. FIG. 43 is a flowchart showing an example of the search process according to the fifth embodiment. The search process described below is performed by the search processing unit 133D of the information processing device 100D. Note that the description of the same points as those of the search processes described in the first, second, third and fourth embodiments will be omitted as appropriate.

The information processing device 100D acquires a search blob starting set, and calculates the distance between each object and the query (step S901). For example, the information processing device 100D acquires a search blob starting set indicating a blob that is the starting point of the search, and calculates the distance between each object included in the blob of the search blob starting set and the query. For example, the information processing device 100D may randomly select the search blob starting set, or may select the search blob starting set using a predetermined index, such as an index of a tree structure with blobs as leaves. For example, the information processing device 100D calculates the approximate distance between each object included in the blob of the search blob starting set and the query by calculating the approximate distance described above.

The information processing device 100D determines the nearest blob to the query in the search blob starting set as the current nearest blob B (hereinafter also simply referred to as "blob B") (step S902). For example, the information processing device 100D determines the blob that is closest to the query in the search blob starting set as the current nearest blob B.

The information processing device 100D sets various parameters (step S903). In FIG. 43, the information processing device 100D sets the number of blob searches to "1". Furthermore, the information processing device 100D sets the object search radius R indicating the second search range (object search range) to "∞ (infinity)". For example, the object search radius R is a radius centered on the query q that defines the second search range. Furthermore, the information processing device 100D sets the object search radius E, which is an example of the second search range, to "∞ (infinity)".

The information processing device 100D also sets the blob search radius Rb, which is an example of the first search range (blob search range), to "d(q,B)". For example, the blob search radius Rb is a radius centered on the query q that defines the first search range. For example, the information processing device 100D sets the blob search radius Rb to the distance d(q,B) between the query q and the current nearest blob B. For example, the information processing device 100D sets the blob search radius Rb to the distance d(q,B) between the query q and the object closest to the query q among the objects included in the current nearest blob B. Note that the blob search radius Rb may be the distance between the query q and the centroid of the current nearest blob B. The information processing device 100D also sets the blob search radius Eb, which indicates the first search range (blob search range), to "Rb x (1 + eb)". Here, the parameter eb is the blob search radius expansion rate (also called the "first search range coefficient"), and is set to an arbitrary value such as 0.1. For example, the information processing device 100D sets the blob search radius Eb to a value obtained by multiplying the blob search radius Rb by 1 + eb.

The information processing device 100D adds the search blob origin set other than blob B to the excluded blob set (step S904). For example, the information processing device 100D adds blobs from the search blob origin set other than the current nearest blob B to the excluded blob set.

The information processing device 100D adds the search blob starting set to the unsearched blob set and the distance-calculated set (step S905). For example, the information processing device 100D adds all blobs in the search blob starting set, including the current nearest blob B, to the unsearched blob set, which indicates that they have not yet been subjected to search processing. For example, the information processing device 100D adds all blobs in the search blob starting set, including the current nearest blob B, to the distance-calculated set, which indicates that distance calculation processing has been performed for the objects in the blobs.

The information processing device 100D determines whether the unsearched blob set is empty (step S906). If the unsearched blob set is not empty (step S906: No), the information processing device 100D acquires a blob T that is closest to the query from the unsearched blob set (step S907). As a result, the unsearched blob set is removed from the unsearched blob set. For example, the information processing device 100D acquires, as blob T, a blob that has the shortest distance from the query q among the unsearched blob set. For example, the distance from the query q is the distance between the query q and the object that is closest to the query q among the objects included in the blob. Note that the distance from the query q may be the distance between the query q and the centroid of the blob.

The information processing device 100D determines whether the blob T is within the blob search range (step S908). For example, the information processing device 100D determines whether the distance between the blob T and the query q is less than or equal to the blob search radius Eb.

If blob T is within the blob search range (step S908: Yes), the information processing device 100D determines whether all blobs connected by edges to blob T have been processed (step S909). For example, the information processing device 100D determines whether all connected blobs of blob T have been processed using information indicating whether or not blobs connected to blob T by edges (also called "connected blobs") have been processed ("processing information") For example, the information processing device 100D may manage whether or not connected blobs of blob T have been processed using information such as a flag. For example, the information processing device 100D may update the processing information stored in the storage unit 120C according to the processing status, and may determine whether all connected blobs of blob T have been processed by referring to the processing information in the storage unit 120C.

When the information processing device 100D has not processed all the blobs connected to blob T via edges (step S909: No), it acquires blob J connected to blob T via an edge (step S910). For example, the information processing device 100D acquires as blob J a blob that is connected to blob T via an edge and has not been processed as a blob connected to blob T via an edge (also called an "unprocessed connected blob"). For example, the information processing device 100D refers to the processing presence/absence information, acquires as blob J an unprocessed connected blob from among the blobs connected to blob T via an edge, and updates the processing presence/absence information for the blob acquired as blob J to processed.

The information processing device 100D determines whether or not blob J exists in the distance-calculated set (step S911). If blob J exists in the distance-calculated set (step S911: Yes), the information processing device 100D returns to step S909 and performs processing.

If blob J does not exist in the distance-calculated set (step S911: No), the information processing device 100D adds blob J to the distance-calculated set (step S912) and adds blob J to the unsearched blob set (step S913). Then, the information processing device 100D calculates the distance De between the centroid of blob J and the query (step S914).

The information processing device 100D determines whether the distance De is smaller than the blob search radius Rb (step S915). If the distance De is not smaller than the blob search radius Rb (step S915: No), the information processing device 100D adds the blob J to the excluded blob set (step S916) and returns to step S909 to perform processing.

Furthermore, if the distance De is smaller than the blob search radius Rb (step S915: Yes), the information processing device 100D adds the current nearest blob B to the excluded blob set and sets blob J as the current nearest blob B (step S917). In this way, if the distance De is smaller than the blob search radius Rb, the information processing device 100D updates the current nearest blob B to blob J.

Then, the information processing device 100D updates the parameters related to the blob based on the current nearest blob B updated to blob J (step S918). In FIG. 43, the information processing device 100D updates the blob search radius Rb to "d(q, B)" based on the current nearest blob B updated to blob J. Also, the information processing device 100D updates the blob search radius Eb to "Rb x (1 + eb)" based on the updated blob search radius Rb. The information processing device 100D then returns to step S909 to perform processing.

When the information processing device 100D has processed all the blobs connected by the edges of blob T (step S909: Yes), it returns to step S906 and performs the process. When the unsearched blob set is empty (step S906: Yes), the information processing device 100D performs the process of step S920. Furthermore, when blob T is not within the blob search range (step S908: No), the information processing device 100D returns blob T to an unsearched blob (step S919) and performs the process of step S920.

In step S920, the information processing device 100D adds 1 to the blob search count (step S920). Then, the information processing device 100D calculates the approximate distances of all objects in blob B, and sets the shortest distance as the blob distance of the blob B (step S921). For example, the information processing device 100D calculates the approximate distance between query q for all objects in blob B, and sets the distance between query q and the object closest to query q among the objects included in the current nearest blob B as the blob distance of blob B. Note that the blob distance of blob B is used in the end determination process in step S924.

The information processing device 100D adds and sorts all objects in blob B to the search result set, and sets only the objects with the highest specified number of searches as the search result set (step S922). For example, the information processing device 100D adds all objects in blob B to the search result set that indicates candidates for objects near query q. Then, the information processing device 100D updates the search result set by sorting the objects in the search result set after adding the objects in blob B in order of the shortest distance from query q, and excludes objects in the updated search result set that are lower than the specified number of searches (e.g., 5, 10, etc.) from the search result set. For example, the information processing device 100D leaves the objects in the search result set after adding the objects in blob B from the objects with the shortest distance from query q up to the search number (e.g., 5, 10, etc.) (i.e., objects with the number of searches) and excludes the rest.

Then, the information processing device 100D updates the parameters related to the object based on the updated search result set (step S923). In FIG. 43, the information processing device 100D updates the object search radius R to the maximum distance of the object in the search result set based on the updated search result set. For example, the information processing device 100D updates the object search radius R to the distance of the object farthest from the query q in the search result set. Furthermore, the information processing device 100D sets the object search radius E to "R x (1 + eo)" based on the updated search result set. Here, the parameter eo is an object search radius expansion rate (also called the "second search range coefficient"), and an arbitrary value such as 0.05 is set. For example, the parameter eo corresponds to the above-mentioned search range coefficient "ε". For example, the information processing device 100D sets the object search radius E to a value obtained by multiplying the object search radius R by 1 + eo. The parameters eo and eb may be the same value.

Then, the information processing device 100D determines whether the termination criteria #1 to #3 are met (step S924). The information processing device 100D determines whether the processing status meets any of the termination criteria #1 to #3 based on each termination condition. Termination criterion #1 is to terminate the process when the upper limit number of blob searches is exceeded. For example, termination criterion #1 is a criterion that is conditioned on the number of blob searches, which is a parameter, exceeding the upper limit number of searches (any value, such as 5, 10, etc.).

Termination criterion #2 is to terminate when the blob distance exceeds the object search radius. For example, termination criterion #2 is a criterion that requires that the blob distance exceeds the object search radius E. Termination criterion #3 is to terminate when the blob search radius exceeds the object search radius. For example, termination criterion #3 is a criterion that requires that the blob search radius Eb exceeds the object search radius E. Note that the above termination criteria #1 to #3 are merely examples, and various termination criteria may be used. Furthermore, multiple termination criteria may be used in combination.

If termination criteria #1 to #3 are not met (step S924: No), the information processing device 100D acquires the blob with the shortest distance from the excluded blob set, and sets it as the current nearest blob B (step S925). For example, the information processing device 100D acquires the blob with the shortest distance to the query q from the excluded blob set as the current nearest blob B. This removes the blob with the shortest distance at that time from the excluded blob set. For example, the information processing device 100D updates the current nearest blob B to the blob with the shortest distance to the query q from the excluded blob set.

Then, the information processing device 100D updates the parameters related to the blob based on the current nearest blob B that has been updated to the blob with the shortest distance (step S926). In FIG. 43, the information processing device 100D updates the blob search radius Rb to "d(q, B)" based on the current nearest blob B that has been updated to the blob with the shortest distance. Also, the information processing device 100D updates the blob search radius Eb to "Rb x (1 + eb)" based on the updated blob search radius Rb. The information processing device 100D then returns to step S906 and performs processing.

Furthermore, if termination criteria #1 to #3 are met (step S924: Yes), the information processing device 100D terminates the process. For example, if termination criteria #1 to #3 are met, the information processing device 100D determines that the objects included in the search result set at that point in time are objects in the vicinity of query q. Then, the information processing device 100D provides information indicating the objects determined to be objects in the vicinity of query q to the source of the search that specified query q, etc.

6. Sixth embodiment
The above-mentioned search process is merely an example, and any search process may be executed using information on a plurality of groups obtained by grouping (classifying) objects. This will be described below as the sixth embodiment. In the sixth embodiment, a search process example will be shown in which the first group (blob) and the second group (cluster) shown in the above example match. Therefore, in the sixth embodiment, the first group (blob) and the second group (cluster) are not particularly distinguished from each other, and are simply referred to as "group" or "blob".

In the sixth embodiment, the information processing system 1 has an information processing device 100E instead of the information processing device 100, the information processing device 100A, the information processing device 100B, the information processing device 100C, or the information processing device 100D. Note that the description of the same points as those described above in the first embodiment, the second embodiment, the third embodiment, the fourth embodiment, the fifth embodiment, etc. will be omitted as appropriate.

[6-1. Information Processing]
The information processing device 100E executes a search process to extract nearby objects corresponding to a search query using information on a plurality of groups that classify a plurality of objects to be the target of a data search. For example, the information processing device 100E executes a process (also called "first stage process") to select a group (also called "target group group") to be the target of the search process from among a plurality of groups. Then, the information processing device 100E executes the following processes (7-1) to (7-10) (also called "second stage process") for the target group group selected in the first stage process. In this way, the information processing device 100E executes the first stage process and the second stage process, that is, executes a two-stage search process, thereby extracting nearby objects corresponding to the search query. Below, an overview of the first stage process and the second stage process will be described, and then an example of the process will be described using the figures.

[6-1-1. First stage processing]
First, an overview of the first stage processing will be described. In the first stage processing, the information processing device 100E selects target groups using a graph in which the representative objects of each of the multiple groups are connected by edges. For example, the information processing device 100E selects target groups using a group connection graph (blob graph) in which the centroids of each of the multiple groups are connected by edges as representative objects. Note that the centroid is merely an example, and the representative object is not limited to the centroid, and any object that represents the group can be used.

In the first stage of processing, the information processing device 100E selects a specified number (also referred to as the "specified number") of groups for a search query (also simply referred to as the "query") used in the search as a group of target groups. For example, the information processing device 100E searches the group connection graph using the search query (query) and selects a specified number of groups in the vicinity of the query as a group of target groups. Note that the search using the group connection graph is similar to the content described above, and a detailed description will be omitted. As a result, the information processing device 100E selects a specified number of groups whose representative objects are located in the vicinity of the query as a group of target groups.

Note that when the information processing device 100E acquires information indicating the target group group from an external device, etc., it may not need to execute the first stage of processing. Furthermore, when the information processing device 100E sets all of the multiple groups as the target group group, it may not need to execute the first stage of processing. For example, when the specified number matches the number of the multiple groups, the information processing device 100E may decide to set all of the multiple groups as the target group group and may not need to execute the first stage of processing. In this way, when the information processing device 100E does not execute the first stage of processing, it executes only the second stage of processing to extract nearby objects corresponding to the query.

[6-1-2. Second stage processing]
Next, an overview of the second stage processing will be described. In the second stage processing, the information processing device 100E calculates (calculates) the distance between the query and objects in multiple groups (blobs) and searches for objects in the vicinity of the query. Note that any value can be adopted as the distance between the object and the query as long as it indicates the distance between the object and the query, and may be, for example, an approximate distance or a positive distance. For example, when the information processing device 100E uses the approximate distance as the distance between the object and the query, it may calculate the distance between the object and the query by the above-mentioned direct product quantization or the like.

For example, in the second stage of processing, the information processing device 100E performs the following processes (7-1) to (7-10).

(7-1): A set of target groups is set as group set S, and search radius R is set to infinity. (7-2): Sort group set S by the distance between the representative object of each group and the query. (7-3): If group set S is an empty set, end processing. (7-4): The group with the shortest distance from group set S is set as blob B, and is obtained from group set S, and blob B is deleted from group set S. (7-5): Calculate the distance between all objects belonging to blob B and the query, and add them to search result set O (for example, a list limited to the number of search results N). (7-6): Sort search result set O by distance, and delete objects exceeding the number of search results N from search result set O. (7-7): When the number of objects in search result set O reaches the number of search results N, set the maximum distance in search result set O to search radius R. (7-8): Set the shortest distance between the object belonging to blob B and the query to blob distance D. (7-9): End processing when blob distance D exceeds search radius R′=R×e. (7-10): Return to processing (7-3).

For example, in process (7-9), the information processing device 100E calculates a search radius R' to be used as a reference value by multiplying the search radius R, which indicates the search range in the search process, by a coefficient e. The coefficient e can be set to any value. For example, the coefficient e can be set to any value greater than 0, and values such as 0.1, 1.1, etc. are set.

As described above, in the second stage processing, the information processing device 100E selects a group in order of the distance between the representative object of each of the target groups and the search query from the one with the shortest distance. Then, the information processing device 100E executes a search process in which an object belonging to the selected group is set as a target object, and a nearby object corresponding to the search query is extracted based on the distance between the search query and each of the target objects. The information processing device 100E ends the search process when a comparison result between a reference value based on a value indicating a search range in the search process and a target distance, which is a distance corresponding to the one group, satisfies a predetermined condition. In this way, the information processing device 100E does not search all of the target groups in the second stage processing, but makes it possible to end the second stage processing midway by introducing a distance. As a result, when it is assumed that the second stage processing thereafter is unnecessary, the information processing device 100E can suppress the execution of unnecessary processing by ending the second stage processing midway. Therefore, the information processing device 100E can execute a search process appropriately according to the group.

Note that the above-mentioned processes (7-1) to (7-10) are merely examples, and the information processing device 100E may execute any process. The information processing device 100E may introduce a search number M in addition to the search result number N and execute the process. In this case, the information processing device 100E calculates the search number M as N×e. For example, a value greater than 1 is used as the coefficient e. The information processing device 100E collects information on a search set P (for example, a list limited to the search number M) in the same way as the search result set O. In this case, in the process (7-5), the information processing device 100E adds objects to the search set P in the same way as the search result set O. Then, in the process (7-6), the information processing device 100E sorts the search set P by distance in the same way as the search result set O, and deletes objects that exceed the search number M from the search set P. In addition, the information processing device 100E sets the maximum distance in the search set P to the search radius R' used in the process (7-9). The information processing device 100E may execute processes (7-1) to (7-10) using a value obtained by multiplying the number of search results N by e, without introducing the search count M. For example, the coefficient e may be greater than 1. In this case, the search result set O contains a greater number of objects (N×e) than the number of search results N. Therefore, when the information processing device 100E ends the process in process (7-9), it sorts the search result set O by distance and deletes objects that exceed the number of search results N from the search result set O, thereby acquiring the number of objects that is the number of search results N.

[6-1-3. Processing example]
An example of information processing according to the sixth embodiment will be described below with reference to FIG. 44. FIG. 44 is a diagram showing an example of information processing according to the sixth embodiment. Prior to the description of information processing by the information processing device 100E, the illustrated aspect of FIG. 44 will be briefly described. In FIG. 44, the distinction between groups (blobs) is indicated by solid lines. Also, as shown in the spatial information SP71 in FIG. 44, a graph GR71, which is a group connection graph (blob graph) that connects between blobs, is indicated by dotted lines connecting between centroids C of blobs BL. In this way, when the centroids of each blob BL are not distinguished, they are described as "centroid C". Note that the spatial information SP71 and spatial information SP72 in FIG. 44 are described by assigning different symbols to the same spatial information in order to describe the processing, but they are the same spatial information, and when they are particularly distinguished, they are described as "spatial information SP70".

In Figure 44, centroids C21 to C30 indicate the centroid C of each of the blobs BL21 to BL30. For example, blob BL21 includes nodes N31, N205, etc., and the centroid C of blob BL21 is centroid C21. For example, centroid C21 is connected by edges to centroids C22, C27, C29, and C30 in graph GR71. Note that the blobs BL and nodes N, etc. shown in Figure 44 are only a partial list, and spatial information SP70 includes many more nodes N and blobs BL in addition to those shown in the figure.

Below, a processing example will be described using as an example a case where information corresponding to the spatial information SP70 shown in FIG. 44 has been acquired. In FIG. 44, the information processing device 100E executes a search process using a search query QE11. In addition, in the example shown below, a case where the number of nearby objects to be extracted is "3", that is, the number of objects to be extracted as nearby objects of the search query QE11 is three, will be described as an example.

First, the information processing device 100E executes the first stage of processing (step S81). In the first stage of processing, the information processing device 100E selects a target group group as described above. In FIG. 44, it is assumed that the specified number is set to 4. For example, the information processing device 100E uses the graph GR71 to select four blobs BL, blobs BL21, BL23, BL29, and BL30, as the target group group.

Then, the information processing device 100E executes the second stage of processing (step S82). In the second stage of processing, as described above, the information processing device 100E selects one group from the target groups in order from the one with the shortest distance, and executes processing on the objects in the one group. As shown in FIG. 44, the four blobs BL included in the target groups are closest to the search query QE11 in the order of blobs BL30, BL21, BL29, and BL23, with the centroid C being the representative object. Therefore, the information processing device 100E selects the blobs BL to be processed in the order of blobs BL30, BL21, BL29, and BL23, and executes processing. At the start of the second stage of processing, the number N of search results that are candidates for object extraction is 0, which is smaller than the number of nearby object extractions "3", so the search range (search radius R) is set to infinity (also called "infinity"), and for example, the reference value (search radius R') is also infinite.

The first range RG1 shown by the dashed-dotted circle in the spatial information SP72 of FIG. 44 corresponds to the search range (search radius R), and the second range RG2 shown by the dashed-dotted circle corresponds to the reference value (search radius R'). Note that the spatial information SP72 of FIG. 44 shows the first range RG1 and the second range RG2 when the termination condition is satisfied (one state), and the first range RG1 and the second range RG2 vary depending on the object extraction candidates. Also, the bidirectional arrow between the search query QE11 and node N in the spatial information SP72 of FIG. 44 indicates the distance between the search query QE11 and that node N.

First, the information processing device 100E performs processing on the object in blob BL30 whose centroid C is closest to the search query QE11 among blobs BL30, BL21, BL29, and BL23. For example, the information processing device 100E collectively calculates the distance between each of nodes N2, N6, N8, etc. in blob BL30 and the search query QE11. Then, the information processing device 100E extracts (updates) extraction candidates (search result set O) for objects corresponding to the search query QE11 based on the distance between each of nodes N2, N6, N8, etc. in blob BL30 and the search query QE11.

In FIG. 44, the information processing device 100E extracts nodes N6, N8, and N2 as object extraction candidates in order of the distance between each of nodes N2, N6, N8, etc. in blob BL30 and the search query QE11. In this case, since the number of search results N has reached the number of nearby object extractions "3", the information processing device 100E updates the search range (search radius R) to the distance between the search query QE11 and node N2, which is the object extraction candidate with the furthest distance from the search query QE11. Then, the information processing device 100E updates the reference value (search radius R') based on the updated search range (search radius R).

The information processing device 100E also determines the distance D1 between the search query QE11 and the node N6 that is the shortest distance from the search query QE11 among the objects in the blob BL30 as the target distance (blob distance) of the blob BL30. Then, the information processing device 100E compares the blob distance of the blob BL30 with a reference value, and ends the search process if the blob distance of the blob BL30 is greater than the reference value. At the time of processing targeting the blob BL30, the blob distance of the blob BL30 is smaller than the reference value, so the information processing device 100E determines not to end the search process and continues the search process. Note that the information processing device 100E excludes (deletes) the blob BL30 from the target group group (group set S). Also, the blob distance, such as the blob distance, may be set to any value, not limited to the distance of the object that is the shortest distance from the search query QE11 among the objects included in the blob BL.

Next, the information processing device 100E performs processing on the objects in blob BL21 whose centroid C is closest to the search query QE11 among blobs BL21, BL29, and BL23 included in the target group group after deleting blob BL30. For example, the information processing device 100E collectively calculates the distance between each of nodes N31, N205, etc. in blob BL21 and the search query QE11. Then, the information processing device 100E updates the extraction candidates (search result set O) for the object corresponding to the search query QE11 based on the distance between each of nodes N31, N205, etc. in blob BL21 and the search query QE11.

In FIG. 44, the information processing device 100E adds node N31, which is closer to the search query QE11 than node N2, to the object extraction candidate (search result set O) among nodes N6, N8, and N2 included in the object extraction candidate (search result set O), and excludes node N2 from the object extraction candidate (search result set O). Then, the information processing device 100E updates the search range (search radius R) to the distance between the search query QE11 and node N31, which is the object extraction candidate with the furthest distance from the search query QE11. Then, the information processing device 100E updates the reference value (search radius R') based on the updated search range (search radius R). In FIG. 44, the information processing device 100E updates the search range (search radius R) to a value corresponding to the distance between node N31 and the search query QE11 (corresponding to the first range RG1). Then, the information processing device 100E updates the reference value (search radius R') to a value corresponding to the second range RG2 based on the correspondence to the first range RG1.

The information processing device 100E also determines the distance D2 between the search query QE11 and node N31, which is the object in blob BL21 that has the shortest distance from the search query QE11, as the target distance (blob distance) of blob BL21. Then, the information processing device 100E compares the blob distance of blob BL21 with a reference value, and terminates the search process if the blob distance of blob BL21 is greater than the reference value. At the time of processing targeting blob BL21, the blob distance of blob BL21 is smaller than the reference value, so the information processing device 100E determines not to terminate the search process and continues the search process. Note that the information processing device 100E excludes (deletes) blob BL21 from the target group group (group set S).

Next, the information processing device 100E performs processing on the objects in blob BL29, which has the centroid C closest to the search query QE11, among blobs BL29 and BL23 included in the target group group after deleting blob BL21. For example, the information processing device 100E collectively calculates the distance between each of nodes N3, N11, N114, etc. in blob BL29 and the search query QE11. Then, the information processing device 100E updates the extraction candidates (search result set O) for the object corresponding to the search query QE11 based on the distance between each of nodes N3, N11, N114, etc. in blob BL29 and the search query QE11.

In FIG. 44, the information processing device 100E does not update the extraction candidates (search result set O) of the object corresponding to the search query QE11 because there is no object in the blob BL29 whose distance to the search query QE11 is shorter than that of the nodes N6, N8, and N31 included in the extraction candidates (search result set O) of the object. Furthermore, because there is no update of the extraction candidates (search result set O) of the object, the information processing device 100E does not update the search range (search radius R) and the reference value (search radius R').

The information processing device 100E also determines the distance D3 between the search query QE11 and node N11, which has the shortest distance from the search query QE11 among the objects in blob BL29, as the target distance (blob distance) of blob BL29. The information processing device 100E then compares the blob distance of blob BL29 with a reference value, and terminates the search process if the blob distance of blob BL29 is greater than the reference value. At the time of processing targeting blob BL29, the blob distance of blob BL29 is greater than the reference value, so the information processing device 100E determines to terminate the search process and terminates the search process.

Then, the information processing device 100E determines the objects included in the object extraction candidates (search result set O) at the end of the second stage processing as nearby objects of the search query QE11 (step S83). In FIG. 44, the information processing device 100E determines the nodes N6, N8, and N31 (objects corresponding to them) included in the object extraction candidates (search result set O) at the time of processing targeting blob BL29 as nearby objects of the search query QE11.

In this way, in the example of FIG. 44, the information processing device 100E ends the search process without processing the objects in blob BL23 out of blobs BL30, BL21, BL29, and BL23 selected as the target group. This allows the information processing device 100E to provide appropriate search results while reducing processing time and processing load. Therefore, the information processing device 100E can execute search processing appropriately according to the group.

6-2. Configuration of information processing device
Next, the configuration of an information processing device 100E according to the sixth embodiment will be described with reference to FIG. 45. FIG. 45 is a diagram showing a configuration example of an information processing device according to the sixth embodiment. As shown in FIG. 45, the information processing device 100E has a communication unit 110, a storage unit 120B, and a control unit 130E. Note that in the information processing device 100E, the description of the same points as those of the information processing device 100, the information processing device 100A, the information processing device 100B, the information processing device 100C, or the information processing device 100D will be omitted as appropriate.

(Memory unit 120B)
The storage unit 120B is realized by, for example, a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 45, the storage unit 120B according to the sixth embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123, a codebook information storage unit 124, a blob information storage unit 125, and a blob connection graph information storage unit 126.

The storage unit 120B according to the sixth embodiment stores various information used in processing, including but not limited to the above. For example, the storage unit 120B according to the sixth embodiment stores various information used in processing, such as a search range, a predetermined coefficient, a reference value, and an end determination.

(Control unit 130E)
The control unit 130E is a controller, and is realized, for example, by a CPU, an MPU, a GPU, etc., executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100E using a RAM as a working area. The control unit 130E is also a controller, and is realized, for example, by an integrated circuit such as an ASIC or an FPGA.

As shown in FIG. 45, the control unit 130E has an acquisition unit 131, a generation unit 132E, a search processing unit 133E, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130E is not limited to the configuration shown in FIG. 45, and may be other configurations as long as they perform the information processing described below.

The acquisition unit 131 according to the sixth embodiment acquires object information indicating a plurality of objects to be the target of a data search. The acquisition unit 131 acquires index information indicating an index for searching a plurality of objects.

The acquisition unit 131 according to the sixth embodiment acquires various information in the same manner as the acquisition unit 131 according to the first to fifth embodiments. For example, the acquisition unit 131 acquires object information indicating a plurality of objects to be the target of a data search. For example, the acquisition unit 131 acquires index information indicating an index for searching a plurality of objects.

The acquisition unit 131 acquires a number of groups that classify a number of objects that are the targets of a data search. The acquisition unit 131 acquires a search query for the multiple objects. The acquisition unit 131 acquires a graph in which representative objects of the multiple groups are connected by edges. The acquisition unit 131 acquires a number of groups that indicate targets for batch processing in the search process.

(Generation unit 132E)
The generating unit 132E generates various types of information in the same manner as the generating unit 132, the generating unit 132A, the generating unit 132B, or the generating unit 132C.

For example, the generation unit 132E may generate group information indicating multiple groups into which multiple objects are classified, based on the object information acquired by the acquisition unit 131. The generation unit 132E generates group information indicating multiple groups used for performing batch processing in a search process targeting multiple objects. The generation unit 132E generates group information indicating multiple groups used for performing batch calculation of distances related to multiple objects. The generation unit 132E generates group information indicating multiple groups used for performing parallel processing of calculation of distances between a search query used in the search process and an object.

For example, the generation unit 132E generates group information indicating multiple groups used to perform processing related to quantization of multiple objects. The generation unit 132E generates group information indicating multiple groups that are units of quantization. The generation unit 132E generates group information indicating multiple groups used to quantize vectors corresponding to each of multiple objects. Note that when the information processing device 100E acquires group information from an external device or the like, it does not need to have the generation unit 132E.

(Search processing unit 133E)
The search processing unit 133E executes search processing including the above-mentioned first stage processing and the second stage processing shown in steps (7-1) to (7-10). For example, the search processing unit 133E performs various processes related to search processing in the same manner as the search processing unit 133, the search processing unit 133A, the search processing unit 133B, the search processing unit 133C, or the search processing unit 133D. The search processing unit 133E performs processing using information stored in the storage unit 120B. The search processing unit 133E performs processing using information generated by the generation unit 132E.

For example, the search processing unit 133E selects one of the target groups selected from multiple groups in order of the distance between the representative object of each of the target groups and the search query. The search processing unit 133E executes a search process in which, with an object belonging to the selected group as the target object, the nearby object corresponding to the search query is extracted based on the distance between the search query and each of the target objects. If the comparison result between a reference value based on a value indicating the search range in the search process and the target distance, which is the distance corresponding to one of the groups, satisfies a predetermined condition, the search processing unit 133E ends the search process.

The search processing unit 133E selects a predetermined number of groups from among the multiple groups as the target group. The search processing unit 133E selects, from among the multiple groups, groups whose representative objects are in the vicinity of the search query as the target group. The search processing unit 133E selects, from among the multiple groups, groups whose representative objects, which are centroids of each of the multiple groups, are in the vicinity of the search query as the target group.

The search processing unit 133E selects a target group using the graph. If the target distance is greater than a reference value, the search processing unit 133E ends the search process. The search processing unit 133E determines the target distance based on an object that belongs to one group. The search processing unit 133E determines the distance of an object that is the smallest distance from the search query among the objects that belong to one group as the target distance.

The search processing unit 133E calculates a reference value by multiplying the search range by a predetermined coefficient. The search processing unit 133E calculates a reference value by multiplying the search range by a predetermined coefficient greater than 0. The search processing unit 133E updates the search range based on extraction candidates of nearby objects during the search process. The search processing unit 133E updates the search range, which is set to infinity as the initial value. The search processing unit 133E updates the search range to the extraction candidate that is the farthest from the search query.

The search processing unit 133E performs batch processing on the objects belonging to one group during search processing. The search processing unit 133E performs batch calculation of distances on the objects belonging to one group. The search processing unit 133E performs parallel processing to calculate the distance between each of the objects belonging to one group and the search query.

6-3. Information processing flow
Next, a procedure of information processing according to the sixth embodiment will be described with reference to Fig. 46. Fig. 46 is a flowchart showing an example of information processing according to the sixth embodiment.

First, FIG. 46 will be described. For example, FIG. 46 is a flowchart showing an example of a group generation process. As shown in FIG. 46, the information processing device 100E acquires a plurality of groups into which a plurality of objects to be the subject of a data search are classified, and a search query for the plurality of objects (step S1001). For example, the information processing device 100E acquires group information indicating a plurality of groups into which a plurality of objects are classified, from the blob information storage unit 125.

The information processing device 100E selects one of the target groups selected from a plurality of groups in order of the distance between the representative object of each of the target groups and the search query, and executes a search process in which, with the objects belonging to the selected group as target objects, nearby objects corresponding to the search query are extracted based on the distance between the search query and each of the target objects. If a comparison result between a reference value based on a value indicating a search range in the search process and a target distance, which is a distance corresponding to the one group, satisfies a predetermined condition, the search process is terminated (step S1002). For example, the information processing device 100E executes a search process including the first stage process described above and the second stage process shown in processes (7-1) to (7-10).

7. Seventh embodiment
In the sixth embodiment described above, an example of the search process in the case where the first group (blob) and the second group (cluster) are the same is shown, but the search process may be performed in the same manner even if the first group (blob) and the second group (cluster) are not the same. For example, the information processing device 100F according to the seventh embodiment performs the search process on objects in which the objects in each first group (blob) are classified into one or more second groups (clusters). That is, the information processing device 100F according to the seventh embodiment performs the search process on objects in which hierarchical clustering (hierarchical clustering) has been performed, in which the second group (cluster) is further classified into the first group (blob).

This point will be described below as the seventh embodiment. In the seventh embodiment, the information processing system 1 has information processing device 100F instead of information processing device 100, information processing device 100A, information processing device 100B, information processing device 100C, information processing device 100D, or information processing device 100E. Note that the description of the same points as those described above in the first embodiment, second embodiment, third embodiment, fourth embodiment, fifth embodiment, sixth embodiment, etc. will be omitted as appropriate.

[7-1. Information Processing]
An example of information processing such as a search process executed by the information processing device 100F will be described below. The search process executed by the information processing device 100F is the same as that of the information processing device 100E except that the object in the first group (blob) is processed based on the classification of the second group (cluster), and the description of the same points as those of the information processing device 100E will be omitted as appropriate. For example, in the seventh embodiment, in the points similar to those of the sixth embodiment, the group in the sixth embodiment may be read as the first group, the representative object may be read as the first representative object, and the target distance may be read as the first target distance.

The information processing device 100F executes a search process to extract nearby objects corresponding to a search query, using group information indicating a plurality of first groups (blobs) into which a plurality of objects to be the subject of a data search are classified, and one or more second groups (clusters) into which each of the plurality of first groups is classified into a group of objects belonging to each of the plurality of first groups. For example, the information processing device 100F executes a process (also called "first stage processing") to select one first group from the first groups (also called "target first group groups") selected from a plurality of first groups in order of the distance between the search query and each representative object (also called "first representative object") of the target first group groups.

Then, the information processing device 100F executes the following processes (8-1) to (8-15) (also referred to as "second stage processing") on the target first groups selected in the first stage processing. In this way, the information processing device 100F executes the first stage processing and the second stage processing, i.e., executes a two-stage search process, to extract nearby objects that correspond to the search query.

For example, in the second stage processing, the information processing device 100F selects one of the second groups belonging to the selected one of the first groups in order of the distance between the representative object (also called the "second representative object") of each second group and the search query from the second group having the shortest distance, and executes a calculation process to calculate the distance between the search query and an object belonging to the selected one of the second groups as a target object. The information processing device 100F executes a search process to extract nearby objects corresponding to the search query based on the distance between each of the target objects and the search query calculated by the calculation process. Below, an overview of the first stage processing and the second stage processing will be described, and then an example of the processing will be described using figures.

[7-1-1. First stage processing]
First, an overview of the first stage processing will be described. The information processing device 100F executes the first stage processing by the same processing as the information processing device 100E. For example, the information processing device 100F selects the target first group group using a graph in which the first representative objects of each of the multiple first groups are connected by edges. For example, the information processing device 100F selects the target first group group using a group connection graph (blob graph) in which the centroids of each of the multiple first groups are connected by edges as the first representative objects. Note that the first stage processing is the same as that of the sixth embodiment, and therefore a detailed description of the first stage processing will be omitted.

[7-1-2. Second stage processing]
Next, an overview of the second stage processing will be described. In the second stage processing, the information processing device 100F calculates (calculates) the distance between the query and an object in each second group (cluster) included in a plurality of first groups (blobs), and searches for an object in the vicinity of the query. Note that, as for the distance between the object and the query, any value can be adopted as long as it indicates the distance between the object and the query, as in the sixth embodiment.

For example, in the second stage of processing, the information processing device 100F performs the following processes (8-1) to (8-15).

(8-1): Set the set of the first target groups to group set S, and set the search radius R to infinity. (8-2): Sort group set S by the distance between the representative object of each group and the query. (8-3): If group set S is an empty set, end the process. (8-4): Obtain the group with the shortest distance from group set S as blob B from group set S, and delete blob B from group set S. (8-5): Calculate the distance between the centroid of multiple clusters contained in blob B and the query, and set the set sorted in order of shortest distance to cluster set CS. (8-6): Set blob distance D to infinity. (8-7): If cluster set CS is empty, return to process (8-3). (8-8): Obtain the cluster with the shortest distance from cluster set CS as cluster A from cluster set CS. and delete cluster A from cluster set CS (8-9): calculate the distance between all objects in cluster A and the query, and add them to search result set O (8-10): sort search result set O by distance, and delete objects exceeding the number of search results N from search result set O (8-11): when the number of objects in search result set O reaches the number of search results N, set the maximum distance in search result set O to search radius R (8-12): if the shortest distance Dc of the approximation distances of objects in cluster A is smaller than the blob distance D, update the blob distance D to the shortest distance Dc (8-13): if the blob distance D exceeds the search radius R' = R x e, end processing (8-14): if the shortest distance Dc is larger than the search radius R' = R x e, return to processing (8-3) (8-15): return to processing (8-7)

For example, the search radius R' used as the reference value in processes (8-13) and (8-14) is the same as the search radius R' in process (7-9), so a detailed explanation is omitted, but for example, the coefficient e can be set to any value greater than 0, such as 0.2, 1.2, etc.

As described above, in the second stage of processing, the information processing device 100F selects one first group in order of the shortest distance between each representative object of the target first groups and the search query. Then, from among the second groups belonging to the selected one first group, the information processing device 100F selects one second group in order of the shortest distance between the second representative object and the search query, and executes a calculation process to calculate the distance between the search query and an object belonging to the selected one second group as a target object.

Then, the information processing device 100F executes a search process to extract nearby objects corresponding to the search query based on the distances between the target object and the search query calculated by the calculation process. The information processing device 100F ends the search process when a comparison result between a reference value based on a value indicating the search range in the search process and a first target distance which is a distance corresponding to one first group satisfies a predetermined condition. Furthermore, the information processing device 100F ends the process targeting the first group to which the one second group belongs when a comparison result between a reference value based on a value indicating the search range in the search process and a second target distance which is a distance corresponding to one second group satisfies a predetermined condition.

In this way, the information processing device 100F does not search all of the target first groups in the second stage of processing, but rather makes it possible to end the second stage of processing midway by introducing distance. As a result, when it is assumed that further second stage processing is unnecessary, the information processing device 100F can prevent unnecessary processing by ending the second stage of processing midway.

For example, in a conventional two-stage search process, the distances of all objects in all quantized clusters of all groups obtained are calculated in the second stage. When calculating the distances of all objects as in the conventional two-stage search process, there is a problem that the distances are calculated for objects for which distance calculation is not necessary at the end of the search process, which increases the processing time. On the other hand, the information processing device 100F does not search for all second groups in the first group that is the target of the second stage processing, but instead introduces distances to make it possible to end the processing targeting the first group midway. As a result, when the information processing device 100F is processing a certain first group, if it is assumed that subsequent processing targeting the first group is unnecessary, it is possible to suppress unnecessary processing by ending the processing targeting the first group midway. Therefore, the information processing device 100F can execute the search processing appropriately according to the group.

Note that the above-mentioned processes (8-1) to (8-15) are merely examples, and the information processing device 100F may execute any process. The information processing device 100F may introduce a search number M in addition to the search result number N and execute the process. In this case, the information processing device 100F calculates the search number M as N×e. For example, the coefficient e is a value greater than 1. The information processing device 100F collects information on the search set P (for example, a list limited to the search number M) in the same way as the search result set O. In this case, in the process (8-9), the information processing device 100F adds objects to the search set P in the same way as the search result set O. Then, in the process (8-10), the information processing device 100F sorts the search set P by distance in the same way as the search result set O, and deletes objects exceeding the search number M from the search set P. In addition, the information processing device 100F sets the maximum distance in the search set P to the search radius R' used in the process (8-13) and the process (8-14). The information processing device 100F may execute processes (8-1) to (8-15) using a value obtained by multiplying the number of search results N by e, without introducing the search count M. For example, the coefficient e may be greater than 1. In this case, the search result set O contains a greater number of objects (N×e) than the number of search results N. Therefore, when the information processing device 100F finishes processing in process (8-13), it sorts the search result set O by distance and deletes objects that exceed the number of search results N from the search result set O, thereby acquiring the number of objects that is the number of search results N.

[7-1-3. Processing example]
First, an overview of the information processing according to the seventh embodiment will be described with reference to FIG. 47. FIG. 47 is a diagram showing an example of the information processing according to the seventh embodiment. Prior to the description of the information processing by the information processing device 100F, the illustrated aspect of FIG. 47 will be briefly described. In FIG. 47, the distinction between the first groups (blobs) and the distinction between the second groups (clusters) in each first group are shown with solid lines. Note that in FIG. 47, the illustration of the group connection graph (blob graph) connecting the blobs corresponding to the first stage processing is omitted. In addition, in FIG. 47, six blobs BL are shown, but since the processing is described mainly with reference to blob BL33, the illustration of the division of clusters in five blobs BL, ie, blobs BL31, BL32, BL34 to BL36 other than blob BL33, is omitted.

In FIG. 47, blob BL33 includes ten clusters CL31 to CL40. That is, the objects in blob BL33, which is the first group, are classified into one of the ten second groups, clusters CL31 to CL40. In FIG. 47, centroids CN31 to CN40 indicate the centroids of each of the clusters CL31 to CL40. When describing the centroids of each cluster CL without distinguishing between them, they are referred to as "centroid CN." Note that the blobs BL, clusters CL, and nodes N shown in FIG. 47 are only a partial list, and the spatial information SP81 includes many more blobs BL, clusters CL, and nodes N in addition to those shown in the figure.

Below, a processing example will be described using as an example a case where information corresponding to spatial information SP81 shown in FIG. 47 has been acquired. In FIG. 47, the information processing device 100F executes search processing using search query QE21. In addition, in the example shown below, a case where the number of nearby objects to be extracted is "3", that is, the number of objects to be extracted as nearby objects of search query QE21 is three, will be described as an example. Note that explanations of points similar to those explained in FIG. 44 will be omitted as appropriate.

First, the information processing device 100F executes the first stage of processing. In the first stage of processing, the information processing device 100F selects the target first group group as described above. In FIG. 47, it is assumed that the specified number is set to 6. For example, the information processing device 100F uses the group connection graph to select six blobs BL, blobs BL31 to BL36, as the target first group group.

Then, the information processing device 100F executes the second stage of processing. In the second stage of processing, as described above, the information processing device 100F selects one first group in order from the one with the shortest distance from the target first group. In FIG. 47, the six blobs BL included in the target first group are blobs BL33, BL31, BL36, BL32, BL34, and BL35 in order of distance from the search query QE21 to the centroid C, which is the first representative object.

Therefore, the information processing device 100F selects the blobs BL to be processed in the order of blobs BL33, BL31, BL36, BL32, BL34, and BL35, and executes the process. At the start of the second stage of processing, the number of search results N that are candidates for object extraction is 0, which is smaller than the number of nearby object extractions "3", so the search range (search radius R) is set to infinity, and for example, the reference value (search radius R') is also infinity.

The first range RG11 shown by the dashed-dotted circle in the spatial information SP81 in FIG. 47 corresponds to the search range (search radius R), and the second range RG12 shown by the dashed-dotted circle corresponds to the reference value (search radius R'). Note that the spatial information SP81 in FIG. 47 shows the first range RG11 and the second range RG12 when the end condition is satisfied (one state), and the first range RG11 and the second range RG12 vary depending on the object extraction candidate. Also, the bidirectional arrow between the first range RG11 and the search query QE21 in the spatial information SP81 in FIG. 47 indicates the search radius R, and the bidirectional arrow between the second range RG12 and the search query QE21 indicates the search radius R'. Also, the bidirectional arrow between the search query QE21 and the node N in the spatial information SP81 in FIG. 47 indicates the distance between the search query QE21 and the node N.

First, the information processing device 100F selects blob BL33, which has a centroid C closest to the search query QE21, as the target blob among blobs BL33, BL31, BL36, BL32, BL34, and BL35, and performs processing on clusters within blob BL33. When starting processing on blob BL33, which is the selected target blob, the information processing device 100F sets the first target distance (blob distance) of blob BL33 to infinity. Note that the information processing device 100F excludes (deletes) blob BL33 from the target first group set (group set S).

As described above, the information processing device 100F selects one second group in order from the group with the shortest distance from the target blob. In FIG. 47, the ten clusters CL in blob BL33, which is the target blob, are clusters CL39, CL38, CL40, etc., in that order, with the centroid CN, which is the second representative object, being closest to the search query QE21. The information processing device 100F performs the following process on the ten clusters CL in blob BL33 as a group of clusters to be processed.

First, the information processing device 100F performs processing on objects in cluster CL39, which is the cluster of 10 clusters CL in blob BL33 whose centroid CN is closest to the search query QE21. For example, the information processing device 100F collectively calculates the distance between each of nodes N2, N5, N8, N27, N77, etc. in cluster CL39 and the search query QE21. Then, the information processing device 100F extracts (updates) extraction candidates (search result set O) for objects corresponding to the search query QE21 based on the distance between each of nodes N2, N5, N8, N27, N77, etc. in cluster CL39 and the search query QE21.

In FIG. 47, the information processing device 100F extracts nodes N8, N27, and N2 as object extraction candidates in order of the distance between each of the nodes N2, N5, N8, N27, and N77 in the cluster CL39 and the search query QE21 in ascending order of distance. In this case, since the number of search results N has reached the number of nearby object extractions "3", the information processing device 100F updates the search range (search radius R) to the distance between the search query QE21 and node N2, which is the object extraction candidate with the furthest distance from the search query QE21. Then, the information processing device 100F updates the reference value (search radius R') based on the updated search range (search radius R). In FIG. 47, the information processing device 100F updates the search range (search radius R) to a value corresponding to the distance between the node N2 and the search query QE21 (corresponding to the first range RG11). Then, the information processing device 100F updates the reference value (search radius R') to a value corresponding to the second range RG12 based on the search range (search radius R) corresponding to the first range RG11.

The information processing device 100F also determines the distance D11 between the search query QE21 and node N8, which is the object in cluster CL39 that has the shortest distance from the search query QE21, as the second object distance (shortest distance) of cluster CL39. If the second object distance of cluster CL39 is smaller than the first object distance of blob BL33, the information processing device 100F updates the value of the first object distance (blob distance) of blob BL33 to the value of the second object distance of cluster CL39. In FIG. 47, the first object distance of blob BL33 at that time is infinite, and distance D11, which is the second object distance of cluster CL39, is smaller, so the first object distance (blob distance) of blob BL33 is updated to distance D11, which is the second object distance of cluster CL39.

Then, the information processing device 100F compares the blob distance of blob BL33 with the reference value, and ends the search process if the blob distance of blob BL33 is greater than the reference value. At the time of processing targeting blob BL33, the blob distance of blob BL33 is less than the reference value, so the information processing device 100F determines not to end the search process and continues the search process.

Then, the information processing device 100F compares the second object distance of the cluster CL39 with a reference value, and if the second object distance of the cluster CL39 is greater than the reference value, ends the processing for the blob BL33. At the time of the processing for the cluster CL39, the second object distance of the cluster CL39 is smaller than the reference value, so the information processing device 100F determines not to end the processing for the blob BL33, and continues the processing for the blob BL33. Note that the information processing device 100F excludes (deletes) the cluster CL39 from the processing target cluster group (cluster set CS). In addition, the second object distance (shortest distance) of the cluster CL may be set to any value, not limited to the distance of the object that is the shortest distance from the search query QE21 among the objects included in the cluster CL.

Next, the information processing device 100F performs processing on the objects in the cluster whose centroid CL is closest to the search query QE21 among the clusters CL38, CL40, etc. included in the group of clusters to be processed after the deletion of cluster CL39. For example, the information processing device 100F collectively calculates the distance between each of the nodes N96, N119, N418, N615, etc. in cluster CL38 and the search query QE21. Then, the information processing device 100F updates the extraction candidates (search result set O) for the object corresponding to the search query QE21 based on the distance between each of the nodes N96, N119, N418, N615, etc. in cluster CL38 and the search query QE21.

In FIG. 47, the information processing device 100F does not update the extraction candidates (search result set O) of the object corresponding to the search query QE21 because there is no object in cluster CL38 whose distance to the search query QE21 is shorter than that of nodes N8, N27, and N2. Furthermore, because there is no update to the extraction candidates (search result set O) of the object, the information processing device 100F does not update the search range (search radius R) and the reference value (search radius R').

Furthermore, the information processing device 100F determines the distance DC1 between the search query QE21 and node N418, which has the shortest distance from the search query QE21 among the objects in cluster CL38, as the second object distance (shortest distance) of cluster CL38. Then, if the second object distance of cluster CL38 is smaller than the first object distance of blob BL33, the information processing device 100F updates the value of the first object distance (blob distance) of blob BL33 to the value of the second object distance of cluster CL38. In FIG. 47, the first object distance of blob BL33 at that time is distance D11 infinity, and distance DC1, which is the second object distance of cluster CL38, is larger, so the first object distance (blob distance) of blob BL33 is not updated.

Then, the information processing device 100F compares the blob distance of blob BL33 with the reference value, and ends the search process if the blob distance of blob BL33 is greater than the reference value. At the time of processing targeting blob BL33, the blob distance of blob BL33 is less than the reference value, so the information processing device 100F determines not to end the search process and continues the search process.

In this way, in the example of FIG. 47, in processing blob BL33, the information processing device 100F ends the search processing without processing objects in eight clusters CL other than clusters CL39 and CL38 out of the ten clusters CL in blob BL33. This allows the information processing device 100F to provide appropriate search results while reducing processing time and processing load. Therefore, the information processing device 100F can execute search processing appropriately according to the group.

Then, the information processing device 100F compares the second object distance of the cluster CL38 with a reference value, and if the second object distance of the cluster CL38 is greater than the reference value, ends the processing targeting the blob BL33. Because the second object distance of the cluster CL38 is greater than the reference value at the time of the processing targeting the cluster CL38, the information processing device 100F determines to end the processing search processing targeting the blob BL33, and continues the processing targeting the blob BL33.

In this case, the information processing device 100F continues processing on blob BL31, which has the centroid C closest to the search query QE21, among blobs BL31, BL36, BL32, BL34, and BL35 included in the first target group after deleting blob BL33. Then, when the blob distance of the blob BL being processed becomes greater than the reference value, the information processing device 100F determines to end the search processing and ends the search processing. For example, when the blob distance of blob BL31 becomes greater than the reference value, the information processing device 100F determines to end the search processing and ends the search processing.

Then, the information processing device 100F determines the objects included in the object extraction candidates (search result set O) at the end of the second stage processing as nearby objects of the search query QE21. Note that in FIG. 47, if the nodes included in the object extraction candidates (search result set O) at the end of the processing are nodes N8 and N27, the information processing device 100F determines nodes N8 and N27 (the objects corresponding to them) as nearby objects of the search query QE21.

7-2. Configuration of information processing device
Next, the configuration of an information processing device 100F according to the seventh embodiment will be described with reference to FIG. 48. FIG. 48 is a diagram showing an example of the configuration of an information processing device according to the seventh embodiment. As shown in FIG. 48, the information processing device 100F has a communication unit 110, a storage unit 120C, and a control unit 130F. Note that in the information processing device 100F, the description of the same points as those of the information processing device 100, the information processing device 100A, the information processing device 100B, the information processing device 100C, the information processing device 100D, or the information processing device 100E will be omitted as appropriate.

(Memory unit 120C)
The storage unit 120C is realized by, for example, a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk. As shown in Fig. 48, the storage unit 120C according to the seventh embodiment has an object information storage unit 121, a graph information storage unit 122, a quantization information storage unit 123, a codebook information storage unit 124, a blob information storage unit 125, a blob connection graph information storage unit 126, and a cluster information storage unit 127.

The storage unit 120C according to the seventh embodiment stores various information used in processing, including but not limited to the above. For example, the storage unit 120C according to the seventh embodiment stores various information used in processing, such as a search range, a predetermined coefficient, a reference value, and an end determination.

(Control unit 130F)
The control unit 130F is a controller, and is realized, for example, by a CPU, an MPU, a GPU, etc., executing various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing device 100F using a RAM as a working area. The control unit 130F is also a controller, and is realized, for example, by an integrated circuit such as an ASIC or an FPGA.

As shown in FIG. 48, the control unit 130F has an acquisition unit 131, a generation unit 132F, a search processing unit 133F, and a provision unit 134, and realizes or executes the functions and actions of the information processing described below. Note that the internal configuration of the control unit 130F is not limited to the configuration shown in FIG. 48, and may be other configurations as long as they perform the information processing described below.

The acquisition unit 131 according to the seventh embodiment acquires object information indicating multiple objects to be the target of a data search. The acquisition unit 131 acquires index information indicating an index for searching multiple objects.

The acquisition unit 131 according to the seventh embodiment acquires various information in the same manner as the acquisition unit 131 according to the first to sixth embodiments. For example, the acquisition unit 131 acquires object information indicating a plurality of objects to be the target of a data search. For example, the acquisition unit 131 acquires index information indicating an index for searching a plurality of objects.

The acquisition unit 131 acquires group information indicating a plurality of first groups into which a plurality of objects to be the subject of a data search are classified, and one or more second groups into which objects belonging to each of the plurality of first groups are classified. The acquisition unit 131 acquires a search query for the plurality of objects. The acquisition unit 131 acquires a graph in which the first representative objects of each of the plurality of first groups are connected by edges.

(Generation unit 132F)
The generating unit 132F generates various types of information in the same manner as the generating unit 132, the generating unit 132A, the generating unit 132B, the generating unit 132C, or the generating unit 132E.

For example, the generating unit 132F may generate a plurality of first groups, which are a first number of groups into which a plurality of objects are classified, based on the object information acquired by the acquiring unit 131. The generating unit 132F may generate one or more second groups into which objects belonging to each of the plurality of first groups are classified.

The generating unit 132F generates first group information that is a group in which objects belonging to the same second group in the multiple second groups are classified into the same first group. The generating unit 132F generates first group information indicating multiple first groups in which a group of objects belonging to each of two or more second groups out of the multiple second groups is classified into one first group.

The generation unit 132F generates a second group used for performing batch processing in a search process targeting multiple objects. The generation unit 132F generates a second group used for performing batch calculation of distances for multiple objects. The generation unit 132F generates a second group used for performing parallel processing of calculation of distances between a search query used in the search process and an object.

The generation unit 132F generates a second group used to perform processing related to quantization of multiple objects. The generation unit 132F generates a second group that serves as a unit of quantization. The generation unit 132F generates a second group used to quantize vectors corresponding to each of the multiple objects.

The generation unit 132F classifies the multiple first groups after classifying the multiple second groups. The generation unit 132F generates the multiple second groups by clustering the multiple objects. The generation unit 132F uses the index information to generate second group information indicating the multiple second groups. The generation unit 132F uses the second group information indicating the second groups to generate first group information indicating the multiple first groups.

The generation unit 132F generates first group information indicating a plurality of first groups by clustering a plurality of second groups. After classifying the plurality of first groups, the generation unit 132F classifies the plurality of second groups. The generation unit 132F generates first group information indicating a plurality of first groups by clustering a plurality of objects.

The generation unit 132F generates second group information indicating a plurality of second groups using first group information indicating the first group. The generation unit 132F divides at least one of the plurality of first groups to generate two or more second groups. The generation unit 132F generates a plurality of second groups by clustering objects belonging to each first group and dividing each first group into two or more second groups. Note that when the information processing device 100F acquires group information from an external device or the like, it does not need to have the generation unit 132F.

(Search processing unit 133F)
The search processing unit 133F executes search processing including the above-mentioned first stage processing and the second stage processing shown in steps (8-1) to (8-13). For example, the search processing unit 133F performs various processes related to the search processing in the same manner as the search processing unit 133, the search processing unit 133A, the search processing unit 133B, the search processing unit 133C, or the search processing unit 133D. The search processing unit 133F performs processing using information stored in the storage unit 120C. The search processing unit 133F performs processing using information generated by the generation unit 132F.

For example, the search processing unit 133F selects one first group from a target first group group selected from a plurality of first groups in order of the shortest distance between the first representative object of each of the target first groups and the search query. The search processing unit 133F selects one second group from the second groups belonging to the selected one first group in order of the shortest distance between the second representative object and the search query. The search processing unit 133F executes a calculation process to calculate the distance between the search query and an object belonging to the selected one second group as a target object. The search processing unit 133F executes a search process to extract nearby objects corresponding to the search query based on the distances between the target objects and the search query calculated by the calculation process.

The search processing unit 133F selects a predetermined number of first groups from among the multiple first groups as the target first group group. The search processing unit 133F selects, from among the multiple first groups, first groups whose representative objects are in the vicinity of the search query as the target first group group. The search processing unit 133F selects, from among the multiple first groups, first groups whose first representative objects, which are centroids of each of the multiple first groups, are in the vicinity of the search query as the target first group group. The search processing unit 133F selects the target first group group using a graph.

The search processing unit 133F ends the search process when a comparison result between a reference value based on a value indicating a search range in the search process and a first target distance, which is a distance corresponding to one first group, satisfies a predetermined condition. The search processing unit 133F ends the search process when the first target distance is greater than the reference value.

The search processing unit 133F determines a second object distance, which is a distance corresponding to the one second group, based on the objects belonging to the one second group, and updates the first object distance to the second object distance if the second object distance is smaller than the first object distance. The search processing unit 133F determines the distance of an object that has the smallest distance from the search query, among the objects belonging to the one second group, to be the second object distance. If the second object distance is larger than a reference value, the search processing unit 133F ends the calculation process for the one second group, and selects another second group belonging to the one first group as the one second group.

The search processing unit 133F calculates a reference value by multiplying the search range by a predetermined coefficient. The search processing unit 133F calculates a reference value by multiplying the search range by a predetermined coefficient greater than 0. The search processing unit 133F updates the search range based on extraction candidates of nearby objects during the search process. The search processing unit 133F updates the search range, which is set to infinity as the initial value. The search processing unit 133F updates the search range to the extraction candidate that is the farthest from the search query.

The search processing unit 133F selects one second group in order of the shortest distance between the search query and a second representative object that is the centroid of each of the one or more second groups. The search processing unit 133F executes a calculation process that collectively calculates the distance for objects that belong to one second group. The search processing unit 133F executes a calculation process that is a parallel process that calculates the distance between each of the objects that belong to one second group and the search query.

[7-3. Information processing flow]
Next, a procedure of information processing according to the seventh embodiment will be described with reference to Fig. 49. Fig. 49 is a flowchart showing an example of information processing according to the seventh embodiment.

First, FIG. 49 will be described. For example, FIG. 49 is a flowchart showing an example of a group generation process. As shown in FIG. 49, the information processing device 100F acquires group information indicating a plurality of first groups into which a plurality of objects to be the subject of a data search are classified, and one or more second groups into which each object group belonging to each of the plurality of first groups is classified, and a search query for the plurality of objects (step S1101). For example, the information processing device 100F acquires from the blob information storage unit 125 first group information indicating a plurality of first groups into which a plurality of objects are classified, and acquires from the cluster information storage unit 127 second group information indicating one or more second groups into which each object group belonging to each of the plurality of first groups is classified.

The information processing device 100F selects one first group from among the target first groups selected from the multiple first groups, in order of the distance between the first representative object of each of the target first groups and the search query, selects one second group from among the second groups belonging to the selected one first group, in order of the distance between the second representative object and the search query, performs a calculation process to calculate the distance between the object belonging to the selected one second group as a target object and the search query, and performs a search process to extract nearby objects corresponding to the search query based on the distances between the target objects and the search query calculated by the calculation process (step S1102). For example, the information processing device 100E performs a search process including the first stage process described above and the second stage processes shown in processes (8-1) to (8-13).

8. Effects
As described above, the information processing device 100F according to the seventh embodiment includes an acquisition unit 131 and a search processing unit 133F. The acquisition unit 131 acquires group information indicating a plurality of first groups into which a plurality of objects to be subjected to data search are classified, and one or more second groups into which each of the plurality of first groups is classified for each of the object groups, and a search query for the plurality of objects. The search processing unit 133F selects one first group from the target first group group selected from the plurality of first groups in order of the distance between the first representative object of each of the target first group groups and the search query, selects one second group from the second groups belonging to the selected one first group in order of the distance between the second representative object and the search query, performs a calculation process to calculate the distance between the object belonging to the selected one second group as a target object and the search query, and performs a search process to extract a nearby object corresponding to the search query based on the distance between each of the target objects and the search query calculated by the calculation process.

In this way, the information processing device 100F according to the seventh embodiment can execute search processing according to grouping by executing search processing using information of the first group and the second group that are in a hierarchical relationship, and therefore can execute search processing appropriately according to the group.

The search processing unit 133F selects a predetermined number of first groups from the multiple first groups as a target first group group.

In this way, the information processing device 100F can select a predetermined number of first groups from among a plurality of first groups as a target first group group, thereby performing a search process appropriately according to the group.

The search processing unit 133F selects, from among the multiple first groups, first groups whose representative objects are in the vicinity of the search query as the target first groups.

In this way, the information processing device 100F can appropriately perform search processing according to the group by selecting, from among a plurality of first groups, first groups whose representative objects are in the vicinity of the search query as target first groups.

The search processing unit 133F selects, from among the multiple first groups, first groups whose first representative objects, which are centroids of each of the multiple first groups, are in the vicinity of the search query as the target first groups.

In this way, the information processing device 100F can appropriately perform search processing according to the group by selecting, as the target first groups, first groups whose first representative objects, which are the centroids of each of the multiple first groups, are in the vicinity of the search query.

The acquisition unit 131 acquires a graph in which the first representative objects of each of the multiple first groups are connected by edges. The search processing unit 133F uses the graph to select a group of target first groups.

In this way, the information processing device 100F can perform appropriate search processing according to the group by selecting the target first group group using a graph.

The search processing unit 133F ends the search process when the comparison result between the reference value based on the value indicating the search range in the search process and the first target distance, which is the distance corresponding to one first group, satisfies a predetermined condition.

In this way, when the comparison result between the reference value based on the value indicating the search range in the search process and the first target distance, which is the distance corresponding to one first group, satisfies a predetermined condition, the information processing device 100F can execute the search process appropriately according to the group by terminating the search process.

If the first target distance is greater than the reference value, the search processing unit 133F terminates the search process.

In this way, when the first target distance is greater than the reference value, the information processing device 100F terminates the search process, thereby enabling the search process to be performed appropriately according to the group.

The search processing unit 133F determines a second target distance, which is a distance corresponding to a second group, based on the objects belonging to the second group, and if the second target distance is smaller than the first target distance, updates the first target distance to the second target distance.

In this way, the information processing device 100F determines the second target distance, which is the distance corresponding to a second group, based on the objects belonging to the second group, and if the second target distance is smaller than the first target distance, updates the first target distance to the second target distance, thereby being able to perform search processing appropriately according to the group.

The search processing unit 133F determines the distance of an object that is the smallest distance from the search query among the objects that belong to the second group as the second target distance.

In this way, the information processing device 100F can perform search processing appropriately according to the group by determining the distance of an object that has the smallest distance from the search query among the objects belonging to a second group as the second target distance.

When the second target distance is greater than the reference value, the search processing unit 133F terminates the calculation process for the one second group, and selects another second group belonging to the one first group as the one second group.

In this way, when the second target distance is greater than the reference value, the information processing device 100F terminates the calculation process for the one second group and selects another second group belonging to the one first group as the one second group, thereby being able to perform the search process appropriately according to the group.

The search processing unit 133F calculates the reference value by multiplying the search range by a predetermined coefficient.

In this way, the information processing device 100F can perform appropriate search processing according to the group by multiplying the search range by a predetermined coefficient to calculate a reference value.

The search processing unit 133F calculates the reference value by multiplying the search range by a predetermined coefficient greater than 0.

In this way, the information processing device 100F can perform appropriate search processing according to the group by multiplying the search range by a predetermined coefficient greater than 0 to calculate a reference value.

The search processing unit 133F updates the search range based on the extracted candidates of nearby objects during the search process.

In this way, the information processing device 100F can perform search processing appropriately according to the group by updating the search range based on extraction candidates of nearby objects during the search processing.

The search processing unit 133F updates the search range, which is initially set to infinity.

In this way, the information processing device 100F can perform appropriate search processing according to the group by updating the search range, which is set to infinity as the initial value.

The search processing unit 133F updates the search range to the extracted candidate that has the greatest distance from the search query.

In this way, the information processing device 100F can perform appropriate search processing according to the group by updating the search range to the extracted candidate that has the greatest distance from the search query.

The search processing unit 133F selects one or more second groups in order of the shortest distance between the search query and a second representative object that is the centroid of each of the second groups.

In this way, the information processing device 100F can appropriately perform search processing according to the group by selecting one second group in order of the shortest distance between the search query and the second representative object, which is the centroid of each of the one or more second groups.

The search processing unit 133F executes a calculation process that collectively calculates the distance for objects that belong to one second group.

In this way, the information processing device 100F can execute a search process appropriately according to the group by executing a calculation process that collectively calculates the distance for objects that belong to one second group.

The search processing unit 133F executes a calculation process that is a parallel process of calculating the distance between each of the objects belonging to one second group and the search query.

In this way, the information processing device 100F can perform an appropriate search process according to the group by performing a calculation process that is a parallel process of calculating the distance between each of the objects belonging to one second group and the search query.

9. Hardware Configuration
The information processing devices 100, 100A, 100B, 100C, 100D, 100E, and 100F according to the above-described embodiments are realized by a computer 1000 having a configuration as shown in Fig. 50. Fig. 50 is a hardware configuration diagram showing an example of a computer that realizes the functions of the information processing device. The computer 1000 has a CPU 1100, a RAM 1200, a ROM (Read Only Memory) 1300, a HDD (Hard Disk Drive) 1400, a communication interface (I/F) 1500, an input/output interface (I/F) 1600, and a media interface (I/F) 1700.

The CPU 1100 operates based on a program stored in the ROM 1300 or the HDD 1400, and controls each component. The ROM 1300 stores a boot program executed by the CPU 1100 when the computer 1000 is started, and programs that depend on the hardware of the computer 1000, etc.

HDD 1400 stores programs executed by CPU 1100 and data used by such programs. Communication interface 1500 receives data from other devices via network N and sends it to CPU 1100, and transmits data generated by CPU 1100 to other devices via network N.

The CPU 1100 controls output devices such as a display and a printer, and input devices such as a keyboard and a mouse, via the input/output interface 1600. The CPU 1100 acquires data from the input devices via the input/output interface 1600. The CPU 1100 also outputs generated data to the output devices via the input/output interface 1600.

The media interface 1700 reads a program or data stored in the recording medium 1800 and provides it to the CPU 1100 via the RAM 1200. The CPU 1100 loads the program from the recording medium 1800 onto the RAM 1200 via the media interface 1700 and executes the loaded program. The recording medium 1800 is, for example, an optical recording medium such as a DVD (Digital Versatile Disc) or a PD (Phase change rewritable Disc), a magneto-optical recording medium such as an MO (Magneto-Optical disk), a tape medium, a magnetic recording medium, or a semiconductor memory.

For example, when the computer 1000 functions as the information processing device 100 according to the first embodiment, the CPU 1100 of the computer 1000 executes programs loaded onto the RAM 1200 to realize the functions of the control unit 130. The CPU 1100 of the computer 1000 reads and executes these programs from the recording medium 1800, but as another example, the CPU 1100 may obtain these programs from another device via the network N.

Although several embodiments of the present application have been described in detail above with reference to the drawings, these are merely examples, and the present invention can be embodied in other forms with various modifications and improvements based on the knowledge of those skilled in the art, including the aspects described in the lines of the disclosure of the invention.

10. Other
In addition, among the processes described in the above embodiments, all or part of the processes described as being performed automatically can be performed manually, or all or part of the processes described as being performed manually can be performed automatically by a known method. In addition, the information including the processing procedures, specific names, various data and parameters shown in the above documents and drawings can be changed arbitrarily unless otherwise specified. For example, the various information shown in each drawing is not limited to the illustrated information.

In addition, each component of each device shown in the figure is a functional concept, and does not necessarily have to be physically configured as shown in the figure. In other words, the specific form of distribution and integration of each device is not limited to that shown in the figure, and all or part of them can be functionally or physically distributed and integrated in any unit depending on various loads, usage conditions, etc.

In addition, the processes described in each of the above embodiments can be combined as appropriate to the extent that the process content is not contradictory.

The above-mentioned "section, module, unit" can be read as "means" or "circuit." For example, an acquisition unit can be read as an acquisition means or an acquisition circuit.

1 Information processing system 10 Terminal device 50 Information providing device 100, 100A to 100F Information processing device 120, 120A to 120C Storage unit 121 Object information storage unit 122 Graph information storage unit 123, 123A Quantization information storage unit 124 Codebook information storage unit 125, 125A Blob information storage unit 126, 126A Blob connection graph information storage unit 130, 130A to 130F Control unit 131 Acquisition unit 132, 132A to 132F Generation unit (processing unit)
133, 133A to 133F Search processing unit 134 Provision unit

Claims (20)

an acquisition unit that acquires group information indicating a plurality of first groups into which a plurality of objects to be subjected to a data search are classified and one or more second groups into which objects belonging to each of the plurality of first groups are classified, and a search query for the plurality of objects;
a search processing unit that selects one first group from a target first group group selected from the plurality of first groups in order of the shortest distance between a first representative object of each of the target first groups and the search query, selects one second group from second groups belonging to the selected one first group in order of the shortest distance between a second representative object and the search query, executes a calculation process to calculate a distance between the search query and an object belonging to the selected one second group as a target object, and executes a search process to extract a nearby object corresponding to the search query based on the distance between each of the target objects and the search query calculated by the calculation process;
An information processing device comprising: The search processing unit:
The information processing apparatus according to claim 1 , wherein a predetermined number of the first groups are selected as the target first groups from among the plurality of first groups. The search processing unit:
The information processing apparatus according to claim 1 , wherein, from among the plurality of first groups, a first group whose representative object is in the vicinity of the search query is selected as the target first group group. The search processing unit:
The information processing apparatus according to claim 3 , further comprising: selecting, as the target first groups, first groups in which the first representative object, which is a centroid of each of the plurality of first groups, is in the vicinity of the search query. The acquisition unit is
obtaining a graph in which the first representative objects of each of the plurality of first groups are connected by edges;
The search processing unit:
The information processing apparatus according to claim 3 , wherein the first target groups are selected using the graph. The search processing unit:
The information processing device according to claim 1, characterized in that, when a comparison result between a reference value based on a value indicating a search range in the search process and a first target distance which is a distance corresponding to the first group satisfies a predetermined condition, the search process is terminated. The search processing unit:
The information processing apparatus according to claim 6 , wherein the search process is terminated when the first object distance is greater than the reference value. The search processing unit:
The information processing device according to claim 6, characterized in that a second object distance, which is a distance corresponding to the one of the second groups, is determined based on an object belonging to the one of the second groups, and if the second object distance is smaller than the first object distance, the first object distance is updated to the second object distance. The search processing unit:
The information processing apparatus according to claim 8 , wherein the second target distance is determined to be a distance of an object that has a minimum distance from the search query among the objects that belong to the second group. The search processing unit:
The information processing device according to claim 8, characterized in that, when the second target distance is greater than the reference value, the calculation process for the one second group is terminated, and another second group belonging to the one first group is selected as the one second group. The search processing unit:
The information processing apparatus according to claim 6 , wherein the reference value is calculated by multiplying the search range by a predetermined coefficient. The search processing unit:
The information processing apparatus according to claim 11 , wherein the reference value is calculated by multiplying the search range by the predetermined coefficient that is greater than zero. The search processing unit:
The information processing apparatus according to claim 6 , wherein the search range is updated based on extraction candidates of nearby objects during the search process. The search processing unit:
The information processing apparatus according to claim 13 , further comprising: updating the search range, which is set to infinity as an initial value. The search processing unit:
The information processing apparatus according to claim 13 , further comprising: updating the search range to a position among the candidates that has the greatest distance from the search query. The search processing unit:
The information processing apparatus according to claim 1 , further comprising: selecting the second group in order of the shortest distance between the search query and the second representative object that is a centroid of each of the one or more second groups. The search processing unit:
The information processing apparatus according to claim 1 , further comprising: a step of executing the calculation process for collectively calculating the distance for the objects belonging to the one second group. The search processing unit:
The information processing apparatus according to claim 17 , further comprising: executing the calculation process, which is a parallel process of calculating the distance between each of the objects belonging to the one second group and the search query. 1. A computer-implemented information processing method, comprising:
an acquisition step of acquiring group information indicating a plurality of first groups into which a plurality of objects to be subjected to a data search are classified and one or more second groups into which objects belonging to each of the plurality of first groups are classified, and a search query for the plurality of objects;
a search processing step of selecting one first group from a target first group group selected from the plurality of first groups in order of the shortest distance between a first representative object of each of the target first groups and the search query, selecting one second group from second groups belonging to the selected one first group in order of the shortest distance between a second representative object and the search query, performing a calculation process to calculate a distance between the search query and an object belonging to the selected one second group as a target object, and performing a search process to extract a nearby object corresponding to the search query based on the distance between each of the target objects and the search query calculated by the calculation process;
13. An information processing method comprising: an acquisition step of acquiring group information indicating a plurality of first groups into which a plurality of objects to be subjected to a data search are classified and one or more second groups into which objects belonging to each of the plurality of first groups are classified, and a search query for the plurality of objects;
a search processing procedure for selecting one first group from a target first group group selected from the plurality of first groups in order of the shortest distance between a first representative object of each of the target first groups and the search query, selecting one second group from second groups belonging to the selected one first group in order of the shortest distance between a second representative object and the search query, performing a calculation process for calculating a distance between the search query and an object belonging to the selected one second group as a target object, and performing a search process for extracting a nearby object corresponding to the search query based on the distance between each of the target objects and the search query calculated by the calculation process;
An information processing program characterized by causing a computer to execute the above.

Images