JP7080803B2 - Information processing equipment, information processing methods, and information processing programs - Google Patents

Description

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

Conventionally, a technique for searching (searching) various information has been provided. For example, there is provided a technique for generating graph data in which nodes corresponding to a search target are connected by directed edges in order to perform a search for a predetermined target. Further, such a technique is used, for example, for image retrieval and the like.

Japanese Patent No. 6293335 Japanese Patent No. 630982

However, with the above-mentioned prior art, it may be difficult to appropriately generate a graph used for searching. For example, regardless of the tendency of the nodes (objects) that make up the graph, if the number of edges connecting the nodes is set to a predetermined value when the graph is generated, a graph that enables efficient search is generated. It is not always possible.

The present application has been made in view of the above, and an object of the present application is to provide an information processing apparatus, an information processing method, and an information processing program for appropriately generating a graph used for a search.

The information processing apparatus according to the present application includes a single object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a directed edge connecting the nodes. An acquisition unit for acquiring one graph, a selection unit for selecting a neighboring node located in the vicinity of one node corresponding to the one object among the plurality of nodes based on the first graph, and the above-mentioned One node is added to the first graph, and with respect to the connection of the directed edges, the directed edge is used between the one node and the neighboring node based on the connection condition changed by a predetermined condition. It is characterized by having a generation unit for generating a concatenated second graph.

According to one aspect of the embodiment, there is an effect that the graph used for the search can be appropriately generated.

FIG. 1 is a diagram showing an example of information processing according to an embodiment. FIG. 2 is a diagram showing a configuration example of an information processing system according to an embodiment. FIG. 3 is a diagram showing a configuration example of the information processing apparatus according to the embodiment. FIG. 4 is a diagram showing an example of an object information storage unit according to an embodiment. FIG. 5 is a diagram showing an example of a connection condition information storage unit according to an embodiment. FIG. 6 is a diagram showing an example of a change condition information storage unit according to an embodiment. FIG. 7 is a diagram showing an example of a graph data storage unit according to an embodiment. FIG. 8 is a diagram showing an example of a starting point information storage unit according to an embodiment. FIG. 9 is a diagram showing an example of the reconstruction condition information storage unit according to the embodiment. FIG. 10 is a diagram showing an example of the reconstructed graph data storage unit according to the embodiment. FIG. 11 is a flowchart showing an example of information processing according to the embodiment. FIG. 12 is a flowchart showing an example of the condition change process according to the embodiment. FIG. 13 is a diagram showing an example of a graph reconstruction process according to an embodiment. FIG. 14 is a flowchart showing an example of the graph reconstruction process according to the embodiment. FIG. 15 is a diagram showing an example of starting point information used for information processing according to the embodiment. FIG. 16 is a flowchart showing an example of a search process using graph data. FIG. 17 is a hardware configuration diagram showing an example of a computer that realizes the functions of the information processing device.

Hereinafter, the information processing apparatus, the information processing method, and the embodiment for implementing the information processing program (hereinafter referred to as “the embodiment”) according to the present application will be described in detail with reference to the drawings. It should be noted that this embodiment does not limit the information processing apparatus, information processing method, and information processing program according to the present application. Further, in each of the following embodiments, the same parts are designated by the same reference numerals, and duplicate explanations are omitted.

(Embodiment)
[1. Information processing]
An example of information processing according to the embodiment will be described with reference to FIG. FIG. 1 is a diagram showing an example of information processing according to an embodiment. In FIG. 1, the information processing apparatus 100 (see FIG. 3) adds a node corresponding to the added object (hereinafter, also referred to as “additional node”) to the graph data (graph information) in response to the addition of the object, and graphs. The case of generating data is shown. In the following, graph data may be simply referred to as a graph. The example of FIG. 1 shows a case where the target information (object) is vectorized and a graph (graph index) is generated for the vectorized object. That is, in the example of FIG. 1, a case where the information processing apparatus 100 processes a vector as an object value corresponding to the object is shown. The information used by the information processing apparatus 100 is not limited to a vector, and may be any form of information as long as it can express the similarity of each object. For example, the information processing apparatus 100 may use predetermined data or values corresponding to each object. For example, the information processing apparatus 100 may use a predetermined numerical value (for example, a binary number value or a hexadecimal number value) generated from each object. For example, the information processing apparatus 100 is not limited to a vector, and may use any form of data as long as the distance (similarity) between the data is defined. Further, although the case where the image information is used as an object will be described below as an example, the object may be various objects such as moving image information and audio information.

Further, the addition of an object here may be read as the registration of an object. The addition of an object performed by the information processing apparatus 100 may mean registering (storing) the object in the object information storage unit 121 (see FIG. 4). Further, the addition of a node here may be read as the registration of a node. The addition of the node performed by the information processing apparatus 100 may be to register (store) the node in the graph data storage unit 124 (see FIG. 7).

Further, in the following, the graph before the addition of one node may be referred to as the first graph, and the graph to which the one node is added may be referred to as the second graph, but the first graph and the second graph are relative. The second graph generated becomes the first graph when the next node is added. For example, the second graph after adding one node is used as the first graph when a new node is added next. That is, the first graph and the second graph referred to here are names for distinguishing and expressing the graphs before and after the addition of a certain node.

Further, as shown in FIG. 1, the information processing apparatus 100 performs information processing on a graph including a node and a directed edge as a generation target. The directed edge here means an edge in which data can be traced in only one direction. In the following, the source traced by the edge, that is, the node that is the start point is referred to as the reference source, and the destination that is traced by the edge, that is, the node that is the end point is referred to as the reference destination. For example, the directed edge connected from the predetermined node "A" to the predetermined node "B" indicates that the reference source is the node "A" and the reference destination is the node "B".

In the following, the edge with the node "A" as the reference source is referred to as the output edge of the node "A". Further, in the following, such an edge with the node "B" as a reference destination is referred to as an input edge of the node "B". That is, the output edge and the input edge referred to here are differences in which node of the two nodes to which the directed edge is connected is regarded as the center, and the directed edge is one directed. The edge becomes the output edge and the input edge. That is, the output edge and the input edge are relative concepts, and when one directed edge is regarded as the center of the reference node, the output edge is regarded as the center of the reference node. In some cases it becomes the input edge. In the present embodiment, since the edge is a directed edge such as an output edge or an input edge, the directed edge may be simply referred to as an “edge” in the following.

Further, each node referred to here corresponds to each object. For example, each of the plurality of local features extracted from the image may be an object. Further, for example, various data in which the distance between objects is defined may be an object.

The information processing device 100 performs graph generation processing for a node corresponding to a huge amount of image information within a range that can be processed by the information processing device 100 (for example, millions to hundreds of millions of millions, etc.). Only a part of it is shown. In the example of FIG. 1, for the sake of simplicity, a maximum of six nodes will be illustrated to explain the outline of the process. Further, in the example of FIG. 1, the information processing apparatus 100 sequentially adds nodes N1 and the like and edges E1 and the like according to the addition of objects from the state where there is nothing, that is, the state where there are 0 nodes and the number of edges is 0. The case where the graph GR11 is generated is shown.

Further, when described as "node N * (* is an arbitrary numerical value)" in this way, it means that the node is a node identified by the node ID "N *". For example, when described as "node N1", the node is a node identified by the node ID "N1".

Further, when "edge E * (* is an arbitrary numerical value)" is described in this way, it means that the edge is an edge identified by the edge ID "E *". For example, when described as "edge E1", the edge is an edge identified by the edge ID "E1". For example, the edge E1 connected with the node N1 as the reference source and the node N2 as the reference destination makes it possible to trace from the node N1 to the node N2. In this case, the edge E1 which is a directed edge becomes an output edge when it is identified with the node N1 as the center, and becomes an input edge when it is identified with the node N2 as the center. In other words, the edge E1 which is a directed edge becomes an edge in which the arrow points from itself to another edge, that is, an outward edge, when viewed from the viewpoint from the node N1 side, and is captured from the viewpoint from the node N2 side. If so, it becomes an edge with the arrow pointing toward itself, that is, an inward-facing edge. That is, the output edge referred to here can be read as an outward edge, and the input edge can be read as an inward edge.

Further, the spatial information VS1-1 to VS1-4 shown in FIG. 1 are diagrams schematically showing the generation process of graph data, and the spaces shown in the spatial information VS1-1 to VS1-4 are the same space. You may. Further, in the following, when the spatial information VS1-1 to VS1-4 are described without particular distinction, they are described as the spatial information VS1.

Further, the spatial information VS1 in FIG. 1 may be an Euclidean space. Further, the spatial information VS1 shown in FIG. 1 is a conceptual diagram for explaining the distance between each vector, and the spatial information VS1 is a multidimensional space. For example, the spatial information VS1 shown in FIG. 1 is shown in a two-dimensional manner for being shown on a plane, but is assumed to be a multidimensional space such as 100 dimensions or 1000 dimensions.

Further, the graphs GR11-1 to GR11-4 shown in FIG. 1 are diagrams schematically showing the graph data generation process, and the graphs GR11-1 to GR11-4 are the same graph data generated by information processing. Is. Further, in the following, when the graphs GR11-1 to GR11-4 will be described without particular distinction, they will be referred to as graph GR11.

Further, in the example shown in FIG. 1, in the graphs GR11-1 to GR11-4, the illustration of "node N * (* is an arbitrary numerical value)" is appropriately omitted, and each acquired node is shown in "○". It is expressed by adding the value of "*" of "node N *". That is, it corresponds to the node in which the "*" in the "node N *" part matches. For example, "○" in the upper left of the spatial information VS1 and "○" with "4" inside corresponds to the node (node N4) identified by the node ID "N4". For example, in the example shown in FIG. 1, the vector data corresponding to each node may be an N-dimensional real value vector.

In the present embodiment, the distance of each node in the spatial information VS1 is defined as the degree of similarity between the corresponding objects. For example, it is assumed that the similarity of the target (image information) corresponding to each node is mapped as the distance between the nodes in the spatial information VS1. For example, it is assumed that the similarity between the concepts corresponding to each node is mapped to the distance between each node. Here, in the example shown in FIG. 1, the similarity between the objects having a short distance between the nodes in the spatial information VS1 is high, and the similarity between the objects having a long distance between the nodes in the spatial information VS1 is low. For example, in the spatial information VS1 in FIG. 1, the node (node N1) identified by the node ID "N1" and the node (node N2) identified by the node ID "N2" are close to each other, that is, the distance. Is short. Therefore, it is shown that the object corresponding to the node identified by the node ID “N1” and the object corresponding to the node identified by the node ID “N2” have a high degree of similarity.

Further, for example, in the spatial information VS1 in FIG. 1, the node identified by the node ID "N2" and the node identified by the node ID "N5" are remote, that is, have a long distance. Therefore, it is shown that the object corresponding to the node identified by the node ID “N2” and the object corresponding to the node identified by the node ID “N5” have a low degree of similarity. The distance as an index indicating the degree of similarity may be any distance as long as it can be applied as a distance between vectors (N-dimensional vectors), for example, Euclidean distance, Mahalanobis distance, cosine distance, and the like. Various distances may be used.

Further, in the example of FIG. 1, the information processing apparatus 100 adds a newly added node to the graph GR11 by the graph generation process described later, and generates the graph GR11 by connecting the nodes with directed edges. For example, at the time of generating the graph GR11 or searching using the graph GR11, the same processing as the graph structure type index is performed, but the start position (starting point) is the predetermined starting point information (hereinafter, also referred to as “starting point index”). ) May be used to start from the node (hereinafter also referred to as the "starting node"). Further, for example, when performing a search using the graph GR11 generated by the information processing apparatus 100, the search may be performed using a predetermined starting node as a starting point. For example, at the time of generation or search, when the starting node is node N1, the nodes N2 to N5, N11 and the like may be searched by tracing the directed edge from the node N1. The information processing apparatus 100 may search (search) nearby nodes by the processing procedure as shown in FIG. 16 at the time of generation or search, but the details will be described later.

From here, the details of information processing will be described with reference to FIG. It should be noted that each step shown in FIG. 1 is a convenient step for explaining the generation of the graph, and the actual processing may be performed by a more detailed processing step. The information processing performed by the information processing apparatus 100 may be any processing flow as long as the graph GR11 as shown in the graph GR11-4 in FIG. 1 is generated.

Further, in the example of FIG. 1, as shown in the connection condition list LCL1, the connection condition shows the case where the input threshold value is “2” and the output threshold value is “1”. That is, the information processing apparatus 100 generates a graph so that at least two input edges and one output edge are connected to each node based on the connection condition list LCL1. Further, in the example of FIG. 1, a case where the connection condition is changed based on the change condition as shown in the change condition list ACL1 and the change condition list ACL2 is shown. In the example of FIG. 1, the edge statistics shown in the change condition list ACL2 are assumed to be the average value of the number of input edges of the top 20% of the nodes having a large number of input edges, and the threshold value ETH1 is "5". It shall be. In the example of FIG. 1, for the sake of simplicity, the average value of the number of input edges of the top 20% of nodes having a large number of input edges will be described as an example of statistical information, but statistically. The information may be various information. For example, the statistical information may be various conditions depending on the connection condition such as a graph and how to add an edge. For example, statistical information is not limited to using information on some nodes and edges such as the average value of the number of input edges such as the top 20% of nodes with a large number of input edges, and the nodes and edges of the entire graph. Information may be used. Further, for example, the statistical information may be the average of the number of output edges of a certain number of initial registration nodes. For example, the statistical information may be the average of the number of output edges of 100 nodes of the node added 100th from the node added first. The information processing apparatus 100 may store information as shown in the change condition list ACL1 and the change condition list ACL2 in the change condition information storage unit 123 or the like (see FIG. 6).

First, the information processing apparatus 100 newly adds a node N1 (step S11). For example, the information processing apparatus 100 adds the node N1 to the graph. In the example of FIG. 1, since the node N1 is the first node, the information processing apparatus 100 newly generates the graph GR11 including the node N1. Further, since the information processing apparatus 100 has only one node N1 in the graph GR11 after step S11, the information processing apparatus 100 does not add an edge to the graph GR11.

For example, the information processing apparatus 100 acquires a newly added object as a search target, and newly adds a node corresponding to the added object. For example, the information processing apparatus 100 stores the newly added object in the object information storage unit 121 (see FIG. 4), and stores the node associated with the newly added object in the graph data storage unit 124. The information processing apparatus 100 adds a node N1 corresponding to an object (see FIG. 4) identified by the object ID “OB1” to the graph GR11.

Then, the information processing apparatus 100 newly adds the node N2 (step S12). In the example of FIG. 1, for example, the information processing apparatus 100 adds a node N2 to the graph GR11. The information processing apparatus 100 adds a node N2 corresponding to an object (see FIG. 4) identified by the object ID “OB2” to the graph GR11.

Then, the information processing apparatus 100 generates a graph (step S13). The information processing apparatus 100 generates a graph based on the connection condition list LCL1 so that two input edges and one output edge are connected to the added node N2. The information processing apparatus 100 generates the graph GR11-1 by adding an edge connected to the added node N2. In the example of FIG. 1, since the information processing apparatus 100 has only the node N1 other than the node N2 in the graph GR11, the edge E1 which is an input edge input from the node N1 to the node N2 and the node N1 from the node N2 Graph GR11-1 is generated by adding an edge E2 which is an output edge to be output to. Then, since the graph GR11-1 has no node other than the node N1 for connecting the edge to the node N2, the information processing apparatus 100 ends the process of connecting the edge to the node N2. The information processing apparatus 100 searches for the graph GR11, selects the node N1 as a node in the vicinity of the node N2, and adds the edges E1 and E2 to the node N1 to generate the graph GR11-1. You may.

Further, the information processing apparatus 100 generates a determination information list DFI1 based on the graph GR11-1. The information processing apparatus 100 generates a determination information list DFI1 based on the node and edge information included in the graph GR11-1. For example, the information processing apparatus 100 generates a determination information list DFI1 including statistical information. The information processing apparatus 100 generates a determination information list DFI1 indicating that the number of nodes included in the graph GR11-1 is two and the number of edges included in the graph GR11-1 is two. The information processing apparatus 100 may generate statistical information of various graphs, not limited to the number of nodes and the number of edges, as long as the information is used for determining the condition. The determination information list DFI1 may include information (edge statistics) indicating the average value of the number of input edges such as the top 20% of the nodes having a large number of input edges in the graph GR11-1. When the number of nodes in the top 20% is less than 1 as in graph GR11-1, the information processing apparatus 100 is in the top 20%. The number of nodes of is set to "1", and the number of input edges of the node having the maximum number of input edges is used as the edge statistic value. For example, the information processing apparatus 100 may store the determination information list DFI1 in the storage unit 120 (see FIG. 3). Further, the decimal point in the case of "1" or more may be rounded down, rounded off, or rounded up.

Then, the information processing apparatus 100 determines whether or not the graph GR11-1 satisfies the change condition. For example, the information processing apparatus 100 determines that the number of nodes included in the graph GR11-1 is two, and therefore the change condition that the number of nodes shown in the change condition list ACL1 is 100 is not satisfied. For example, the information processing apparatus 100 compares the number of nodes "2" in the decision information list DFI1 with the number of nodes "100" in the change condition list ACL1 and compares the number of nodes "100" in the decision information list DFI1 with the number of nodes "2" in the decision information list DFI1. Is different from the number of nodes "100" in the change condition list ACL1, so it is determined that the change condition is not satisfied. Further, in the information processing apparatus 100, in the graph GR11-1, the average value of the number of input edges of the top 20% of the nodes having a large number of input edges is "1", which is less than the threshold value ETH1. It is determined that the edge statistical value shown in ACL2 does not satisfy the change condition of the threshold value ETH1 or more. In this way, the information processing apparatus 100 determines that the graph GR11-1 does not satisfy the change condition. Therefore, the information processing apparatus 100 continues the process without changing the connection condition. That is, the information processing apparatus 100 continues the processing without changing the input threshold value “2” and the output threshold value “1”.

Then, the information processing apparatus 100 newly adds the node N3 (step S14-1). In the example of FIG. 1, for example, the information processing apparatus 100 adds a node N3 corresponding to the added object to the graph GR11.

Then, the information processing apparatus 100 searches for the graph (step S14-2). For example, the information processing apparatus 100 searches (searches) for a node (neighboring node) located in the vicinity of the additional node by the processing procedure as shown in FIG. For example, the information processing apparatus 100 selects a predetermined number (hereinafter, also referred to as “selection number”) of neighboring nodes by searching the graph by the processing procedure as shown in FIG. For example, the information processing apparatus 100 determines the number of selections according to the input threshold value and the output threshold value. In the example of FIG. 1, the information processing apparatus 100 determines the input threshold value “2”, which is a larger value, as the selection number. The information processing apparatus 100 may determine the number of selections to be larger than the input threshold value and the output threshold value. For example, the information processing apparatus 100 may determine various values such as "100" as the selection number. For example, the information processing apparatus 100 may determine the number of selections by appropriately using various information. For example, the information processing apparatus 100 may determine the number of selections (the number of neighboring nodes) based on the performance of searching the graph after generation. Further, for example, the information processing apparatus 100 may dynamically change the number of selections during graph generation. For example, the information processing apparatus 100 may check the search performance in the middle of graph generation and increase or decrease the number of selections. For example, the information processing apparatus 100 may increase or decrease the number of selections based on the search performance of the graph being generated. For example, the information processing apparatus 100 may increase or decrease the number of selections based on a comparison between a value indicating the search performance of the graph being generated and a predetermined threshold value. In this way, the information processing apparatus 100 may dynamically change the conditions regarding the number of selections.

The information processing apparatus 100 searches for the graph GR11-1 by using the node N3, which is an additional node, as a query, by the processing procedure as shown in FIG. Select the nodes N1 and N2 of. Further, in the example of FIG. 1, the node N1 is located closer to the node N3 than the node N2. In this way, the information processing apparatus 100 can select the neighboring nodes more efficiently by selecting the neighboring nodes of the additional node using the graph being generated, and enable efficient graph generation. .. For example, even when the number of nodes included in the graph increases, the information processing apparatus 100 increases the processing time for selecting the neighboring node by using the graph being generated for selecting the neighboring node of the additional node. It is possible to suppress the above, select neighboring nodes more efficiently, and enable efficient graph generation. That is, the information processing apparatus 100 can generate a graph at a higher speed by selecting a node in the vicinity of the additional node using the graph being generated. The information processing apparatus 100 may select the neighboring node by any method as long as the neighboring node can be selected. For example, the information processing apparatus 100 uses information indicating the distance between each node and the additional node in the graph being generated. Then, the neighboring nodes of the selected number may be selected in order from the one with the closest distance.

The information processing apparatus 100 may determine the starting node by using the information for the starting point of the tree structure having the nodes N1 and N2 of the graph GR11-1 as leaves in order to speed up the processing. Details will be described later. For example, the information processing apparatus 100 may determine the node N1 among the nodes N1 and N2 of the graph GR11-1 as the starting node by using the starting point information of the tree structure as shown in FIG. As described above, the information processing apparatus 100 can efficiently search the graph by determining the starting point node using the starting point information corresponding to the graph being generated, so that the neighboring node can be searched more efficiently. It can be selected to enable efficient graph generation. For example, even when the number of nodes included in the graph increases, the information processing apparatus 100 suppresses an increase in the processing time for selecting the starting node by determining the starting node using the starting information. , It is possible to select the starting node more efficiently and enable efficient graph generation.

Then, the information processing apparatus 100 generates the second graph by adding the directed edge connecting the node and the neighboring node to the first graph based on the connection condition (step S14-3). In the example of FIG. 1, the information processing apparatus 100 has a graph GR11-1 which is a first graph showing a directed edge connecting a node N3 and neighboring nodes N1 and N2 based on the connection condition list LCL1. By adding to, the graph GR11-2, which is the second graph, is generated. Specifically, the information processing apparatus 100 generates the graph GR11-2 so that two input edges and one output edge are connected to the node N3 based on the connection condition list LCL1.

The information processing apparatus 100 connects the input edges to the node N3 to the two selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E3 to be input to the node N3 to the node N1 having the shortest distance among the selected neighboring nodes N1 and N2. As a result, the information processing apparatus 100 connects the node N1 and the node N3, which are nodes in the vicinity of the node N3.

The information processing apparatus 100 connects the edge E5 to be input to the node N3 to the node N2 having the second shortest distance among the selected neighboring nodes N1 and N2. As a result, the information processing apparatus 100 connects the node N2 and the node N3, which are nodes in the vicinity of the node N3.

Further, the information processing apparatus 100 connects the output edge from the node N3 to one of the selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E4 output from the node N3 to the node N1 having the shortest distance among the selected neighboring nodes N1 and N2. As a result, the information processing apparatus 100 connects the node N3 and the node N1 which is a neighboring node thereof. As a result, the information processing apparatus 100 generates a graph GR11-2 in which two input edges E3, E5 and one output edge E4 are connected to the added node N3.

Further, the information processing apparatus 100 generates the determination information list DFI2 based on the graph GR11-2. For example, the information processing apparatus 100 generates the decision information list DFI2 by updating the decision information list DFI1. The information processing apparatus 100 generates a determination information list DFI2 indicating that the number of nodes included in the graph GR11-2 is three and the number of edges included in the graph GR11-2 is five. For example, the information processing apparatus 100 may update the determination information list DFI1 stored in the storage unit 120 (see FIG. 3) to the determination information list DFI2.

Then, the information processing apparatus 100 determines whether or not the graph GR11-2 satisfies the change condition. For example, the information processing apparatus 100 determines that the number of nodes included in the graph GR11-2 is three, and therefore the change condition that the number of nodes shown in the change condition list ACL1 is 100 is not satisfied. For example, the information processing apparatus 100 compares the number of nodes "3" in the decision information list DFI2 with the number of nodes "100" in the change condition list ACL1 and compares the number of nodes "3" in the decision information list DFI2. Is different from the number of nodes "100" in the change condition list ACL1, so it is determined that the change condition is not satisfied. Further, in the information processing apparatus 100, in the graph GR11-2, the average value of the number of input edges of the top 20% of the nodes having a large number of input edges is "2", which is less than the threshold value ETH1. It is determined that the edge statistical value shown in ACL2 does not satisfy the change condition of the threshold value ETH1 or more. As described above, the information processing apparatus 100 determines that the graph GR11-2 does not satisfy the change condition (step S14-4). Therefore, the information processing apparatus 100 continues the process without changing the connection condition. That is, the information processing apparatus 100 continues the processing without changing the input threshold value “2” and the output threshold value “1”.

Then, the information processing apparatus 100 newly adds the nodes N4, N5, and the like (step S15-1). For example, the information processing apparatus 100 sequentially adds 97 nodes including the nodes N4 and N5 to the graph GR11-2. In the example of FIG. 1, the information processing apparatus 100 adds the node N4 to the graph GR11-2, and then sequentially adds 96 nodes such as the node N5 to the graph GR11.

Then, the information processing apparatus 100 searches for the graph (step S15-2). In the example of FIG. 1, the information processing apparatus 100 searches the graph GR11-2 using the added node N4 as a query. The information processing apparatus 100 searches the graph GR11-2 by the processing procedure as shown in FIG. 16, and selects two nodes N1 and N3 corresponding to the selection number "2" as the neighboring nodes of the node N4. Further, in the example of FIG. 1, the node N3 is located closer to the node N4 than the node N1. For example, the information processing apparatus 100 may determine the node N3 among the nodes N1 to N3 of the graph GR11-2 as the starting node by using the starting point information of the tree structure as shown in FIG.

Then, the information processing apparatus 100 generates the second graph by adding the directed edge connecting the node and the neighboring node to the first graph based on the connection condition (step S15-3). In the example of FIG. 1, in the information processing apparatus 100, the directed edge connecting the node N4 and the neighboring nodes N1 and N3 is shown in the graph GR11-2, which is the first graph, based on the connection condition list LCL1. By adding to, the graph GR11-3 which is the second graph is generated. Specifically, the information processing apparatus 100 generates the graph GR11-3 so that two input edges and one output edge are connected to the node N4 based on the connection condition list LCL1.

The information processing apparatus 100 connects the input edges to the node N4 to the two selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E7 to be input to the node N4 to the node N3 having the shortest distance among the selected neighboring nodes N1 and N3. As a result, the information processing apparatus 100 connects the node N3 and the node N4, which are nodes in the vicinity of the node N4.

The information processing apparatus 100 connects the edge E6 to be input to the node N4 to the node N1 having the second shortest distance among the selected neighboring nodes N1 and N3. As a result, the information processing apparatus 100 connects the node N1 and the node N4, which are nodes in the vicinity of the node N4.

Further, the information processing apparatus 100 connects the output edge from the node N4 to one of the selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E8 output from the node N4 to the node N3 having the shortest distance among the selected neighboring nodes N1 and N3. As a result, the information processing apparatus 100 connects the node N4 and the node N3 which is a node in the vicinity thereof. As a result, the information processing apparatus 100 generates a graph GR11-3 in which two input edges E6 and E7 and one output edge E8 are connected to the added node N4.

Further, the information processing apparatus 100 also generates the graph GR11-3 by sequentially adding the 96 nodes such as the node N5 to the graph GR11 in the same manner as the node N4.

For example, when the node N5 is added after the node N4 is added, the information processing apparatus 100 selects the nodes N1 and N4 as the neighboring nodes of the node N5. Further, in the example of FIG. 1, the node N1 is located closer to the node N5 than the node N4. Then, the information processing apparatus 100 connects the edge N9, which is an input edge to the node N5, to the node N1, and connects the edge N10, which is an input edge to the node N5, to the node N4. Further, the information processing apparatus 100 connects the edge N11, which is the output edge from the node N5, to the node N1. As a result, the information processing apparatus 100 generates a graph GR11-3 in which two input edges E9 and E10 and one output edge E11 are connected to the added node N5. Further, the information processing apparatus 100 also generates the graph GR11-3 by sequentially adding the remaining 95 nodes other than the nodes N4 and N5 to the graph GR11 in the same manner as the nodes N4 and N5.

Further, the information processing apparatus 100 generates a determination information list DFI3 based on the graph GR11-3. For example, the information processing apparatus 100 generates the decision information list DFI3 by updating the decision information list DFI2. The information processing apparatus 100 generates a determination information list DFI3 indicating that the number of nodes included in the graph GR11-3 is 100 and the number of edges included in the graph GR11-3 is 200. For example, the information processing apparatus 100 may update the determination information list DFI2 stored in the storage unit 120 (see FIG. 3) to the determination information list DFI3.

Then, the information processing apparatus 100 determines whether or not the graph GR11-3 satisfies the change condition. For example, since the information processing apparatus 100 includes 100 nodes in the graph GR11-3, it is determined that the change condition that the number of nodes shown in the change condition list ACL1 is 100 is satisfied. For example, the information processing apparatus 100 compares the number of nodes "100" in the decision information list DFI3 with the number of nodes "100" in the change condition list ACL1 and compares the number of nodes "100" in the decision information list DFI3 with "100". Matches the number of nodes "100" in the change condition list ACL1, so it is determined that the change condition is satisfied. In this way, the information processing apparatus 100 determines that the graph GR11-3 satisfies the change condition (step S15-4).

Therefore, the information processing apparatus 100 changes the connection condition (step S16). In the example of FIG. 1, the information processing apparatus 100 changes the connection condition based on the change content of the change condition list ACL1 that satisfies the condition. The information processing apparatus 100 increases the input threshold value by 1 as shown in the change condition list ACL1. The information processing apparatus 100 generates the connection condition list LCL2 based on the change contents in the change condition list ACL1. For example, the information processing apparatus 100 generates the connection condition list LCL2 by updating the connection condition list LCL1. The information processing apparatus 100 generates a concatenation condition list LCL2 indicating that the input threshold value is “3” and the output threshold value is “1”. For example, the information processing apparatus 100 may update the information shown in the connection condition list LCL1 stored in the connection condition information storage unit 122 or the like (see FIG. 5) to the information shown in the connection condition list LCL2.

In the processing after step S16, the information processing apparatus 100 sets the input threshold value to "3" and continues the processing. As described above, the information processing apparatus 100 can appropriately change the graph generation conditions according to the graph generation specifics and the like by dynamically changing the connection conditions in the graph generation process, which is appropriate. Graph generation can be performed. Further, the information processing apparatus 100 updates the number of selections according to the change of the connection condition. In the example of FIG. 1, the information processing apparatus 100 determines the input threshold value “3”, which is a larger value, as the selection number. That is, the information processing apparatus 100 updates the number of selections from "2" to "3".

Then, the information processing apparatus 100 newly adds the node N11 and the like (step S17-1). For example, the information processing apparatus 100 sequentially adds a large number of nodes (for example, 1000 or the like) including the node N11 to the graph GR11-3. In the example of FIG. 1, the information processing apparatus 100 adds a node N11 to the graph GR11-3, and then sequentially adds a large number of remaining nodes to the graph GR11.

Then, the information processing apparatus 100 searches for the graph (step S17-2). In the example of FIG. 1, the information processing apparatus 100 searches the graph GR11-3 using the added node N11 as a query. The information processing apparatus 100 searches the graph GR11-3 by the processing procedure as shown in FIG. 16, and selects three nodes N1, N4, and N5 corresponding to the selection number "3" as the neighboring nodes of the node N11. .. Further, in the example of FIG. 1, the node N5 is located closest to the node N11, and is located near the node N11 in the order of the nodes N5, N1, and N4. For example, the information processing apparatus 100 determines the node N5 as the starting node among the 100 nodes including the nodes N1 to N5 of the graph GR11-3 by using the starting point information of the tree structure as shown in FIG. You may.

Then, the information processing apparatus 100 generates the second graph by adding the directed edge connecting the node and the neighboring node to the first graph based on the connection condition (step S17-3). In the example of FIG. 1, in the information processing apparatus 100, the directed edge connecting the node N11 and the neighboring nodes N1, N4, and N5 based on the connection condition list LCL2 is the graph GR11 which is the first graph. By adding to -3, the second graph, graph GR11-4, is generated. Specifically, the information processing apparatus 100 generates the graph GR11-4 so that three input edges and one output edge are connected to the node N11 based on the connection condition list LCL2.

The information processing apparatus 100 connects the input edges to the node N11 to the three selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E13 to be input to the node N11 to the node N5 having the shortest distance among the selected neighboring nodes N1, N4, and N5. As a result, the information processing apparatus 100 connects the node N5, which is a node in the vicinity of the node N11, with the node N11.

The information processing apparatus 100 connects the edge E14 to be input to the node N11 to the node N1 having the second shortest distance among the selected neighboring nodes N1, N4, and N5. As a result, the information processing apparatus 100 connects the node N1 and the node N11, which are nodes in the vicinity of the node N11.

The information processing apparatus 100 connects the edge E15 to be input to the node N11 to the node N4 having the third shortest distance among the selected neighboring nodes N1, N4, and N5. As a result, the information processing apparatus 100 connects the node N4, which is a node in the vicinity of the node N11, with the node N11.

Further, the information processing apparatus 100 connects the output edge from the node N11 to one of the selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E12 output from the node N11 to the node N5 having the shortest distance among the selected neighboring nodes N1, N4, and N5. As a result, the information processing apparatus 100 connects the node N11 and the node N5 which is a node in the vicinity thereof. As a result, the information processing apparatus 100 generates a graph GR11-4 in which three input edges E13 and E14 and one output edge E12 are connected to the added node N11.

Further, the information processing apparatus 100 also generates the graph GR11-4 by sequentially adding the nodes other than the node N11 to the graph GR11 in the same manner as the node N11.

Further, the information processing apparatus 100 generates a determination information list DFI4 based on the graph GR11-4. For example, the information processing apparatus 100 generates the decision information list DFI4 by updating the decision information list DFI3. In the information processing apparatus 100, the number of nodes included in the graph GR11-4 is one NNUM, the number of edges included in the graph GR11-4 is one ENUM, and the edge statistical value of the graph GR11-4 is SVL1. A determination information list DFI4 indicating that the above is generated. In the determination information list DFI4, each value is indicated by an abstract code such as NNUM1, ENUM1 or SVL1, but each value is assumed to be a specific numerical value. For example, it is assumed that the number of nodes NNUM1 is "10000", the number of edges ENUM1 is "25000", and the edge statistical value SVL1 is "5". For example, the information processing apparatus 100 may update the determination information list DFI3 stored in the storage unit 120 (see FIG. 3) to the determination information list DFI4.

Then, the information processing apparatus 100 determines whether or not the graph GR11-4 satisfies the change condition. For example, in the information processing apparatus 100, the number of nodes included in the graph GR11-4 is 1 NNUM (10000, etc.), which is larger than 100. Therefore, the change condition that the number of nodes shown in the change condition list ACL1 is 100. Is not satisfied. For example, the information processing apparatus 100 compares the number of nodes "NNUM1" in the decision information list DFI1 with the number of nodes "100" in the change condition list ACL1 and compares the number of nodes "NNUM1" in the decision information list DFI4. Is different from the number of nodes "100" in the change condition list ACL1, so it is determined that the change condition is not satisfied.

Further, in the graph GR11-4, the information processing apparatus 100 has an average value of the number of input edges such as the top 20% of nodes having a large number of input edges, that is, the edge statistical value SVL1 is "5" and is a threshold value ETH1. Since it is "5" or more, it is determined that the edge statistical value shown in the change condition list ACL2 satisfies the change condition of the threshold value ETH1 or more. In this way, the information processing apparatus 100 determines that the graph GR11-4 satisfies the change condition (step S17-4).

Therefore, the information processing apparatus 100 changes the connection condition (step S18). In the example of FIG. 1, the information processing apparatus 100 changes the connection condition based on the change content of the change condition list ACL2 that satisfies the condition. The information processing apparatus 100 increases the input threshold value by 1 and increases the output threshold value by 5 as shown in the change condition list ACL2. The information processing apparatus 100 generates a connection condition list LCL3 based on the change contents in the change condition list ACL2. For example, the information processing apparatus 100 generates the connection condition list LCL3 by updating the connection condition list LCL2. The information processing apparatus 100 generates a concatenation condition list LCL3 indicating that the input threshold value is “4” and the output threshold value is “6”. For example, the information processing apparatus 100 may update the information shown in the connection condition list LCL2 stored in the connection condition information storage unit 122 or the like (see FIG. 5) to the information shown in the connection condition list LCL3.

In the processing after step S18, the information processing apparatus 100 sets the input threshold value to "4" and the input threshold value to "6", and continues the processing. As described above, the information processing apparatus 100 can appropriately change the graph generation conditions according to the graph generation specifics and the like by dynamically changing the connection conditions in the graph generation process, which is appropriate. Graph generation can be performed. Further, the information processing apparatus 100 updates the number of selections according to the change of the connection condition. In the example of FIG. 1, the information processing apparatus 100 determines the output threshold value “6”, which is a larger value, as the selection number. That is, the information processing apparatus 100 updates the number of selections from "3" to "6".

As described above, when a node is added to the graph being generated, the information processing apparatus 100 searches the graph being generated and selects a neighboring node corresponding to the added node (additional node) at high speed. Then, the information processing apparatus 100 connects the effective edge between the selected neighboring node and the node based on the connection condition dynamically changed during generation and the additional node. As described above, the information processing apparatus 100 can be changed to an appropriate connection condition by updating the connection conditions such as the output threshold value and the input threshold value according to the generation status of the graph being generated, and is therefore used for the search. The graph can be generated properly. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

[1-1. Increase in the number of connected edges according to the graph scale]
For example, when a graph is generated, many edges tend to be concatenated to the nodes added in the early stages of generation. For example, even if three edges (two input edges and one output edge, etc.) are connected to the added node, the node registered (added) first has thousands or tens of thousands. The edges are connected. Therefore, the information processing apparatus 100 can suppress the variation in edges caused by when a node is added by increasing the number of connected edges as the graph is generated, so that the graph used for the search is appropriate. Can be generated in.

For example, the information processing apparatus 100 dynamically changes the connection condition according to the scale of the graph. In this case, the information processing apparatus 100 has three edges (one input edge and two output edges) on the additional node in the first stage when the number of nodes in the first graph is up to the first threshold value (for example, 1,000). Etc.) are connected. For example, the information processing apparatus 100 adds an edge to the graph based on a connection condition for connecting three edges (one input edge, two output edges, etc.) until the number of nodes in the graph reaches 1,000. to add.

Then, in the second stage in which the number of nodes in the first graph reaches the second threshold value (for example, 10,000), the information processing apparatus 100 has five edges (two input edges and three output edges) in the additional node. Etc.) are connected. For example, when the number of nodes in the graph satisfies the change condition of the first threshold value, the information processing apparatus 100 changes the connection condition to five edges (two input edges, three output edges, etc.) and displays the graph. Add a node. The information processing apparatus 100 adds an edge to the graph based on a connection condition for connecting five edges (two input edges, three output edges, etc.) until the number of nodes in the graph reaches 10,000. do.

Then, in the third stage where the number of nodes in the first graph is up to the third threshold value (for example, 100,000), the information processing apparatus 100 has 10 additional nodes (4 input edges, 6 output edges, etc.). Connect the edges of. For example, when the number of nodes in the graph satisfies the change condition of the second threshold value, the information processing apparatus 100 changes the connection condition to 10 (4 input edges, 6 output edges, etc.) and displays the nodes in the graph. to add. The information processing apparatus 100 adds an edge to the graph based on a connection condition for connecting 10 (4 input edges, 6 output edges, etc.) until the number of nodes in the graph reaches 100,000. Further, when the number of nodes in the graph satisfies the change condition of the third threshold value, the information processing apparatus 100 changes the connection condition to a condition in which the number of edges is further increased, and adds the node to the graph.

As described above, the information processing apparatus 100 can suppress the variation of the edges by increasing the number of edges to be connected stepwise, so that the graph used for the search can be appropriately generated.

[1-2. Graph data]
In the example of FIG. 1, the case where the information processing apparatus 100 generates the graph GR11 from the beginning (the state where the number of nodes is 0), that is, the case where the graph is newly generated is shown, but the information processing apparatus 100 Not limited to new generation, various graphs may be generated. For example, the information processing apparatus 100 may generate a graph by adding a node corresponding to the newly added object to the graph including the node and the edge. For example, the information processing apparatus 100 may generate a graph by adding a node corresponding to the newly added object to the graph whose edges have been adjusted and reconstructed. For example, the information processing apparatus 100 may generate a graph by adding a node corresponding to the newly added object to the reconstruction graph GR21 shown in FIG. 13 and updating the reconstruction graph GR21.

[1-3. Consolidation conditions]
In the example of FIG. 1, the case where the input threshold value and the output threshold value are increased by a predetermined number is shown, but the information processing apparatus 100 may change the input threshold value and the output threshold value in various ways. For example, it may be the total number of input edges and output edges that give an average value of the output edges of a certain number of initial nodes. For example, the average value of the output edges of a certain number of nodes (for example, 50 or the like) added first may be the total number of the input threshold value and the output threshold value. Further, the information processing apparatus 100 may increase the input threshold value and the output threshold value by a predetermined ratio. For example, when the target is an "input edge", the change content of the change condition ACDX is "10% increase", and the input threshold value is "10", the information processing apparatus 100 has an input threshold value of "10" lines. May be increased to "11 (= 10 + 10 * 0.1)" books. Further, the information processing apparatus 100 is not limited to increasing the input threshold value and the output threshold value, and may make changes to decrease the input threshold value and the output threshold value. The connection condition is not limited to the input threshold value and the output threshold value, and may be any condition as long as it is a condition related to edge connection at the time of graph generation.

[1-4. Change conditions]
The change condition shown in FIG. 1 is an example, and the information processing apparatus 100 may use various change conditions. For example, the information processing apparatus 100 may use a change condition based on the percentage of additional nodes added to the graph. For example, the information processing apparatus 100 may use the reconstruction condition in FIG. 13 as a change condition. For example, the information processing apparatus 100 may use a change condition on the condition that the ratio of the additional nodes among the nodes included in the graph is equal to or higher than a predetermined threshold value. For example, the information processing apparatus 100 is a change condition on the condition that the ratio of the additional nodes added after the reconstruction process, which is the adjustment process of the directed edge, among the nodes included in the graph is equal to or higher than a predetermined threshold value. May be used.

Further, for example, the information processing apparatus 100 may use a change condition regarding the graph generation time. In this case, the information processing apparatus 100 estimates the time (generation time) required for the generation process. For example, when the information processing apparatus 100 acquires information indicating the number of nodes constituting the graph (number of constituent nodes) such as the number of nodes to be added, the information processing apparatus 100 may estimate the generation time based on the number of constituent nodes. .. For example, the information processing apparatus 100 may estimate the generation time by using the processing time (sample time) at the time of adding a predetermined number (for example, 10 or 100) of nodes from the start of graph generation.

For example, the information processing apparatus 100 may estimate the generation time (estimated generation time) by using the sample time, the number of constituent nodes, and the connection condition. For example, the information processing apparatus 100 may estimate the estimated generation time by using the history information of the past graph generation. For example, the information processing apparatus 100 compares the combination of the sample time, the number of constituent nodes, and the connection condition with the history information of the past graph generation, and among the history information, the combination of the sample time, the number of constituent nodes, and the connection condition. The processing time included in the similar history may be estimated as the estimated generation time.

Then, when the information processing apparatus 100 is estimated to exceed the designated generation time (designated time), the information processing apparatus 100 may change the connection conditions so as to reduce the number of connection edges. For example, the information processing apparatus 100 may compare the estimated generation time with the designated time, and if the estimated generation time exceeds the designated time, the connection condition may be changed so as to reduce the number of connected edges.

[1-5. Information for starting point]
For example, the information processing apparatus 100 may use the starting point information IND11 regarding the tree structure (tree structure) as shown in FIG. 15 as the starting point information (starting point index). FIG. 15 is a diagram showing an example of starting point information used for information processing according to the embodiment. For example, the starting information IND11 is an index having a tree structure that can reach the nodes in the graph GR11. In the example of FIG. 15, for the sake of simplicity, the origin information IND11 illustrates only the route to reach the five nodes N1 to N5, but many other nodes (eg, 500, 1000, etc.). May include a route to reach. For example, the origin information IND11 may be reachable to all the nodes in the graph GR11.

The information processing device 100 may generate the starting point information such as the starting point information IND11, and the information processing device 100 acquires the starting point information from another external device such as the information providing device 50. May be good. For example, when the information processing apparatus 100 generates the starting point information, the information processing apparatus 100 appropriately uses various conventional techniques related to the tree structure, and the starting point information of the tree structure (for example, the graph GR11) has a node as a leaf. For example, the starting point information IND11) is generated. Further, when a new node is added to the graph (for example, graph GR11), the information processing apparatus 100 uses the node corresponding to the newly added object (also referred to as “additional node”) as a leaf for the starting point of the tree structure. It is added to the information (for example, starting information IND11). As a result, the information processing apparatus 100 updates the starting point information when a new node is added to the graph. That is, when a new node is added to the graph, the information processing apparatus 100 generates information for a starting point in which the new node is added as a leaf.

As described above, the information processing apparatus 100 appropriately uses various conventional techniques related to the tree structure to obtain a starting point index such as the starting point information IND11 stored in the starting point information storage unit 125 (see FIG. 8). Generate. For example, when a new object is added, the information processing apparatus 100 may update the starting information IND11 by adding a node corresponding to the newly added object as a leaf. In the example of FIG. 1, the information processing apparatus 100 may update the starting point information IND11 by adding the node N3, the node N4, or the like as a leaf each time the node N3, the node N4, or the like is added.

Further, when the information processing apparatus 100 acquires the starting point information from another external device, the information processing apparatus 100 provides the graph to the other external device. Then, the information processing device 100 acquires the starting point information generated by the other external device that has received the graph from the other external device. For example, when the information processing apparatus 100 acquires the starting information IND11 from the information providing apparatus 50, the information processing apparatus 100 transmits the graph GR11 to the information providing apparatus 50. Then, the information processing apparatus 100 acquires the starting point information IND11 generated by the information providing apparatus 50 that has received the graph GR11 from the information providing apparatus 50. For example, the information processing device 100 may acquire the starting point information IND11 updated by the additional node from the information providing device 50 by providing the starting point information IND11 and the information about the additional node to the information providing device 50. .. The above is an example, and the information providing device 50 may acquire the starting point information IND11 by any means as long as the starting point information IND11 can be acquired.

Further, the information processing apparatus 100 may determine the starting point node by using the starting point information IND11 as shown in the index information group GINF11 in FIG. In the example of FIG. 15, the information processing apparatus 100 determines the starting point node corresponding to the query QE1 based on the starting point information IND11. The query QE1 may be a node corresponding to the newly added object, a target to be searched using the graph GR11, or the like. That is, the information processing apparatus 100 determines the starting point node by using the starting point information IND11 at the time of graph generation or retrieval.

Specifically, the information processing apparatus 100 determines the starting point node by using the starting point information IND11 stored in the starting point information storage unit 125 (see FIG. 8). The starting point information IND11 in FIG. 15 has a hierarchical structure shown in the starting point information storage unit 125 in FIG. For example, the starting point information IND11 indicates that the node (vector) of the first layer located immediately below the root RT is a node VT1, VT2, VT3, or the like. Further, for example, the starting point information IND11 indicates that the nodes in the second layer immediately below the node VT2 are the nodes VT2-1 to VT2-4 (not shown). For example, the starting point information IND11 indicates that the node in the third layer immediately below the node VT2-1 is the node N1, N2, that is, the node (vector) in the graph GR11. Further, the starting point information IND11 indicates that the node in the third layer immediately below the node VT2-2 is the node N3, N4, N5, that is, the node (vector) in the graph GR11.

For example, the information processing apparatus 100 determines the starting point node in the graph GR11 by using the tree-structured starting point index information as shown in the starting point information IND11 in FIG. In the example of FIG. 1, the information processing apparatus 100 determines (identifies) a starting node that is a candidate for the vicinity of the starting information IND11 by tracing the starting information IND11 from the top (route RT) to the bottom based on the query QE1. )do. As a result, the information processing apparatus 100 can efficiently determine the starting node corresponding to the search query (query QE1). For example, the information processing apparatus 100 can quickly determine an appropriate starting node corresponding to the query QE1 which is an additional node.

The information processing apparatus 100 is not limited to the above, and various starting point indexes may be used. That is, the starting point information (starting point index) shown in the example of FIG. 15 is an example, and the information processing apparatus 100 may search for graph information using various starting point information. The information processing apparatus 100 may generate a starting point index used for determining the starting point node at the time of searching. For example, the information processing apparatus 100 generates a search index (starting point information) for searching a high-dimensional vector at high speed. The high-dimensional vector referred to here may be, for example, a vector having several hundred dimensions to several thousand dimensions, or a vector having more dimensions.

For example, the information processing apparatus 100 may generate a search index related to a kd tree (k-dimensional tree) as a starting index. For example, the information processing apparatus 100 may generate a search index related to a VP tree (Vantage-Point tree) as a starting index.

Further, for example, the information processing apparatus 100 may be generated as a starting index having another tree structure. For example, the information processing apparatus 100 may generate various origin indexes in which the leaf of the origin index of the tree structure is connected to the graph. For example, the information processing apparatus 100 may generate various origin indexes in which the leaf of the origin index of the tree structure corresponds to the node in the graph. Further, when the information processing apparatus 100 performs a search using such a starting point index, the information processing apparatus 100 may search for a graph from a leaf (node) reached by following the starting point index.

The starting index as described above is an example, and the information processing apparatus 100 may generate a starting index of any data structure as long as the query in the graph can be specified at high speed. good. For example, if the information processing apparatus 100 can identify a node in graph information corresponding to a query at high speed, the information processing apparatus 100 generates an index for a starting point by appropriately using various conventional techniques such as a technique related to binary space partitioning. You may. For example, the information processing apparatus 100 may generate a starting index of any data structure as long as it is a starting index capable of searching for a high-dimensional vector. The information processing apparatus 100 can enable a more efficient search for a predetermined target by using the starting index and the graph as described above. That is, the information processing apparatus 100 can execute a search for a predetermined target at a higher speed by using the starting point index and the graph as described above.

[2. Information processing system configuration]
As shown in FIG. 2, 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 communicable by wire or wirelessly. FIG. 2 is a diagram showing a configuration example of an information processing system according to an embodiment. The information processing system 1 shown in FIG. 2 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 the 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. That is, in the following, the user can be read as the terminal device 10. The terminal device 10 described above is realized by, for example, a smartphone, a tablet terminal, a notebook PC (Personal Computer), a desktop PC, a mobile phone, a PDA (Personal Digital Assistant), or the like.

The information providing device 50 is an information processing device in which information for providing various information to a user or the like is stored. For example, the information providing device 50 stores an object ID based on character information or the like collected from various external devices such as a web server. For example, the information providing device 50 is an information processing device that provides an image search service to users and the like. For example, the information providing device 50 stores each information for providing an 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. Further, the information providing device 50 receives an object ID or the like indicating an image corresponding to the query from the information processing device 100 by transmitting the query to the information processing device 100.

The information processing apparatus 100 displays a first graph including one object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a directed edge connecting the nodes. It is an information processing device that generates a second graph by using it. That is, the information processing device 100 is a generation device that generates a second graph using the first graph. For example, the information processing apparatus 100 selects a neighboring node located in the vicinity of one node corresponding to one object from among a plurality of nodes in the first graph. Then, the information processing apparatus 100 adds one node to the first graph, and has a connection between the one node and the neighboring node based on the connection condition changed by a predetermined condition regarding the connection of the directed edge. A second graph connected by a directed edge is generated.

For example, when the information processing device 100 receives query information (hereinafter, also simply referred to as “query”) from the terminal device, the information processing device 100 searches for an object (vector information or the like) similar to the query and provides the search result to the terminal device. Further, for example, the data provided by the information processing apparatus 100 to the terminal apparatus may be the data itself such as image information, or the information for referring to the corresponding data such as a URL (Uniform Resource Locator). May be good. Further, the data to be queried or searched may be any kind of data such as image, voice, and text data. In the present embodiment, the case where the information processing apparatus 100 searches for an image will be described as an example.

[3. Information processing device configuration]
Next, the configuration of the information processing apparatus 100 according to the embodiment will be described with reference to FIG. FIG. 3 is a diagram showing a configuration example of the information processing apparatus 100 according to the embodiment. As shown in FIG. 3, the information processing apparatus 100 includes a communication unit 110, a storage unit 120, and a control unit 130. The information processing device 100 includes an input unit (for example, a keyboard, a mouse, etc.) that receives various operations from the administrator of the information processing device 100, and a display unit (for example, a liquid crystal display, etc.) for displaying various information. You may have.

(Communication unit 110)
The communication unit 110 is realized by, for example, a NIC (Network Interface Card) or the like. Then, the communication unit 110 is connected to the network (for example, the network N in FIG. 2) by wire or wirelessly, and transmits / receives information to / from 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 RAM (Random Access Memory) or a flash memory (Flash Memory), or a storage device such as a hard disk or an optical disk. As shown in FIG. 3, the storage unit 120 according to the embodiment includes an object information storage unit 121, a connection condition information storage unit 122, a change condition information storage unit 123, a graph data storage unit 124, and a starting information storage unit. It has a unit 125, a reconstruction condition information storage unit 126, and a reconstruction graph data storage unit 127.

(Object information storage unit 121)
The object information storage unit 121 according to the embodiment stores various information about the object. For example, the object information storage unit 121 stores object IDs and vector data. FIG. 4 is a diagram showing an example of an object information storage unit according to an embodiment. The object information storage unit 121 shown in FIG. 4 includes items such as “object ID” and “vector information”.

The "object ID" indicates identification information for identifying an object. Further, "vector information" indicates vector information corresponding to the object identified by the object ID. That is, in the example of FIG. 4, the vector data (vector information) corresponding to the object is associated and registered with the object ID that identifies the object.

For example, in the example of FIG. 4, it is shown that the object (object) identified by the ID “OB1” is associated with the multidimensional vector information of “10, 24, 51, 2, ...”.

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

(Consolidation condition information storage unit 122)
The connection condition information storage unit 122 according to the embodiment stores various information regarding connection conditions related to edge connection. FIG. 5 is a diagram showing an example of a connection condition information storage unit according to an embodiment. The connection condition information storage unit 122 shown in FIG. 5 includes items such as “connection condition ID”, “target”, “threshold value name”, and “value”.

"Concatenation condition ID" indicates information for identifying the concatenation condition regarding the concatenation of the directed edge. “Target” indicates the target of the concatenation condition identified by the concatenation condition ID. The "threshold name" indicates information (name) for identifying the threshold. Further, the “value” indicates a specific value of the corresponding threshold value.

In the example of FIG. 5, the connection condition (connection condition LCD1) identified by the connection condition ID “LCD1” indicates that the condition targets the input edge. Concatenation condition The condition used as LCD1 is an input threshold value, which indicates that the value is "ITH1". In the example shown in FIG. 5, the value of the "input threshold value" is shown as an abstract code such as "ITH1", but is assumed to be a specific numerical value such as "2" or "10".

Further, in the example of FIG. 5, it is shown that the connection condition (connection condition LCD2) identified by the connection condition ID “LCD2” is a condition for the output edge. The condition used as the connection condition LCD2 is an output threshold value, which indicates that the value is “OTH1”. In the example shown in FIG. 5, the value of the "output threshold value" is shown as an abstract code such as "OTH1", but is assumed to be a specific numerical value such as "1" or "20".

The connection condition information storage unit 122 is not limited to the above, and may store various information depending on the purpose.

(Change condition information storage unit 123)
The change condition information storage unit 123 according to the embodiment stores various information regarding the change condition regarding the change of the connection condition. FIG. 6 is a diagram showing an example of a change condition information storage unit according to an embodiment. The change condition information storage unit 123 shown in FIG. 6 has items such as "change condition ID", "determination information", and "change information".

The "change condition ID" indicates information for identifying the condition related to the change of the concatenation condition. The "decision information" stores information used for determining (determining) whether to change the connection condition. The "determination information" includes items such as "target information" and "threshold value". "Target information" indicates the target used in determining whether to change the consolidation condition. The "threshold value" indicates a threshold value used for determination. In the example shown in FIG. 6, the value of the “threshold value” is shown as an abstract code such as “NTH1”, but is concrete such as “100”, “5000”, “5%”, “0.2”, etc. Numerical value.

The "change information" stores information indicating the connection condition to be changed and the content of the change. The "change information" includes items such as "change target" and "change content". "Change target" indicates a consolidation condition to be changed when the corresponding condition is satisfied. Information (consolidation condition ID, etc.) that identifies the target concatenation condition is stored in the "change target". "Change content" indicates a specific content for changing the connection condition when the corresponding condition is satisfied. In the example shown in FIG. 6, the "change content" illustrates an abstract code such as "AINF11", but "+1", "5 increase", "2 decrease", "10% increase", and "5". It may be various changes such as "% decrease".

In the example of FIG. 6, the change condition (change condition ACD1) identified by the change condition ID “ACD1” indicates that the information regarding the number of additional nodes is used for the determination. The change condition ACD1 indicates that the threshold value is “NTH1”. Further, when the change condition ACD1 is satisfied, it is shown that the connection conditions to be changed are the connection condition LCD1 and the connection condition LCD2. When the change condition ACD1 is satisfied, it is shown that the connection condition LCD1 is changed according to the change content AINF11. For example, when the change content AINF11 is "2 increase", the information processing apparatus 100 increases the value of the input threshold value ITH1 of the connection condition LCD1 by 2 when it is determined that the change condition ACD1 is satisfied. Further, when the change condition ACD1 is satisfied, it is shown that the connection condition LCD2 is changed according to the change content AINF12. For example, when the change content AINF12 is "1 decrease", the information processing apparatus 100 reduces the value of the output threshold value OTH1 of the connection condition LCD2 by 1 when it is determined that the change condition ACD2 is satisfied.

The change condition information storage unit 123 is not limited to the above, and may store various information depending on the purpose.

(Graph data storage unit 124)
The graph data storage unit 124 according to the embodiment stores various information related to the graph data. For example, the graph data storage unit 124 stores the generated graph data. FIG. 7 is a diagram showing an example of a graph data storage unit according to an embodiment. The graph data storage unit 124 shown in FIG. 7 has items such as "node ID", "object ID", and "directed edge information". Further, the "directed edge information" includes information such as "edge ID" and "reference destination".

The "node ID" indicates identification information for identifying each node (target) in the graph data. Further, the "object ID" indicates identification information for identifying an object.

Further, "directed edge information" indicates information about the edge connected to the corresponding node. In the example of FIG. 7, “directed edge information” indicates information about the output edge output from the corresponding node. Further, the "edge ID" indicates identification information for identifying an edge connecting the nodes. Further, "reference destination" indicates information indicating a reference destination (node) connected by an edge. That is, in the example of FIG. 7, the reference destination (output edge) to which the information for identifying the object (target) corresponding to the node and the directed edge (output edge) from the node are concatenated with respect to the node ID for identifying the node. Node) is associated and registered.

In the example of FIG. 7, it is shown that the node (node N1) identified by the node ID “N1” corresponds to the object (target) identified by the object ID “OB1”. Further, from the node N1, it is shown that the edge (edge E1) identified by the edge ID “E1” is connected to the node (node N2) identified by the node ID “N2”. That is, in the example of FIG. 7, it is shown that the node N1 in the graph data can be traced to the node N2 by the edge E1. Further, from the node N1, it is shown that the edge (edge E3) identified by the edge ID “E3” is connected to the node (node N3) identified by the node ID “N3”. That is, in the example of FIG. 7, it is shown that the node N1 in the graph data can be traced to the node N3 by the edge E3.

The graph data storage unit 124 is not limited to the above, and may store various information depending on the purpose. For example, the graph data storage unit 124 may store the length of the edge connecting each node (vector). That is, the graph data storage unit 124 may store information indicating the distance between each node (vector). Further, for example, the graph data storage unit 124 may store information indicating the number of input edges to each node.

Further, the graph data may include a program module that takes a query as an input, searches for a node by tracing an edge in the graph data, and extracts and outputs a node similar to the query. That is, the graph data may be expected to be used as a program module that performs a search process using a graph. For example, the graph data GR 11 may be a program that extracts and outputs a node corresponding to the vector data similar to the vector data from the graph when the vector data is input as a query. For example, the graph data GR 11 may be data used as a program module for searching a similar image corresponding to a query image. For example, the graph data GR11 causes a computer to extract and output a node similar to the query in the graph based on the input query.

(Information storage unit 125 for starting point)
The starting point information storage unit 125 according to the embodiment stores various information related to the starting point information. FIG. 8 is a diagram showing an example of a starting point information storage unit according to an embodiment. Specifically, in the example of FIG. 8, the starting point information storage unit 125 shows the starting point index information of the tree structure. In the example of FIG. 8, the starting information storage unit 125 includes items such as “root layer”, “first layer”, “second layer”, and “third layer”. In addition, not limited to "first layer" to "third layer", "fourth layer", "fifth layer", "sixth layer" and the like may be included depending on the number of layers of the index.

The "root hierarchy" indicates a hierarchy of routes (top level) that is a starting point for determining a starting node using an index. The "first layer" stores information for identifying (identifying) a node (node or vector in graph information) belonging to the first layer of the index. The node stored in the "first layer" is a node corresponding to the layer directly connected to the root of the index.

The "second layer" stores information for identifying (identifying) a node (node or vector in graph information) belonging to the second layer of the index. The node stored in the "second layer" is a node corresponding to the immediately lower layer connected to the node of the first layer. The "third layer" stores information for identifying (identifying) a node (node or vector in graph information) belonging to the third layer of the index. The node stored in the "third layer" is a node corresponding to the immediately lower layer connected to the node of the second layer.

In the example shown in FIG. 8, the starting point information storage unit 125 stores information corresponding to the starting point information IND11 in FIG. 1. For example, the information storage unit 125 for the starting point indicates that the nodes in the first layer are nodes VT1 to VT3 and the like. The numerical values in parentheses below each node indicate the value of the vector corresponding to each node.

Further, the information storage unit 125 for the starting point indicates that the nodes in the second layer immediately below the node VT2 are the nodes VT2-1 to VT2-4. Further, the information storage unit 125 for the starting point indicates that the node in the third layer immediately below the node VT2-1 is the node (vector) in the graph GR11 of the node N1 and the node N2. The information storage unit 125 for the starting point indicates that the node in the third layer immediately below the node VT2-2 is the node (vector) in the graph GR11 of the node N3, the node N4, and the node N5.

The starting information storage unit 125 is not limited to the above, and may store various information depending on the purpose.

(Reconstruction condition information storage unit 126)
The reconstruction condition information storage unit 126 according to the embodiment stores various information regarding the reconstruction conditions regarding the conditions used for determining whether to reconstruct the graph for adjusting the edge. FIG. 9 is a diagram showing an example of the reconstruction condition information storage unit according to the embodiment. The reconstruction condition information storage unit 126 shown in FIG. 9 has items such as “reconstruction condition ID” and “determination information”.

The “reconstruction condition ID” indicates information for identifying a condition relating to the determination of execution of the graph reconstruction process. The "decision information" stores information used for determining (determining) whether to execute reconstruction. The "determination information" includes items such as "target information" and "threshold value". "Target information" indicates the target used to determine whether to perform the reconstruction. The "threshold value" indicates a threshold value used for determination. In the example shown in FIG. 9, the value of the "threshold value" is shown as an abstract code such as "NTH2", but is concrete such as "10%", "0.3", "500", "10000", etc. Numerical value.

In the example of FIG. 9, the reconstruction condition (reconstruction condition RCD1) identified by the reconstruction condition ID “RCD1” indicates that the information regarding the ratio of the additional node is used for the determination. The reconstruction condition RCD1 indicates that the threshold value is “NTH2”. That is, when the information processing apparatus 100 determines that the reconstruction condition RCD1 is satisfied, the information processing apparatus 100 executes the graph reconstruction process. When the reconstruction condition RCD1 is "10%", the information processing apparatus 100 executes the graph reconstruction process when the ratio of the additional nodes among the nodes in the graph reaches 10%.

The reconstruction condition information storage unit 126 is not limited to the above, and may store various information depending on the purpose.

(Reconstructed graph data storage unit 127)
The reconstructed graph data storage unit 127 according to the embodiment stores various information regarding the reconstructed graph data. FIG. 10 is a diagram showing an example of the reconstructed graph data storage unit according to the embodiment. In the example of FIG. 10, the reconstructed graph data storage unit 127 has items such as “node ID”, “object ID”, and “directed edge information”. Further, the "directed edge information" includes information such as "edge ID" and "reference destination".

The "node ID" indicates identification information for identifying each node (target) in the graph data. Further, the "object ID" indicates identification information for identifying an object.

Further, "directed edge information" indicates information about the edge connected to the corresponding node. In the example of FIG. 10, "directed edge information" indicates information about the output edge output from the corresponding node. Further, the "edge ID" indicates identification information for identifying an edge connecting the nodes. Further, "reference destination" indicates information indicating a reference destination (node) connected by an edge. That is, in the example of FIG. 10, the reference destination (output edge) to which the information for identifying the object (target) corresponding to the node and the directed edge (output edge) from the node are concatenated with respect to the node ID for identifying the node. Node) is associated and registered.

In the example of FIG. 10, it is shown that the node (node N1) identified by the node ID “N1” corresponds to the object (target) identified by the object ID “OB1”. Further, from the node N1, it is shown that the edge (edge E1) identified by the edge ID “E1” is connected to the node (node N2) identified by the node ID “N2”. That is, in the example of FIG. 10, it is shown that the node N1 in the graph data can be traced to the node N2 by the edge E1. Further, from the node N1, it is shown that the edge (edge E13) identified by the edge ID “E13” is connected to the node (node N6) identified by the node ID “N6”. That is, in the example of FIG. 10, it is shown that the node N1 in the graph data can be traced to the node N6 by the edge E13.

The reconstructed graph data storage unit 127 is not limited to the above, and may store various information depending on the purpose. For example, the reconstruction graph data storage unit 127 may store the length of the edge connecting each node (vector). That is, the reconstruction graph data storage unit 127 may store information indicating the distance between each node (vector). Further, for example, the reconstruction graph data storage unit 127 may store information indicating the number of input edges to each node.

Further, FIG. 10 illustrates a case where the graph data after reconstruction is stored in the reconstruction graph data storage unit 127, but the graph data after the reconstruction is completed is stored in the graph data storage unit 124. For example, the information processing apparatus 100 stores the graph data in the process of reconstruction in the reconstruction graph data storage unit 127, and after the reconstruction is completed, updates the graph data storage unit 124 with the graph data after the reconstruction is completed. .. For example, the information processing apparatus 100 updates the graph data storage unit 124 by storing the graph data stored in the reconstruction graph data storage unit 127 in the graph data storage unit 124 after the reconstruction is completed. The above is an example, and the graph data storage unit 124 may be updated by any method as long as the reconstructed graph data is stored in the graph data storage unit 124.

(Control unit 130)
Returning to the description of FIG. 3, the control unit 130 is a controller, and is inside the information processing device 100 by, for example, a CPU (Central Processing Unit), an MPU (Micro Processing Unit), a GPU (Graphics Processing Unit), or the like. Various programs (corresponding to an example of an information processing program) stored in the storage device of the above are realized by executing the RAM as a work area. Further, the control unit 130 is a controller, and is realized by, for example, an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array).

As shown in FIG. 3, the control unit 130 includes an acquisition unit 131, a selection unit 132, a determination unit 133, a generation unit 134, a search unit 135, and a provision unit 136, and information described below. Realize or execute the function or action of processing. The internal configuration of the control unit 130 is not limited to the configuration shown in FIG. 3, and may be any other configuration as long as it is configured to perform information processing described later.

(Acquisition unit 131)
The acquisition unit 131 acquires various types of information. For example, the acquisition unit 131 acquires various information from the storage unit 120. For example, the acquisition unit 131 includes an object information storage unit 121, a connection condition information storage unit 122, a change condition information storage unit 123, a graph data storage unit 124, a starting point information storage unit 125, and a reconstruction condition information storage unit. Various information is acquired from the unit 126, the reconstructed graph data storage unit 127, and the like. Further, the acquisition unit 131 acquires various information from an external information processing device.

The acquisition unit 131 obtains one object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a first graph including a directed edge connecting the nodes. get.

The acquisition unit 131 acquires a newly added object (newly added object). For example, the information processing device 100 may acquire a newly added object (newly added object) from an external device such as the information providing device 50. The acquisition unit 131 may acquire information as object information in which the information for identifying the newly added object (object ID) and the vector generated from the newly added object are associated with each other. In this case, the acquisition unit 131 may store the acquired object information in the object information storage unit 121. Then, when the newly added object is acquired, the acquisition unit 131 makes a node corresponding to the newly added object.

Further, the acquisition unit 131 may acquire graph data. For example, the information processing apparatus 100 may acquire the graph GR11-1 in FIG. For example, the information processing device 100 may acquire graph data from an external device such as the information providing device 50.

For example, the acquisition unit 131 acquires information about the search query. 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 to be used. For example, the acquisition unit 131 acquires a query from the information providing device 50 that has received the query from the terminal device 10 to be used.

(Selection unit 132)
The selection unit 132 selects various types of information. The selection unit 132 extracts various information. The selection unit 132 selects various information based on the various information stored in the storage unit 120. The selection unit 132 extracts various information based on the various information stored in the storage unit 120.

The selection unit 132 selects a neighboring node located in the vicinity of one node corresponding to one object among a plurality of nodes based on the first graph. The selection unit 132 selects a node in the vicinity of the number of input threshold values or output threshold values (selection number). When the input threshold value is equal to or higher than the output threshold value, the selection unit 132 selects nodes in the vicinity of the selection number, using the number of input threshold values as the selection number. When the output threshold value is larger than the input threshold value, the selection unit 132 selects nodes in the vicinity of the selection number by using the number of output threshold values as the selection number.

The selection unit 132 selects nearby nodes by searching the first graph. The selection unit 132 selects the neighboring nodes of the selected number by searching the first graph using the additional node as a query. The selection unit 132 selects nearby nodes by searching the first graph by the search process as shown in FIG.

The selection unit 132 selects neighboring nodes corresponding to each node included in the provisional graph by searching the provisional graph. The selection unit 132 selects the neighboring nodes of the selected number by searching the provisional graph. The selection unit 132 selects nearby nodes by searching the provisional graph by the search process as shown in FIG.

The selection unit 132 may cause the search unit 135 to search for information by requesting the search unit 135, and may use the search result searched by the search unit 135. The selection unit 132 may select information from the search results searched by the search unit 135. The selection unit 132 selects the neighboring node corresponding to each node included in the second graph by referring to the information regarding the neighboring node of each node included in the second graph.

In the example of FIG. 1, the selection unit 132 selects a node in the vicinity of the selected number by searching the graph by the processing procedure as shown in FIG. The selection unit 132 searches the graph GR11-1 by the processing procedure as shown in FIG. 16, and selects two nodes N1 and N2 corresponding to the selection number “2” as the neighboring nodes of the node N3. The selection unit 132 searches the graph GR11-2 by the processing procedure as shown in FIG. 16, and selects two nodes N1 and N3 corresponding to the selection number “2” as the neighboring nodes of the node N4. The selection unit 132 searches the graph GR11-3 by the processing procedure as shown in FIG. 16, and selects three nodes N1, N4, and N5 corresponding to the selection number “3” as the neighboring nodes of the node N11.

(Decision unit 133)
The determination unit 133 determines various information. The determination unit 133 determines various information. The determination unit 133 changes various information. The determination unit 133 updates various information. The determination unit 133 determines various information based on the various information stored in the storage unit 120. The determination unit 133 determines various information based on the various information stored in the storage unit 120. The determination unit 133 changes various information based on the various information stored in the storage unit 120. The determination unit 133 updates various information.

The determination unit 133 determines whether to change the connection condition based on the change condition regarding the connection condition which is a predetermined condition. The determination unit 133 determines whether to change the connection condition based on the change condition regarding the number of a plurality of nodes in the first graph. The determination unit 133 determines whether to change the connection condition when the number of the plurality of nodes in the first graph is equal to or greater than a predetermined threshold value. The determination unit 133 compares the number of a plurality of nodes in the first graph with a predetermined threshold value, and dynamically changes the connection condition according to the result.

The determination unit 133 determines whether to change the connection condition based on the change condition regarding the ratio of the additional nodes that are the nodes added after a predetermined time point among the plurality of nodes in the first graph. The determination unit 133 determines whether to change the connection condition based on the change condition regarding the ratio of the additional nodes added after the adjustment process of the directed edge among the plurality of nodes in the first graph.

The determination unit 133 determines whether to change the connection condition when the ratio of the additional nodes among the plurality of nodes in the first graph is equal to or higher than a predetermined threshold value. The determination unit 133 compares the ratio of the additional nodes in the first graph with a predetermined threshold value, and dynamically changes the connection condition according to the result. The determination unit 133 determines whether to change the connection condition based on the change condition regarding the number of directed edges in the first graph. The determination unit 133 determines whether to change the connection condition based on the change condition regarding the statistical information of the directed edge in the first graph.

The determination unit 133 changes the edge number condition regarding the number of directed edges in the connection condition based on the change condition. The determination unit 133 increases the number of connected edges specified in the edge number condition as the number of the plurality of nodes in the first graph increases. The determination unit 133 reduces the number of connected edges specified in the edge number condition when it is estimated that the specified generation time is exceeded.

The determination unit 133 changes the edge number condition including the output number condition regarding the number of output edges starting from one node and ending at the other node. The determination unit 133 changes the edge number condition including the input number condition regarding the number of input edges starting from another node and ending at one node.

In the example of FIG. 1, the determination unit 133 determines the input threshold value “2” as the selection number. The determination unit 133 determines the origin node using the origin information corresponding to the graph being generated. Further, the determination unit 133 updates the number of selections according to the change of the connection condition. The determination unit 133 determines the input threshold value "3" as the number of selections. The determination unit 133 determines the output threshold value “6” as the number of selections. The determination unit 133 updates the number of selections from "3" to "6".

(Generation unit 134)
The generation unit 134 generates various information. For example, the generation unit 134 generates various information (data) from the information (data) stored in the storage unit 120. For example, the generation unit 134 may include an object information storage unit 121, a connection condition information storage unit 122, a change condition information storage unit 123, a graph data storage unit 124, a starting point information storage unit 125, and a reconstruction condition information storage unit. Various information is generated from the unit 126, the reconstructed graph data storage unit 127, and the like. For example, the generation unit 134 generates the first graph data from the graph data. For example, the generation unit 134 generates the second graph data by adding the newly added node to the first graph data.

The generation unit 134 adds one node to the first graph and connects one node and a neighboring node by the directed edge based on the connection condition regarding the connection of the directed edge changed by a predetermined condition. Generate the second graph. When the determination unit 133 determines that the connection condition is changed, the generation unit 134 generates a second graph in which one node and a neighboring node are connected by a directed edge based on the changed connection condition. ..

The generation unit 134 generates a second graph in which one node and a neighboring node are connected by a directed edge based on the changed edge number condition. The generation unit 134 generates a second graph in which one node and neighboring nodes are connected by directed edges based on the number of connected edges after the increase. The generation unit 134 generates a second graph in which one node and neighboring nodes are connected by directed edges based on the number of connected edges after the decrease.

Based on the changed output number condition, the generation unit 134 generates a second graph in which the output edges starting from one node are connected to the number of output destination nodes corresponding to the output number condition among the neighboring nodes. do. Based on the changed edge number condition, the generation unit 134 generates a second graph in which the input source nodes corresponding to the input number condition among the neighboring nodes are connected to the input edges having one node as the end point. do.

The generation unit 134 generates the third graph by updating the directed edge in the second graph. The generation unit 134 generates the third graph when the second graph satisfies a predetermined condition regarding the reconstruction of the graph. The generation unit 134 generates a provisional graph by adding an inverted edge obtained by inverting the directed edge of the second graph, and generates a third graph by using the generated provisional graph. The generation unit 134 generates a third graph in which each node and a neighboring node are connected by a directed edge based on the connection condition. The generation unit 134 generates the third graph by using the information about the neighboring nodes of each node included in the second graph.

When the newly added object is acquired by the acquisition unit 131, the generation unit 134 may generate a vector corresponding to the newly added object. In this case, the generation unit 134 may associate the generated vector with the object and store it in the object information storage unit 121.

In the example of FIG. 1, since the node N1 is the first node, the generation unit 134 newly generates the graph GR11 including the node N1. The generation unit 134 generates a graph so that two input edges and one output edge are connected to the added node N2 based on the connection condition list LCL1. The generation unit 134 generates the graph GR11-1 by adding an edge connected to the added node N2.

The generation unit 134 generates the determination information list DFI1 based on the graph GR11-1. The generation unit 134 generates a graph GR11-2 in which two input edges E3, E5 and one output edge E4 are connected to the added node N3.

The generation unit 134 generates the determination information list DFI2 based on the graph GR11-2. The generation unit 134 generates a graph GR11-3 in which two input edges E6 and E7 and one output edge E8 are connected to the added node N4. The generation unit 134 also generates the graph GR11-3 by sequentially adding the 96 nodes such as the node N5 to the graph GR11 in the same manner as the node N4.

The generation unit 134 generates the determination information list DFI3 based on the graph GR11-3. The generation unit 134 generates a graph GR11-4 in which three input edges E13 and E14 and one output edge E12 are connected to the added node N11. The generation unit 134 generates the connection condition list LCL2 based on the change contents in the change condition list ACL1.

The generation unit 134 generates the determination information list DFI4 based on the graph GR11-4. The generation unit 134 generates the connection condition list LCL3 based on the change contents in the change condition list ACL2.

(Search unit 135)
The search unit 135 provides a search service for objects. The search unit 135 searches for various information. The search unit 135 searches for various types of information. For example, the search unit 135 searches for an object by searching for graph data. For example, when the query acquired by the acquisition unit 131 is acquired, the search unit 135 searches for an object similar to the query by searching the graph data. For example, the search unit 135 extracts an object similar to a query by searching the graph data. For example, the search unit 135 extracts an object similar to a query by searching the graph data based on the processing procedure as shown in FIG. If the search unit 135 does not provide the search service, the search unit 135 may not have the search unit 135.

(Providing Department 136)
The providing unit 136 provides various information. For example, the providing unit 136 provides various information to the terminal device 10 and the information providing device 50. For example, the providing unit 136 provides the object ID corresponding to the query as a search result. For example, the providing unit 136 provides the object ID searched by the searching unit 135 to the information providing device 50. For example, the providing unit 136 provides the object ID extracted by the search unit 135 to the information providing device 50. The providing unit 136 provides the information providing device 50 with the object ID extracted by the searching unit 135 as information indicating a vector corresponding to the query.

Further, the providing unit 136 may provide the second graph data generated by the generating unit 134 to an external information processing device. For example, the providing unit 136 may transmit the graph GR 11 generated by the generating unit 134 to the information providing device 50.

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

As shown in FIG. 11, the information processing apparatus 100 acquires one object (step S101). For example, the information processing apparatus 100 acquires object information newly added to the graph from the information providing apparatus 50.

Then, the information processing apparatus 100 acquires the first graph (step S102). For example, the information processing apparatus 100 acquires the graph stored in the graph data storage unit 124 (see FIG. 7) as the first graph.

Then, the information processing apparatus 100 selects a node in the vicinity of one node corresponding to one object from the plurality of nodes based on the first graph (step S103). For example, the information processing apparatus 100 selects a neighboring node by searching the first graph using one node to be added as a query.

Then, the information processing apparatus 100 adds one node to the first graph (step S104). Then, the information processing apparatus 100 generates a second graph in which one node and a neighboring node are connected by the directed edge based on the connection condition regarding the connection of the directed edge (step S105).

Next, the procedure of information processing by the information processing system 1 according to the embodiment will be described with reference to FIG. FIG. 12 is a flowchart showing an example of the condition change process according to the embodiment. For example, the condition change process shown in FIG. 12 may be performed before step S101 in FIG. 11 or after step S105.

As shown in FIG. 12, the information processing apparatus 100 determines whether or not the change condition is satisfied (step S201). When the information processing apparatus 100 determines that the change condition is satisfied (step S201: Yes), the information processing apparatus 100 changes the connection condition based on the change condition (step S202).

When the information processing apparatus 100 determines that the change condition is not satisfied (step S201: No), the information processing apparatus 100 ends the process without changing the connection condition.

[5. Example of reconstruction process]
In the example of FIG. 1, the process of connecting an edge to an additional node is repeated every time a node is added, but as the number of additional nodes increases, the edge connection process becomes uneven, for example, the edge adjustment process. May be required. In such a case, it is difficult to eliminate the variation in the edge connection by simply adding the connection edge to the new additional node while maintaining the connected edge. Therefore, when the edge adjustment process is required, the information processing apparatus 100 executes a reconstruction process of reconnecting the edges of each node in the graph. For example, when the graph satisfies the reconstruction condition, the information processing apparatus 100 executes a reconstruction process for reconnecting the edges of the graph. The point of this reconstruction process will be described with reference to FIG. FIG. 13 is a diagram showing an example of a graph reconstruction process according to an embodiment. The same points as in FIG. 1 will be omitted as appropriate. Further, the spatial information VS1-21 to VS1-24 shown in FIG. 13 are diagrams schematically showing the generation process of graph data, and the spaces shown in the spatial information VS1-21 to VS1-24 are the same space. You may. Further, when the spatial information VS1-21 to VS1-24 are described without particular distinction, they are described as spatial information VS1.

In the example of FIG. 13, the information processing apparatus 100 generates graph GR11-21 including 9999 nodes such as nodes N1 to N5. For example, the information processing apparatus 100 uses a graph (initial graph) including 9900 nodes such as nodes N1 to N5, adds 99 additional nodes to the initial graph, and generates graph GR11-21. Show the case. In the example of FIG. 13, the information processing apparatus 100 determines the input threshold value “2” of the connection condition list LCL1 as the number of selections.

Further, the information processing apparatus 100 generates the determination information list DFI21 based on the graph GR11-21. The information processing apparatus 100 generates a determination information list DFI21 indicating that the number of nodes included in the graph GR11-21 is 9999 and the number of additional nodes included in the graph GR11-21 is 99. For example, the information processing apparatus 100 may store the determination information list DFI 21 in the storage unit 120 (see FIG. 3).

Then, the information processing apparatus 100 determines whether or not the graph GR11-21 satisfies the reconstruction condition. For example, in the information processing apparatus 100, since the number of nodes included in the graph GR11-21 is 9999 and the number of additional nodes is 99, the ratio of additional nodes is calculated as "0.0099 (= 99/9999)". do. Since the information processing apparatus 100 has an additional node ratio of "0.0099" in the graph GR11-21, the information processing apparatus 100 satisfies the reconstruction condition that the threshold value of the additional node ratio shown in the reconstruction condition list RCL21 is "0.1" or more. It is determined that there is no such thing. Therefore, the information processing apparatus 100 continues the processing without executing the reconstruction processing.

Then, the information processing apparatus 100 newly adds the node N6 (step S21-1). For example, the information processing apparatus 100 adds the node N6 to the graph GR11-21.

Then, the information processing apparatus 100 searches for the graph (step S21-2). In the example of FIG. 13, the information processing apparatus 100 searches the graph GR11-21 using the added node N6 as a query. The information processing apparatus 100 searches the graph GR11-21 by the processing procedure as shown in FIG. 16, and selects two nodes N1 and N3 corresponding to the selection number "2" as the neighboring nodes of the node N6. Further, in the example of FIG. 13, the node N1 is located closest to the node N6. For example, the information processing apparatus 100 determines the node N1 as the starting node among the 9999 nodes including the nodes N1 to N5 of the graph GR11-21 by using the starting point information of the tree structure as shown in FIG. You may.

Then, the information processing apparatus 100 generates the second graph by adding the directed edge connecting the node and the neighboring node to the first graph based on the connection condition (step S21-3). In the example of FIG. 13, the information processing apparatus 100 has a graph GR11-21 which is the first graph of the directed edge connecting the node N6 and the neighboring nodes N1 and N3 based on the connection condition list LCL1. By adding to, the graph GR11-22, which is the second graph, is generated. Specifically, the information processing apparatus 100 generates the graph GR11-22 so that two input edges and one output edge are connected to the node N6 based on the connection condition list LCL1.

The information processing apparatus 100 connects the input edges to the node N6 to the two selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E13 to be input to the node N6 to the node N1 having the shortest distance among the selected neighboring nodes N1 and N3. As a result, the information processing apparatus 100 connects the node N1 and the node N6, which are nodes in the vicinity of the node N6.

The information processing apparatus 100 connects the edge E14 to be input to the node N6 to the node N3 having the second shortest distance among the selected neighboring nodes N1 and N3. As a result, the information processing apparatus 100 connects the node N3 and the node N6, which are nodes in the vicinity of the node N6. In the graph GR11-22 in FIG. 13, the reference numerals are omitted for the edges shown in the graph GR11-21 due to space limitations, and when the edges in both directions are connected, they are shown by double-headed arrows. For example, a bidirectional arrow connecting node N3 and node N4 in the graph GR11-22 indicates that node N3 and node N4 are connected by edges E7 and E8.

Further, the information processing apparatus 100 connects the output edge from the node N6 to one of the selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E12 output from the node N6 to the node N1 having the shortest distance among the selected neighboring nodes N1 and N3. As a result, the information processing apparatus 100 connects the node N6 and the node N1 which is a node in the vicinity thereof. As a result, the information processing apparatus 100 generates a graph GR11-22 in which two input edges E13 and E14 and one output edge E12 are connected to the added node N6. As described above, since one node N6 is added to the graph GR11-22, the number of nodes of the graph GR11-22 becomes 10,000 (= 9999 + 1), and the number of additional nodes included in the graph GR11-22. Is 100 (= 99 + 1).

Further, the information processing apparatus 100 generates a determination information list DFI22 based on the graph GR11-22. For example, the information processing apparatus 100 generates the decision information list DFI 22 by updating the decision information list DFI 21. The information processing apparatus 100 generates a determination information list DFI21 indicating that the number of nodes included in the graph GR11-22 is 10,000 and the number of additional nodes included in the graph GR11-22 is 100. For example, the information processing apparatus 100 may update the determination information list DFI 21 stored in the storage unit 120 (see FIG. 3) to the determination information list DFI 22.

Then, the information processing apparatus 100 determines whether or not the graph GR 11-22 satisfies the reconstruction condition. For example, in the information processing apparatus 100, since the number of nodes included in the graph GR11-22 is 10,000 and the number of additional nodes is 100, the ratio of additional nodes is calculated as "0.01 (= 100/10000)". do. Since the information processing apparatus 100 has the additional node ratio of the graph GR 11-22 of "0.01", the information processing apparatus 100 satisfies the reconstruction condition that the threshold value of the additional node ratio shown in the reconstruction condition list RCL21 is "0.1" or more. Is determined. As described above, the information processing apparatus 100 determines that the graph GR 11-22 satisfies the reconstruction condition (step S21-4). Therefore, the information processing apparatus 100 determines to execute the reconstruction process. The information processing apparatus 100 determines that the graph GR11-22, which is the second graph, generates a third graph (also referred to as a “reconstruction graph”) because the graph GR 11-22 satisfies a predetermined condition regarding the reconstruction of the graph.

Therefore, the information processing apparatus 100 adds an inverted edge to the graph (step S22). The information processing apparatus 100 adds an inverted edge to the graph GR11-22, which is the second graph to which the node N6 is added. For each node of the graph GR 11-22, the information processing apparatus 100 connects the other edge between the nodes when only one edge is connected to the other node. That is, the information processing apparatus 100 adds an edge (inverted edge) in which one edge is inverted between the nodes connected by only one edge.

In the example of FIG. 13, the information processing apparatus 100 connects the node N1 and the node N4 by the inverted edge E15 of the edge E6 from the node N1 to the node N4. That is, the information processing apparatus 100 connects the edge E15, which is an output edge starting from the node N4, to the node N1. Further, the information processing apparatus 100 adds an edge E16 in which the edge E5 is inverted between the node N2 and the node N3 connected by one edge E5. Further, the information processing apparatus 100 adds an edge E17 in which the edge E10 is inverted between the node N4 and the node N5 connected by one edge E10. Further, the information processing apparatus 100 adds an edge E18 in which the edge E14 is inverted between the node N3 and the node N6 connected by one edge E14. In this way, the information processing apparatus 100 adds an edge in which one edge is inverted between the nodes connected by only one edge, so that each node based on the virtual K nearest neighborhood graph is added. Generates the data GR20 of the neighboring node of (referred to as "neighboring node data GR20").

That is, the information processing apparatus 100 adds an inverted edge to the graph, so that the nodes connected by at least one node in the graph GR11-22 are connected in both directions to form a virtual K nearest neighborhood graph. Generates neighborhood node data GR20 based on. The neighborhood node data GR20 in FIG. 13 is shown in the state of a graph, but is an image for facilitating understanding, and the neighborhood node data GR20 is assumed to be data (information) about the neighborhood nodes of each node. .. For example, the neighborhood node data GR20 may be list information of the distance between each node in the graph GR11-22 and the node to which the output edge is connected and the node. For example, in the neighborhood node data GR20, information in which the neighborhood node candidate to which the output edge from a certain target node is connected and the distance between the neighborhood node candidate and the target node are associated with each other (hereinafter, “neighborhood node candidate”). Information ") is included. For example, in the neighborhood node data GR20, the distance between the neighboring node candidates such as the nodes N2, N3, N4, N5, N6 to which the output edge from the node N1 is connected to the node N1 and the node is associated with the node N1. The information provided may be included. Further, for example, in the neighborhood node data GR20, the neighborhood node in which the distance between the neighborhood node candidate such as the nodes N1 and N3 to which the output edge from the node N2 is connected and the node is associated with the node N2 is associated with the node N2. Candidate information may be included. The information processing apparatus 100 may use any information, not limited to the neighboring node data GR20, as long as the neighboring nodes of the individual nodes can be selected. For example, the information processing apparatus 100 may select the neighboring nodes of each node included in the reconstructed graph GR21 based on the graph GR11 without using the neighboring node data GR20, but this point will be described later.

Then, the information processing apparatus 100 executes the graph reconstruction process and generates the reconstruction graph (step S23). The information processing apparatus 100 provides a graph GR21 (reconstruction graph GR21) which is a reconstruction graph in which 10,000 nodes including the nodes N1 to N6 included in the graph GR11 are connected by an edge based on the connection condition list LCL1. Generate. In the example of FIG. 13, the information processing apparatus 100 determines the input threshold value “2” of the connection condition list LCL1 as the number of selections.

For example, the information processing apparatus 100 generates the reconstructed graph GR21 by performing processing in order from the node N1. First, the information processing apparatus 100 generates a reconstruction graph GR21 including 10000 nodes including nodes N1 to N6 and the like and does not include edges. For example, the information processing apparatus 100 generates a reconstructed graph GR21 including 10000 nodes including N1 to N6 and the like and not including an edge by copying only the nodes among the information contained in the graph GR11. Then, the information processing apparatus 100 generates the reconstruction graph GR21 by sequentially adding edges to the nodes in the reconstruction graph GR21 with the reconstruction graph GR21 not including the edge as the initial state. In the example of FIG. 13, for the sake of simplicity, the case of processing with the same node ID as the node in the graph GR11 and the node of the reconstructed graph GR21 is shown, but the node in the graph GR11 and the reconstructed graph GR21 are shown. As long as it is associated with the node of, it may be managed by any node ID. For example, the node N1 in the graph GR11 is a node N1-1 (that is, the node ID “N1-1”) in the reconstructed graph GR21, and the information in which the node N1 and the node N1-1 are associated is stored in the storage unit 120. (See FIG. 3).

Further, the information processing apparatus 100 may refer to the neighborhood node data GR20 and select a neighborhood node from the nodes to which the output edges from the target node (target node) of the edge connection processing are connected. In the neighborhood node data GR20, the information processing apparatus 100 may select a selection number of nodes as the neighborhood node from the node to which the output edges from the target node are connected, from the one having the shortest distance. Further, the information processing apparatus 100 may select a node in the reconstruction graph GR21 corresponding to the neighboring node selected in the neighborhood node data GR20 as the neighborhood node. Further, the information processing apparatus 100 may select a neighboring node by searching the graph when generating the reconstructed graph GR21. For example, the information processing apparatus 100 may select a neighboring node by searching the graph GR 11 when generating the reconstructed graph GR 21. In this case, the information processing apparatus 100 does not have to generate the neighborhood node data GR20 or the virtual K-nearest neighbor graph.

For example, when the information processing apparatus 100 connects edges with the node N1 as the target node (target node), the information processing apparatus 100 refers to the information of the neighborhood node candidate to which the output edge from the node N1 is connected in the neighborhood node data GR20. .. The information processing apparatus 100 refers to the neighborhood node candidate of the node N1 included in the neighborhood node data GR20, and selects two nodes N2 and N6 corresponding to the selection number "2" as the neighborhood node of the node N1. For example, the information processing apparatus 100 compares the distances of the neighboring node candidates of the node N1 included in the neighboring node data GR20, and selects the neighboring nodes of the node N1 in order from the shortest distance. In the example of FIG. 13, the information processing apparatus 100 selects two nodes, the node N6 having the shortest distance from the node N1 and the node N2 having the shortest distance from the node N1, among the neighboring node candidates of the node N1 in the reconstruction graph GR21. Select as a node near node N1 of.

Then, the information processing apparatus 100 adds a directed edge connecting the target node and the neighboring node to the reconstruction graph GR 21 based on the connection condition. In the example of FIG. 13, the information processing apparatus 100 reconstructs a directed edge connecting the node N1 in the reconstruction graph GR21 and the neighboring nodes N2 and N6 based on the connection condition list LCL1. Add to GR21. Specifically, the information processing apparatus 100 sets the reconstruction graph GR21 so that two input edges and one output edge are connected to the node N1 in the reconstruction graph GR21 based on the connection condition list LCL1. Generate (update).

The information processing apparatus 100 connects the input edges to the node N1 to the two selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E12 to be input to the node N1 to the node N6 having the shortest distance in the reconstruction graph GR21 among the selected neighboring nodes N2 and N6. Further, the information processing apparatus 100 connects the edge E2 to be input to the node N1 to the node N2 having the second shortest distance in the reconstruction graph GR21 among the selected neighboring nodes N2 and N6.

Further, the information processing apparatus 100 connects the output edge from the node N1 to one of the selected neighboring nodes in order from the one having the shortest distance. The information processing apparatus 100 connects the edge E13 output from the node N1 to the node N6 having the shortest distance in the reconstruction graph GR21 among the selected neighboring nodes N2 and N6.

Then, the information processing apparatus 100 generates the reconstructed graph GR21 by similarly performing a process of adding a connecting edge to the remaining 9999 nodes including the nodes N2 to N6 and the like. The information processing apparatus 100 may use the generated reconstruction graph GR21 as the first graph to perform a process of newly adding an object (node) as shown in FIG. For example, the information processing apparatus 100 may generate a second graph by using the generated reconstruction graph GR21 as the first graph and adding an additional node corresponding to the added object to the reconstruction graph GR21.

As described above, when the graph satisfies the reconstruction condition, the information processing apparatus 100 can adjust the edge balance at an appropriate timing by generating the reconstruction graph, so that the graph used for the search can be used. Can be generated appropriately. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

[6. Reconstruction process flow]
Next, with reference to FIG. 14, a procedure for graph reconstruction processing by the information processing system 1 according to the embodiment will be described. FIG. 14 is a flowchart showing an example of the graph reconstruction process according to the embodiment.

As shown in FIG. 14, the information processing apparatus 100 determines whether or not the reconstruction condition is satisfied (step S501). When the information processing apparatus 100 determines that the reconstruction condition is not satisfied (step S501: No), the information processing apparatus 100 ends the process without performing the reconstruction process.

When the information processing apparatus 100 determines that the reconstruction condition is satisfied (step S501: Yes), the information processing apparatus 100 refers to the information regarding the neighboring nodes of each node included in the second graph, whereby the node included in the second graph is referred to. Select the corresponding neighbor node (step S502). Then, the information processing apparatus 100 generates a third graph in which each node and neighboring nodes are connected by the directed edge based on the connection condition regarding the connection of the directed edge (step S503).

[7. Search example]
Here, an example of the search using the graph data described above is shown. The search using the generated graph data is not limited to the following, and may be performed by various procedures. This point will be described with reference to FIG. 16 as an example. FIG. 16 is a flowchart showing an example of a search process using graph data. The search process described below is performed by the search unit 135 of the information processing apparatus 100. In addition, the objects referred to below may be read as nodes. In the following, the information processing device 100 (selection unit 132 and search unit 135) performs a search process. If the search service is not provided, the information processing apparatus 100 does not have to have the search unit 135. The search query of the process described below may be an additional node, a target node, an object specified by the user, or the like.

Here, the neighborhood object set N (G, y) is a set of neighborhood objects associated with the edge assigned to the node y. “G” may be predetermined graph data (for example, the second graph GR12 or the like). For example, the information processing apparatus 100 executes the k-nearest neighbor search process.

For example, the information processing apparatus 100 sets the radius r of the hypersphere to ∞ (infinity) (step S300), and extracts the subset S from the existing object set (step S301). For example, the information processing apparatus 100 may extract an object (node) selected as a root node as a subset S. Further, for example, a hypersphere is a virtual sphere indicating a search range. 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 results at the same time.

Next, the information processing apparatus 100 extracts the object having the shortest distance from the object y from the objects included in the object set S, where y is the search query object, and sets it as the object s (step S302). For example, in the information processing apparatus 100, when only the object (node) selected as the root node is an element of S, the root node is extracted as the object s as a result. Next, the information processing apparatus 100 excludes the objects s from the object set S (step S303).

Next, the information processing apparatus 100 determines whether or not the distance d (s, y) between the object s and the object y exceeds r (1 + ε) (step S304). Here, ε is an extension element, and r (1 + ε) is a value indicating the radius of the search range (searching only the nodes within this range. The accuracy can be improved by making it larger than the search range). be. When the distance d (s, y) between the object s and the object y exceeds r (1 + ε) (step S304: Yes), the information processing apparatus 100 outputs the object set R as a neighborhood object set of the object y (step). S305), the process is terminated.

When the distance d (s, y) between the object s and the search query object y does not exceed r (1 + ε) (step S304: No), the information processing apparatus 100 determines the neighborhood object set N (G, s) of the objects s. One object not included in the object set C is selected from the objects that are the elements of the above, and the selected object u is stored in the object set C (step S306). The object set C is provided for convenience in order to avoid duplicate search, and is set to an empty set at the start of processing.

Next, the information processing apparatus 100 determines whether or not the distance d (u, y) between the object u and the object y is r (1 + ε) or less (step S307). When the distance d (u, y) between the object u and the object y is r (1 + ε) or less (step S307: Yes), the information processing apparatus 100 adds the object u to the object set S (step S308). Further, when the distance d (u, y) between the object u and the object y is not r (1 + ε) or less (step S307: No), the information processing apparatus 100 determines (processes) step S309.

Next, the information processing apparatus 100 determines whether or not the distance d (u, y) between the object u and the object y is r or less (step S309). When the distance d (u, y) between the object u and the object y exceeds r, the information processing apparatus 100 performs the determination (processing) in step S315. Further, when the distance d (u, y) between the object u and the object y is not r or less (step S309: No), the information processing apparatus 100 determines (processes) in step S315.

When the distance d (u, y) between the object u and the object y is r or less (step S309: Yes), the information processing apparatus 100 adds the object u to the object set R (step S310). Then, the information processing apparatus 100 determines whether or not the number of objects included in the object set R exceeds ks (step S311). The predetermined number ks is an arbitrarily determined natural number. For example, ks may be a selection number. For example, ks = 2 may be set. When the number of objects included in the object set R does not exceed ks (step S311: No), the information processing apparatus 100 determines (processes) step S313.

When the number of objects included in the object set R exceeds ks (step S311: Yes), the information processing apparatus 100 selects the object having the longest distance (far) from the object y among the objects included in the object set R. Exclude from the object set R (step S312).

Next, the information processing apparatus 100 determines whether or not the number of objects included in the object set R matches ks (step S313). When the number of objects included in the object set R does not match ks (step S313: No), the information processing apparatus 100 determines (processes) step S315. Further, when the number of objects included in the object set R matches ks (step S313: Yes), the information processing apparatus 100 has the longest distance (far) from the object y among the objects included in the object set R. The distance between the object and the object y is set to a new r (step S314).

Then, the information processing apparatus 100 selects all the objects from the objects that are the elements of the object set N (G, s) in the vicinity of the objects s, and determines whether or not the objects have been stored in the object set C (step S315). .. When all the objects are selected from the objects which are the elements of the object set N (G, s) in the vicinity of the objects and stored in the object set C (step S315: No), the information processing apparatus 100 performs step S306. Return to and repeat the process.

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

[8. effect〕
As described above, the information processing apparatus 100 according to the embodiment includes an acquisition unit 131, a selection unit 132, and a generation unit 134. The acquisition unit 131 obtains one object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a first graph including a directed edge connecting the nodes. get. The selection unit 132 selects a neighboring node located in the vicinity of one node corresponding to one object among a plurality of nodes based on the first graph. The generation unit 134 adds one node to the first graph, and regarding the connection of the directed edge, the directed edge between the one node and the neighboring node based on the connection condition changed by a predetermined condition. Generate a concatenated second graph.

As described above, the information processing apparatus 100 according to the embodiment adds one node corresponding to one object to the first graph, and regarding the connection of the directed edges, based on the connection condition changed by a predetermined condition. , By generating a second graph in which one node and a neighboring node are connected by a directed edge, the graph used for the search can be appropriately generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, the information processing apparatus 100 according to the embodiment has a determination unit 133. The determination unit 133 determines whether to change the connection condition based on the change condition regarding the connection condition which is a predetermined condition. When the determination unit 133 determines that the connection condition is changed, the generation unit 134 generates a second graph in which one node and a neighboring node are connected by a directed edge based on the changed connection condition. ..

As a result, the information processing apparatus 100 according to the embodiment can determine whether to change the connection condition according to the change condition, so that the connection condition is dynamically changed and the graph used for the search is appropriately generated. be able to. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 determines whether to change the connection condition based on the change condition regarding the number of the plurality of nodes in the first graph.

Thereby, the information processing apparatus 100 according to the embodiment can dynamically change the connection condition according to the number of nodes in the first graph and appropriately generate the graph used for the search. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 determines whether to change the connection condition when the number of the plurality of nodes in the first graph is equal to or more than a predetermined threshold value.

As a result, the information processing apparatus 100 according to the embodiment compares the number of a plurality of nodes in the first graph with a predetermined threshold value, dynamically changes the connection condition according to the result, and uses the graph for the search. Can be properly generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 concatenates based on the change condition regarding the ratio of the additional nodes that are the nodes added after a predetermined time point among the plurality of nodes in the first graph. Decide if you want to change the conditions.

Thereby, the information processing apparatus 100 according to the embodiment can dynamically change the connection condition according to the ratio of the additional nodes in the first graph and appropriately generate the graph used for the search. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 determines whether to change the connection condition when the ratio of the additional nodes among the plurality of nodes in the first graph is equal to or more than a predetermined threshold value.

As a result, the information processing apparatus 100 according to the embodiment compares the ratio of the additional nodes in the first graph with the predetermined threshold value, dynamically changes the connection condition according to the result, and obtains the graph used for the search. Can be generated appropriately. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 determines whether to change the connection condition based on the change condition regarding the number of directed edges in the first graph.

As a result, the information processing apparatus 100 according to the embodiment can dynamically change the connection condition according to the change condition regarding the number of directed edges in the first graph, and appropriately generate the graph to be used for the search. .. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 determines whether to change the connection condition based on the change condition regarding the statistical information of the directed edge in the first graph.

As a result, the information processing apparatus 100 according to the embodiment can dynamically change the connection condition according to the statistical information of the number of directed edges in the first graph, and appropriately generate the graph to be used for the search. can. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 changes the edge number condition regarding the number of directed edges in the connection condition based on the change condition. The generation unit 134 generates a second graph in which one node and a neighboring node are connected by a directed edge based on the changed edge number condition.

As a result, the information processing apparatus 100 according to the embodiment dynamically changes the edge number condition based on the change condition, generates a second graph based on the changed edge number condition, and uses the graph for the search. Can be generated appropriately. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 increases the number of connected edges specified in the edge number condition as the number of the plurality of nodes in the first graph increases. The generation unit 134 generates a second graph in which one node and neighboring nodes are connected by directed edges based on the number of connected edges after the increase.

As a result, the information processing apparatus 100 according to the embodiment increases the number of connected edges specified in the edge number condition as the number of nodes increases, and generates a second graph based on the increased edge number condition. Therefore, the graph used for the search can be appropriately generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 reduces the number of connected edges specified in the edge number condition when it is estimated that the specified generation time is exceeded. The generation unit 134 generates a second graph in which one node and neighboring nodes are connected by directed edges based on the number of connected edges after the decrease.

As a result, the information processing apparatus 100 according to the embodiment reduces the number of connected edges specified in the edge number condition when the generation time is exceeded, and generates a second graph based on the reduced edge number condition. The graph used for the search can be appropriately generated while suppressing the excess of the specified generation time. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 changes the edge number condition including the output number condition regarding the number of output edges starting from one node and ending at the other node. Based on the changed output number condition, the generation unit 134 generates a second graph in which the output edges starting from one node are connected to the number of output destination nodes corresponding to the output number condition among the neighboring nodes. do.

As a result, the information processing apparatus 100 according to the embodiment dynamically changes the edge number condition including the output number condition, and the number of output destination nodes corresponding to the output number condition is the output edge starting from one node. Can be concatenated, so that the graph used for the search can be appropriately generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the determination unit 133 changes the edge number condition including the input number condition regarding the number of input edges starting from another node and ending at one node. Based on the changed edge number condition, the generation unit 134 generates a second graph in which the input source nodes corresponding to the input number condition among the neighboring nodes are connected to the input edges having one node as the end point. do.

As a result, the information processing apparatus 100 according to the embodiment dynamically changes the edge number condition including the input number condition, and makes the input source node of the number corresponding to the input number condition an input edge having one node as an end point. Can be concatenated, so that the graph used for the search can be appropriately generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the selection unit 132 selects a neighboring node by searching the first graph.

As a result, the information processing apparatus 100 according to the embodiment can efficiently select neighboring nodes by searching the first graph, so that the graph used for the search can be appropriately selected while suppressing an increase in the generation time. Can be generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 134 generates the third graph by updating the directed edge in the second graph.

As a result, the information processing apparatus 100 according to the embodiment can perform edge adjustment processing when the edge connection is uneven, such as when a large number of edges are connected to a specific node in the generated second graph. If necessary, by updating the directed edge and generating the third graph, it is possible to reconstruct the graph in which the variation in the connection of the edges is eliminated, so that the graph used for the search is appropriately generated. be able to. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 134 generates the third graph when the second graph satisfies a predetermined condition regarding the reconstruction of the graph.

As a result, the information processing apparatus 100 according to the embodiment requires edge adjustment processing, such as when the connection of edges in the generated second graph is uneven, or when certain conditions relating to graph reconstruction are satisfied. In such a case, by updating the directed edge and generating the third graph, it is possible to reconstruct the graph in which the variation in the connection of the edges is eliminated, so that the graph used for the search should be generated appropriately. Can be done. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 134 generates the third graph by using the information about the nodes in the vicinity of each node included in the second graph.

As a result, the information processing apparatus 100 according to the embodiment generates a third graph by using the information about the nearby nodes of each node included in the second graph, for example, to virtually obtain an approximate K neighborhood graph state. Since the graph can be generated using the information about the nodes in the vicinity of each node included in the second graph, the graph used for the search can be appropriately generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

Further, in the information processing apparatus 100 according to the embodiment, the selection unit 132 refers to the information regarding the neighboring nodes of each node included in the second graph, thereby displaying the neighboring nodes corresponding to the neighboring nodes included in the second graph. select. The generation unit 134 generates a third graph in which each node and a neighboring node are connected by a directed edge based on the connection condition.

As a result, the information processing apparatus 100 according to the embodiment can efficiently select the neighboring nodes by referring to the information about the neighboring nodes of each node included in the second graph, so that the increase in the generation time is suppressed. However, the graph used for the search can be appropriately generated. Therefore, the information processing apparatus 100 can generate graph data that enables efficient search for a predetermined target.

[9. Hardware configuration]
The information processing apparatus 100 according to the above-described embodiment is realized by, for example, a computer 1000 having a configuration as shown in FIG. FIG. 17 is a hardware configuration diagram showing an example of a computer that realizes the functions of the information processing device. The computer 1000 includes a CPU 1100, a RAM 1200, a ROM (Read Only Memory) 1300, an HDD (Hard Disk Drive) 1400, a communication interface (I / F) 1500, an input / output interface (I / F) 1600, and a media interface (I / F). ) Has 1700.

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

The HDD 1400 stores a program executed by the CPU 1100, data used by such a program, and the like. The communication interface 1500 receives data from another device via the network N and sends it to the CPU 1100, and transmits the data generated by the CPU 1100 to the other device via the network N.

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

The media interface 1700 reads a program or data stored in the recording medium 1800 and provides the program or data 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 PD (Phase change rewritable Disk), a magneto-optical recording medium such as MO (Magneto-Optical disk), a tape medium, a magnetic recording medium, or a semiconductor memory. And so on.

For example, when the computer 1000 functions as the information processing apparatus 100 according to the embodiment, the CPU 1100 of the computer 1000 realizes the function of the control unit 130 by executing the program loaded on the RAM 1200. The CPU 1100 of the computer 1000 reads these programs from the recording medium 1800 and executes them, but as another example, these programs may be acquired from another device via the network N.

Although some of the embodiments of the present application have been described in detail with reference to the drawings, these are examples, and various modifications are made based on the knowledge of those skilled in the art, including the embodiments described in the disclosure line of the invention. It is possible to carry out the present invention in other modified forms.

[10. others〕
Further, among the processes described in the above-described embodiment, all or a part of the processes described as being automatically performed can be manually performed, or the processes described as being manually performed can be performed. All or part of it can be done automatically by a known method. In addition, information including processing procedures, specific names, various data and parameters shown in the above documents and drawings can be arbitrarily changed unless otherwise specified. For example, the various information shown in each figure is not limited to the information shown in the figure.

Further, each component of each of the illustrated devices is a functional concept, and does not necessarily have to be physically configured as shown in the figure. That is, the specific form of distribution / integration of each device is not limited to the one shown in the figure, and all or part of them may be functionally or physically distributed / physically in any unit according to various loads and usage conditions. Can be integrated and configured.

In addition, the processes described in the above-described embodiments can be appropriately combined as long as the processing contents do not contradict each other.

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

1 Information processing system 100 Information processing device 121 Object information storage unit 122 Connection condition information storage unit 123 Change condition information storage unit 124 Graph data storage unit 125 Origin information storage unit 126 Reconstruction condition information storage unit 127 Reconstruction graph data storage unit 130 Control unit 131 Acquisition unit 132 Selection unit 133 Decision unit 134 Generation unit 135 Search unit 136 Providing unit 10 Terminal device 50 Information providing device N network

Claims (20)

An acquisition unit that acquires one object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a first graph including a directed edge connecting the nodes. When,
Based on the first graph, a selection unit for selecting a neighboring node located in the vicinity of the one node corresponding to the one object among the plurality of nodes.
The one node is added to the first graph, and the connection of the directed edges is based on the connection condition changed by a predetermined condition which is a condition based on the tendency of the nodes or edges constituting the graph. A generator that generates a second graph in which the node of the above and the neighboring node are connected by the directed edge.
An information processing device characterized by being equipped with. A determination unit that determines whether to change the connection condition based on the change condition related to the connection condition, which is the predetermined condition.
Further prepare
The generator is
When the determination unit determines to change the connection condition, the second graph in which the one node and the neighboring node are connected by the directed edge is generated based on the changed connection condition. The information processing apparatus according to claim 1, wherein the information processing apparatus is to be used. The decision-making part
The information processing apparatus according to claim 2, wherein it is determined whether or not to change the connection condition based on the change condition regarding the number of the plurality of nodes in the first graph. The decision-making part
The information processing apparatus according to claim 3, wherein when the number of the plurality of nodes in the first graph is equal to or greater than a predetermined threshold value, it is determined whether or not to change the connection condition. The decision-making part
It is characterized in that it is determined whether to change the connection condition based on the change condition regarding the ratio of the additional node which is a node added after a predetermined time point among the plurality of nodes in the first graph. The information processing apparatus according to claim 2 or 3. The decision-making part
The information processing apparatus according to claim 5, wherein when the ratio of the additional node among the plurality of nodes in the first graph is equal to or higher than a predetermined threshold value, it is determined whether or not to change the connection condition. .. The decision-making part
The information processing apparatus according to any one of claims 2 to 6, wherein it is determined whether or not to change the connection condition based on the change condition regarding the number of directed edges in the first graph. .. The decision-making part
The information according to any one of claims 2 to 7, wherein it is determined whether or not to change the connection condition based on the change condition regarding the statistical information of the directed edge in the first graph. Processing equipment. The decision-making part
Based on the change condition, the edge number condition regarding the number of the directed edges in the connection condition is changed.
The generator is
Any of claims 2 to 8, wherein the second graph in which the one node and the neighboring node are connected by the directed edge is generated based on the changed edge number condition. The information processing apparatus according to item 1. The decision-making part
As the number of the plurality of nodes in the first graph increases, the number of connected edges specified in the edge number condition is increased.
The generator is
The information processing according to claim 9, wherein the second graph in which the one node and the neighboring node are connected by the directed edge is generated based on the number of connected edges after the increase. Device. The decision-making part
If it is estimated that the specified generation time will be exceeded, the number of connected edges specified in the edge number condition will be reduced.
The generator is
The information processing according to claim 9, wherein the second graph in which the one node and the neighboring node are connected by the directed edge is generated based on the reduced number of connected edges. Device. The decision-making part
The edge number condition including the output number condition regarding the number of output edges starting from the one node and ending at the other node is changed.
The generator is
Based on the changed output number condition, the second graph in which the output edge starting from the one node is connected to the number of output destination nodes corresponding to the output number condition among the neighboring nodes. The information processing apparatus according to any one of claims 9 to 11, characterized in that it is generated. The decision-making part
The edge number condition including the input number condition regarding the number of input edges starting from another node and ending at the one node is changed.
The generator is
Based on the changed edge number condition, the second graph in which the input edge having the one node as the end point is connected to the input source node of the number corresponding to the input number condition among the neighboring nodes. The information processing apparatus according to any one of claims 9 to 12, wherein the information processing apparatus is generated. The selection unit is
The information processing apparatus according to any one of claims 1 to 13, wherein the neighboring node is selected by searching the first graph. The generator is
The information processing apparatus according to any one of claims 1 to 14, wherein a third graph is generated by updating the directed edge in the second graph. The generator is
The information processing apparatus according to claim 15, wherein the second graph satisfies a predetermined condition for reconstructing the graph, and the third graph is generated. The generator is
The information processing apparatus according to claim 15 or 16, wherein the third graph is generated by using information about a node in the vicinity of each node included in the second graph. The selection unit is
By referring to the information about the neighboring nodes of each node included in the second graph, the neighboring node corresponding to each node included in the second graph is selected.
The generator is
The information processing apparatus according to claim 17, wherein the third graph in which each node and the neighboring node are connected by the directed edge is generated based on the connection condition. It is an information processing method executed by a computer.
Acquisition process to acquire one object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a first graph including a directed edge connecting the nodes. When,
A selection step of selecting a neighboring node located in the vicinity of the one node corresponding to the one object from the plurality of nodes based on the first graph.
The one node is added to the first graph, and the connection of the directed edges is based on the connection condition changed by a predetermined condition which is a condition based on the tendency of the nodes or edges constituting the graph. And a generation step of generating a second graph in which the node of the above and the neighboring node are connected by the directed edge.
An information processing method characterized by including. Acquisition procedure for acquiring one object to be searched for data, a plurality of nodes corresponding to each of other objects different from the one object, and a first graph including a directed edge connecting the nodes. When,
Based on the first graph, a selection procedure for selecting a neighboring node located in the vicinity of the one node corresponding to the one object among the plurality of nodes, and a selection procedure.
The one node is added to the first graph, and the connection of the directed edges is based on the connection condition changed by a predetermined condition which is a condition based on the tendency of the nodes or edges constituting the graph. And a generation procedure for generating a second graph in which the node of the above and the neighboring node are connected by the directed edge.
An information processing program characterized by having a computer execute.

Images