JP6705764B2 - Generation device, generation method, and generation program - Google Patents

Description

The present invention relates to a generation device, a generation method, and a generation program.

Conventionally, techniques for searching various information have been provided. For example, a technology has been provided that discloses a technology for performing a search using graph information generated by an undirected edge. Further, such a technique is used, for example, for image search.

Japanese Patent No. 5208001

However, in the above-mentioned conventional technique, it may be difficult to generate graph information that enables an efficient search for a predetermined target. For example, when each node corresponding to each target is searched using the graph information connected by the undirected edge, it is difficult to suppress the cost such as the processing time due to the search of the overlapping route.

The present application has been made in view of the above, and an object thereof is to provide a generation device, a generation method, and a generation program that generate graph information that enables an efficient search for a predetermined target.

The generation device according to the present application, an acquisition unit that acquires a node group including a plurality of nodes corresponding to each of the search target in the data search, and a predetermined node among the node group acquired by the acquisition unit first at the time of searching A selection unit to be selected as a root node to be used as a starting point, and a node other than a processed node group including a node reachable by tracing a directed edge from the root node among the node group A generation unit that generates graph information by a connection process that selects a node and connects directed edges from a predetermined number of nodes of the processed node group to the target node. ..

According to the aspect of the embodiment, it is possible to generate graph information that enables efficient search for a predetermined target.

FIG. 1 is a diagram for explaining an example of a function and effect exhibited by the generation device according to the embodiment. FIG. 2 is a diagram illustrating an example of a functional configuration included in the generation device according to the embodiment. FIG. 3 is a diagram illustrating an example of the object information storage unit according to the embodiment. FIG. 4 is a diagram illustrating an example of the graph information storage unit according to the embodiment. FIG. 5 is a flowchart showing an example of the generation process according to the embodiment. FIG. 6 is a diagram showing an example of graph information including a plurality of root nodes. FIG. 7 is a diagram showing an example of generation of a plurality of pieces of graph information. FIG. 8 is a diagram showing an example of graph information having a hierarchical structure. FIG. 9 is a flowchart showing an example of a generation process related to graph information having a hierarchical structure. FIG. 10 is a diagram showing an example of a process of generating graph information having a hierarchical structure. FIG. 11 is a flowchart showing an example of a search process using graph information.

Hereinafter, modes (hereinafter, referred to as “embodiments”) for carrying out the generation device, the generation method, and the generation program according to the present application will be described in detail with reference to the drawings. Note that the generation device, the generation method, and the generation program according to the present application are not limited by this embodiment. Also, in each of the following embodiments, the same parts are designated by the same reference numerals, and duplicate description will be omitted.

[1. Generation process concept]
First, the concept of the generation process executed by the generation device 100 will be described with reference to FIG. FIG. 1 is a diagram for explaining an example of a function and effect exhibited by the generation device according to the embodiment. For example, the generation device 100 is realized by one or a plurality of generation devices such as a server device and a cloud system, and a search is performed via a network N (see FIG. 2) such as a mobile communication network or a wireless LAN (Local Area Network). It is an information processing device capable of communicating with a terminal device (not shown) used by a user or the like.

For example, when the generation device 100 receives query information (hereinafter, also simply referred to as “query”) from the terminal device, the generation device 100 searches for a target (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 generation device 100 to the terminal device may be data itself such as image information, or may be information for referring to corresponding data such as a URL (Uniform Resource Locator). Good. Further, the query or search target data may be any type of data such as image, voice, text data. In the following description, it is assumed that the generation device 100 searches for an image.

The generation device 100 also generates graph information, as shown in FIG. Here, the directed edge means an edge that can trace data in only one direction. In the following, a source that is traced by an edge, that is, a node that is a start point is a reference source, and a destination that is traced by an edge, that is, a node that is an end point is a 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”. Here, each node corresponds to each object. For example, each of the plurality of local feature amounts 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 generation device 100 performs processing for nodes corresponding to millions to hundreds of millions of units of image information, but only a part of them is shown in the drawing. In the example of FIG. 1, for simplification of description, nine nodes are shown and the outline of the process is described. For example, the generation device 100 acquires a node group including a plurality of nodes such as the nodes N1 to N9 in FIG. 1 and generates graph information GR11 in which each node is connected by a directed edge.

In addition, in this way, when described as “node N* (* is an arbitrary numerical value)”, it indicates 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”.

The spatial information VS1-1 to VS1-6 in FIG. 1 may be Euclidean space. In addition, the spatial information VS1-1 to VS1-6 illustrated in FIG. 1 are conceptual diagrams for explaining the distance between each vector and the like. It becomes a multidimensional space. Note that, for example, the spatial information VS1-1 to VS1-6 shown in FIG. 1 is illustrated in a two-dimensional mode for illustration on a plane, but is, for example, a multidimensional space such as 100 dimensions or 1000 dimensions. And

In addition, the spatial information VS1-1 to VS1-6 illustrated in FIG. 1 are diagrams schematically illustrating the process of generating the graph information, and the spaces illustrated in the spatial information VS1-1 to VS1-6 are the same space. .. Further, in the following, the spatial information VS1-1 to VS1-6 will be referred to as spatial information VS1 in the case where they are described without distinction.

In addition, in the example illustrated in FIG. 1, in the spatial information VS1 other than the spatial information VS1-1 and the spatial information VS1-6, the illustration of the “node N* (* is an arbitrary numerical value)” is omitted and each acquired A node is expressed by adding a value of "*" of "node N* (* is an arbitrary numerical value)" in "○". For example, “◯” in the upper left of the space information VS1-2, which is internally marked with “2”, corresponds to the node identified by the node ID “N2”. For example, in the example shown in FIG. 1, the vector data corresponding to each node may be an N-dimensional real-valued vector.

In the present embodiment, the distance of each node in the spatial information VS1 is the similarity between corresponding objects. Here, in the example shown in FIG. 1, the degree of similarity between objects having a small distance between nodes in the spatial information VS1 is high, and the degree of similarity between objects having a large distance between nodes in the spatial information VS1 is low. For example, in the space information VS1 in FIG. 1, the node identified by the node ID “N6” and the node identified by the node ID “N7” are close to each other, that is, the distance is small. Therefore, the object corresponding to the node identified by the node ID “N6” and the object corresponding to the node identified by the node ID “N7” have a high degree of similarity.

Further, for example, in the spatial information VS1 in FIG. 1, the node identified by the node ID “N6” and the node identified by the node ID “N2” are remote, that is, the distance is large. Therefore, the object corresponding to the node identified by the node ID “N6” and the object corresponding to the node identified by the node ID “N2” have a low degree of similarity.

Further, in the example of FIG. 1, the generation device 100 generates the graph information GR11 by connecting the nodes with the directed edges by the generation process described later. For example, in the search using the graph information GR11, the same process as the graph structure type index is performed at the time of search, but the start position (starting point) starts from the root of this index (graph information GR11). For example, when performing a search using the graph information GR11 generated by the generation device 100, the search is performed starting from the node N1 that is the root node. For example, at the time of search, the nodes N2 to N9 and the like may be sequentially searched by tracing a directed edge from the node N1 that is the root node.

[2. Regarding the generation process executed by the generation device according to the embodiment]
For example, the generation device 100 can reach the target node by selecting a predetermined node from among the node group as the root node to be used as the first starting point at the time of searching, and following the root node from the node group and the directed edge from the root node. Information for generating graph information by selecting a node other than the processed node group including the target node as the target node, and connecting the directed edges from a predetermined number of nodes to the target node in the processed node group. It is a processing device. For example, the generation device 100 generates the graph information by repeating the above-described connection processing until there are no unprocessed nodes that are not connected to other nodes in the node group. Hereinafter, with reference to the drawings, an example of the functional configuration and operational effects of the generation device 100 that realizes the generation process will be described.

[2-1. Example of functional configuration]
First, the configuration of the generation device 100 according to the embodiment will be described with reference to FIG. FIG. 2 is a diagram illustrating an example of a functional configuration of the information processing apparatus according to the embodiment. FIG. 2 is a diagram illustrating an example of a functional configuration included in the generation device according to the embodiment. As illustrated in FIG. 2, the generation device 100 includes a communication unit 110, a storage unit 120, and a control unit 130. The generation device 100 has an input unit (for example, a keyboard and a mouse) that receives various operations from an administrator of the generation device 100, and a display unit (for example, a liquid crystal display) for displaying various information. May be. 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 N by wire or wirelessly, and transmits and receives various information such as a search query and a search result to and from the terminal device.

The storage unit 120 is realized by, for example, a semiconductor memory device 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. The storage unit 120 according to the embodiment includes an object information storage unit 121 and a graph information storage unit 122, as shown in FIG. Hereinafter, an example of information registered in the object information storage unit 121 and the graph information storage unit 122 will be described with reference to FIGS. 3 and 4.

Information regarding a search target (object) is registered in the object information storage unit 121. For example, identification information for identifying an object and vector data (vector information) corresponding to the object are registered in the object information storage unit 121.

For example, FIG. 3 is a diagram illustrating an example of the object information storage unit according to the embodiment. As shown in FIG. 3, information having items such as “object ID” and “vector information” is registered in the object information storage unit 121. The “object ID” is identification information for identifying an object. The "vector information" is vector information corresponding to the object identified by the object ID. That is, in the example of FIG. 3, vector data (vector information) corresponding to an object is registered in association with an object ID that identifies the object.

The graph information storage unit 122 has registered therein the graph information generated by the generation process described later. For example, in the graph information storage unit 122, information on edges that connect a plurality of objects, and information on directed edges that connect a reference source object and a reference destination object is registered.

For example, FIG. 4 is a diagram illustrating an example of the graph information storage unit according to the embodiment. As shown in FIG. 4, information having items such as “node ID”, “object ID”, and “directed edge information” is registered in the graph information storage unit 122. The “node ID” is identification information for identifying each node (target) in the graph information. The “object ID” is identification information for identifying the object. The “directed edge information” includes information such as “edge ID” and “reference destination”. The “edge ID” is identification information for identifying an edge connecting nodes. The “reference destination” is information indicating a reference destination (node) connected by an edge. That is, in the example of FIG. 4, the node ID that identifies a node corresponds to the information that identifies the object (target) corresponding to that node and the reference destination (node) to which the directed edge from that node is connected. It is attached and registered.

For example, the example of FIG. 4 indicates that the node identified by the node ID “N1” corresponds to the object (target) identified by the object ID “OB1”. Further, from the node identified by the node ID “N1”, the edge identified by the edge ID “E11” is connected to the node identified by the node ID “N2”. That is, the example of FIG. 4 shows that the node identified by the node ID “N1” can be followed from the node identified by the node ID “N1”.

Returning to FIG. 2, the description will be continued. The control unit 130 is stored in a storage device inside the generation device 100 by, for example, a CPU (Central Processing Unit), an MPU (Micro Processing Unit), an ASIC (Application Specific Integrated Circuit), an FPGA (Field Programmable Gate Array), or the like. The various programs are realized by executing a storage area such as a RAM as a work area. In the example illustrated in FIG. 2, the control unit 130 includes an acquisition unit 131, a selection unit 132, a generation unit 133, and a provision unit 134 (hereinafter, may be collectively referred to as processing units 131 to 134). Have.

The connection relationship between the processing units 131 to 134 included in the control unit 130 is not limited to the connection relationship illustrated in FIG. 2 and may be another connection relationship. Further, each of the processing units 131 to 134 realizes and executes the function/action (for example, FIG. 1) of the generation processing as described below, but these are functional units arranged for the purpose of description. It does not matter whether it matches the actual hardware element or software module. That is, if the following functions and actions of the generation process can be realized and executed, the generation device 100 may realize and execute the guidance process in arbitrary function units.

[2-2. Example of action and effect in generation processing]
Hereinafter, the content of the generation process executed and realized by each of the processing units 131 to 134 will be described using the flowchart shown in FIG. FIG. 5 is a flowchart showing an example of the generation process according to the embodiment.

First, the acquisition unit 131 acquires a node group (step S101). For example, the generation device 100 acquires the node group that is the target of the generation process from the external information processing device or the storage unit 120. For example, the generation device 100 acquires a node group corresponding to each object stored in the object information storage unit 121. In the example of FIG. 1, the generation device 100 acquires a node group such as the nodes N1 to N9.

Then, the selection unit 132 selects a root node (step S102). Here, the root node means a node used as an initial starting point at the time of searching. Note that the generation device 100 may select the root node by appropriately using various criteria. For example, the generation device 100 may select a node close to the average of the node group as the root node. For example, the generation device 100 may select a node located in the center of the spatial information VS1 as the root node. For example, the generation device 100 may cluster the node group by a predetermined clustering method and select the root node from the cluster having the largest number of elements (nodes). For example, the generation device 100 may select a node that is close to the average as the root node among the clusters having the largest number of elements (nodes).

In the example of FIG. 1, it is assumed that the generation device 100 randomly selects a root node. For example, the generation device 100 selects the node N1 as the root node, as shown in step S11 in FIG. In the example of FIG. 1, the node N1 is hatched and illustrated in a manner different from the other nodes N2 to N9 to indicate that the node N1 is the root node.

Then, the generation unit 133 selects the target node from the unprocessed nodes (step S103). Here, the unprocessed node means a node other than the processed node group including the root node and the nodes reachable by following the directed edge from the root node in the node group. In the example of FIG. 1, after selecting the node N1 as the root node, the nodes N2 to N9 are unprocessed nodes. In addition, the target node here means a node which is a target for performing the process of connecting the directed edges. In addition, as described above, the processed node group includes a root node and a node reachable by following a directed edge from the root node.

In the example of FIG. 1, it is assumed that the generation device 100 randomly selects a target node. For example, the generation device 100 selects the node N2 as the target node, as shown in step S12 in FIG. In addition, the generation device 100 may select the target node based on various criteria, not limited to random. For example, the generation device 100 may select a node close to the root node as the target node. In this case, in the search using the graph information generated by the generation device 100, the exhaustiveness of the search is improved, so that the search can be performed with high accuracy. For example, the generation device 100 may select a node remote from the root node as the target node. In this case, in the search using the graph information generated by the generation device 100, since one edge is moved to a farther place in the space, for example, the movement distance in the space by tracing one edge is long. As a result, it is expected that the search processing will be speeded up. Further, the generation device 100 may select and register not the root node but the node closest to the previously registered node and the node farthest from the previously registered node. In this case, the same effects as described above can be expected. For example, the generation device 100 may select, as the target node, not the root node but the node closest to the previously processed node or the node farthest from the previously processed node. For example, the generation device 100 may select the node other than the processed node group that is closest to the target node in the concatenation process immediately before the one concatenation process or the target node in the concatenation process immediately before the one concatenation process. The node farthest from may be selected as the target node in one connection process.

Then, the generation unit 133 connects to the target node the directed edges from a predetermined number of nodes in the processed node group that are closer to the target node (step S104). In this way, the generation unit 133 connects the directed edges from the predetermined number of nodes selected according to the distance from the target node in the processed node group to the target node.

In the example of FIG. 1, the generation device 100 sets the predetermined number to “2”, and connects the directed edges from the two nodes in the processed node group that are closer to the target node to the target node. The case is shown. The predetermined number “2” is an example, and may be various values (for example, 5 and 10) according to the number of nodes included in the node group and the like. For example, the generation device 100 may set the predetermined number to “100 or more” when handling data having a large number of dimensions. This may be expected to improve the search performance.

Here, as shown in the spatial information VS1-2 in FIG. 1, after the selection of the root node, the processed node group includes only the node N1 that is the root node. In this case, the generation device 100 connects the edge E11, which is the directed edge from the node N1, to the node N2, as shown in step S13 in FIG.

An arrow line connecting the nodes shown in the edge E11 and the like in FIG. 1 indicates that the connected nodes have a relationship between a reference source and a reference destination. Specifically, the node on the start point side of the arrow line is the reference source, and the node on the arrow tip side is the reference destination. For example, the edge E11 indicates that the node N1 is a reference source and the node N2 is a reference destination.

In this way, the generation device 100 performs the connection process of connecting the directed edges from the predetermined number of nodes in the processed node group to the target node. Note that the generation device 100 may connect the directed edges from all the nodes of the processed node group to the target node when the number of nodes included in the processed node group does not reach the predetermined number.

In addition, when the "edge E* (* is an arbitrary numerical value)" is written in this way, it indicates that the edge is an edge identified by the edge ID "E*". For example, when described as “edge E11”, the edge is the edge identified by the edge ID “E11”. As described above, by connecting the edge E11 from the node N1 to the node N2, it is possible to trace from the node N1 that is the starting point during the search to the node N2. Further, the node N2 is no longer an unprocessed node group and is included in the processed node group.

Then, when there is an unprocessed node (step S105: Yes), the generation unit 133 returns to step S103 and repeats the processing.

For example, after the linking process with the node N2 as the target node, the generation device 100 selects the node N3 as the target node as shown in step S14 in FIG. Here, as shown in the spatial information VS1-3 in FIG. 1, after the connection processing of the node N2, the processed node group includes two nodes N1 and N2. In this case, the generation device 100 connects the edge E12, which is the directed edge from the node N1, to the node N3, and the edge E21, which is the directed edge from the node N2, is connected to the node N3, as shown in step S15 in FIG. Connect to. In this way, the generation device 100 performs the connection process with the node N3 as the target node.

Then, when there is an unprocessed node (step S105: Yes), the generation unit 133 returns to step S103 and repeats the processing.

For example, after the connection process with the node N3 as the target node, the generation device 100 selects the node N4 as the target node, as shown in step S16 in FIG. Here, as shown in the spatial information VS1-4 in FIG. 1, after the connection processing of the node N3, the processed node group includes three nodes N1 to N3. In this case, the generation device 100 connects the directed edges from the two nodes, which are closer to the node N4 among the nodes N1 to N3, to the target node. In the example of FIG. 1, as shown in the spatial information VS1, the nodes N4 and N3 are near and the node N2 is far from the node N4. Therefore, as shown in step S17 in FIG. 1, the generation device 100 connects the edge E13, which is the directed edge from the node N1, to the node N4, and the edge E31, which is the directed edge from the node N3, to the node N4. Link. In this way, the generation device 100 performs the connection process with the node N4 as the target node.

Note that the generation device 100 may determine the node connected to the target node by performing proximity search for the target node using graph information such as index information during generation. For example, the generation device 100 may speed up by determining the node that is close to the target node in the processed node group by performing the same neighbor search process as at the time of the search. That is, the generation device 100 may determine a node connected to the target node by regarding the target node as a query and searching for a node close to the target node.

For example, the generation device 100 performs a neighborhood search on the top k nodes (k is an arbitrary number such as “2”) in the processed node group that are close to the target node, Set a directed edge (link) from the node to the target node.

Then, when there is an unprocessed node (step S105: Yes), the generation unit 133 returns to step S103 and repeats the processing.

For example, after the linking process with the node N4 as the target node, the generation device 100 selects the node N5 as the target node, as shown in step S18 in FIG. Here, as shown in the spatial information VS1-5 in FIG. 1, after the connection processing of the node N4, the processed node group includes four nodes N1 to N4. In this case, the generation device 100 connects the directed edges from the two nodes, which are closer to the node N5, of the nodes N1 to N4 to the target node. In the example of FIG. 1, as shown in the spatial information VS1, the distance to the node N5 is closer in the order of the nodes N1, N2, N4, and N3. Therefore, the generation device 100 connects the edge E14, which is the directed edge from the node N1, to the node N5, and the edge E22, which is the directed edge from the node N2, to the node N5, as shown in step S19 in FIG. Link. In this way, the generation device 100 performs the connection process with the node N5 as the target node.

Then, when there is an unprocessed node (step S105: Yes), the generation unit 133 returns to step S103 and repeats the processing. As illustrated in step S20 in FIG. 1, the generation device 100 sequentially performs the connection process after the connection process with the node N5 as the target node and the nodes N6 to N9 that are unprocessed nodes as the target nodes. For example, as shown in the spatial information VS1-6 in FIG. 1, the generation device 100 generates the graph information GR11 by performing the connection process as the target nodes in the order of nodes N6, N7, N8, and N9.

Then, when there is no unprocessed node (step S105: No), the generation unit 133 ends the process.

For example, the generation device 100 performs the following processing. For example, the generation device 100 selects an arbitrary node from a node set (hereinafter, also referred to as “set S”) corresponding to an object to be registered as a root node and excludes it from the set S. Then, the generation device 100 selects an arbitrary node from the set S and excludes it from the set S. Then, the generation device 100 performs a neighborhood search for the top k nodes that are close to the selected node in the nodes (processed node group) on the tree, and selects the relevant k node from the k searched nodes. Set an edge (link) to a node. The generation device 100 repeats the above-described processing until the set S becomes empty. In addition, in the example of FIG. 1, the generation of the graph information is shown, but the generation device 100 may provide various services by using the generated graph information. For example, the providing unit 134 may provide the graph information generated by the generating unit 133 to an external information processing device. For example, the providing unit 134 may provide the graph information GR11 to an information processing device that provides a predetermined search service. When the generating device 100 provides the search service, the providing unit 134 may provide the terminal device with the search result corresponding to the search query acquired from the terminal device by the acquisition unit 131.

[3. Modification example)
The generation device 100 according to the above-described embodiment may be implemented in various different forms other than the above-described embodiment. Therefore, in the following, another embodiment of the generation device 100 will be described. Note that, in the following, description of the same points as in the embodiment will be appropriately omitted.

[3-1. Multiple root nodes)
In the above example, the case where one node is selected as the root node has been shown, but the number of root nodes is not limited to one, and may be plural. For example, the generation device 100 may select nodes far from each other as the plurality of root nodes. Further, for example, the generation device 100 may perform predetermined clustering, and set the node closest to the center of each cluster as the root node. That is, the generation device 100 may select a plurality of nodes as the root node from the node group. This point will be described with reference to FIG. FIG. 6 is a diagram showing an example of graph information including a plurality of root nodes.

Spatial information VS1-6 in FIG. 6 corresponds to the spatial information VS1-6 in FIG. 1 and shows a case where one node N1 is selected as the root node. On the other hand, the spatial information VS1-21 in FIG. 6 indicates a case where two nodes, the node N1 and the node N10, are selected as root nodes. That is, the spatial information VS1-21 in FIG. 6 differs from the spatial information VS1-6 in FIG. 6 in including the node N10.

In this way, the generation device 100 may select a plurality of root nodes. As a result, by selecting a plurality of root nodes, the connection relation of the edges in each node is changed. In the example shown in FIG. 6, the graph information GR11 is changed to the graph information GR21. For example, in the spatial information VS1-21, the directed edge from the node N10 to the node N3 is connected instead of the directed edge from the node N3 to the node N4 in the spatial information VS1-6. When a search is performed using the graph information GR21 including a plurality of root nodes in this way, the search can be performed in parallel from a plurality of starting points, so that the search processing can be speeded up.

[3-2. Multiple root nodes)
Further, in the example of FIG. 6, the case where the common graph information GR21 is generated for a plurality of root nodes is shown, but the graph information may be generated for each root node. That is, the generation device 100 may generate a plurality of searchable graph information starting from each root node. This point will be described with reference to FIG. 7. FIG. 7 is a diagram showing an example of generation of a plurality of pieces of graph information.

The spatial information VS1-31 in FIG. 7 includes nodes N1 to N10. That is, the spatial information VS1-31 in FIG. 7 differs from the spatial information VS1-6 in FIG. 1 in that it includes the node N10. The spatial information VS1-31 in FIG. 7 shows a case where two nodes, the node N1 and the node N10, are selected as root nodes.

Here, the generation device 100 generates graph information for each root node. In the example of FIG. 7, the generation device 100 generates graph information for each of the nodes N1 and N10 that are root nodes.

In the example illustrated in FIG. 7, the generation device 100 generates the graph information GR11 illustrated in the spatial information VS1-6 by performing the connection process on the node N1 that is the root node. For example, the generation device 100 generates the graph information GR11 by performing connection processing until the unprocessed nodes are exhausted, with the nodes N2 to N9 excluding the node N10 that is another root node as unprocessed nodes. The spatial information VS1-6 in FIG. 7 corresponds to the spatial information VS1-6 in FIG.

Further, in the example illustrated in FIG. 7, the generation device 100 generates the graph information GR31 shown in the spatial information VS1-32 by performing the connection process on the node N10 that is the root node. For example, the generation device 100 generates the graph information GR31 by using the nodes N2 to N9 excluding the node N1 which is another root node as unprocessed nodes and performing the connection process until there are no unprocessed nodes.

In this way, the generation device 100 may generate the graph information for each of the plurality of root nodes. When the search is performed using the graph information GR11 and GR31 generated for each of the plurality of root nodes in this way, the search accuracy can be improved because the search can be performed in parallel from a plurality of starting points. Is possible. Although an example in which each node is registered in both GR11 and GR31 is shown, the registration target node may be registered alternately, randomly, or by calculating the distance from the root node and registering only in the nearest graph. For example, the generation device 100 performs each of the plurality of root nodes N1 and N10 by performing the linking process so that the target node is included in any of the plurality of graph information corresponding to each of the plurality of root nodes N1 and N10. You may generate several graph information corresponding to.

[3-3. Graph information with hierarchical structure]
The generation device 100 may generate graph information having a hierarchical structure. This point will be described with reference to FIGS. FIG. 8 is a diagram showing an example of graph information having a hierarchical structure.

For example, the generation device 100 generates graph information GR41 having a hierarchical structure as shown in FIG. Further, in the example shown in FIG. 8, in the graph information GR41, the illustration of “node N* (* is an arbitrary numerical value)” is omitted, and each acquired node is indicated by “○” in “node N*(* Is expressed by adding a value of "*" of "arbitrary numerical value)". For example, “◯”, which is the topmost “◯” in the graph information GR41 and internally attached with “1”, corresponds to the node identified by the node ID “N1”. Further, for example, the leftmost part “◯” of the fifth layer in the graph information GR41, and “◯” with “16” added inside corresponds to the node identified by the node ID “N16”. ..

Further, in the example of FIG. 8, in order to simplify the description, 18 nodes are illustrated and the outline of the process is described. For example, the generation device 100 acquires a node group including a plurality of nodes such as the nodes N1 to N18 in FIG. 1, has a hierarchical structure, and generates graph information GR41 in which nodes are connected by directed edges. .. For example, in the search using the graph information GR41, the same processing as the graph structure type index is performed at the time of search, but the start position (starting point) starts from the root of this index (graph information GR41). For example, when performing a search using the graph information GR41 generated by the generation device 100, the search is performed starting from the node N1 that is the root node. For example, at the time of search, the nodes N2 to N18 and the like on the second and subsequent layers may be sequentially searched by tracing the directed edge from the node N1 that is the root node.

[3-3-1. Example of graph information generation with hierarchical structure]
An example of graph information generation having a hierarchical structure will be described below with reference to the flowchart shown in FIG. FIG. 9 is a flowchart showing an example of a generation process related to graph information having a hierarchical structure. Further, in the description of FIG. 9, the generation process of the graph information GR41 will be described in detail with reference to FIGS. 8 and 10 as appropriate. FIG. 10 is a diagram showing an example of a process of generating graph information having a hierarchical structure.

Further, the graph information GR41-1 and GR41-2 shown in FIG. 10 are diagrams schematically showing the generation process of the graph information GR41, and the graph information GR41-1 and GR41-2 are the graph information GR41. Shows the state in the process of being generated. Further, in the following, the graph information GR41-1 and GR41-2 will be referred to as graph information GR41 when the generation process is described without any distinction.

Arrow lines connecting the nodes in FIGS. 8 and 10 indicate that the connected nodes have a reference source and a reference destination. Specifically, the node on the start point side of the arrow line is the reference source, and the node on the arrow tip side is the reference destination. For example, an edge (arrow line) having the node N1 as an arrowhead and the node N3 as an arrowhead indicates that the node N1 is a reference source and the node N3 is a reference destination.

First, the acquisition unit 131 acquires a node group (step S201). For example, the generation device 100 acquires the node group that is the target of the generation process from the external information processing device or the storage unit 120. For example, the generation device 100 acquires a node group corresponding to each object stored in the object information storage unit 121. In the example of FIG. 8, the generation device 100 acquires a node group such as the nodes N1 to N18.

Then, the selection unit 132 selects a root node (step S202). Further, the generation device 100 sets the hierarchy of the root node to the first hierarchy. In the example of FIG. 10, the generation device 100 randomly selects a root node. For example, the generation device 100 selects the node N1 as the root node, as shown in step S41 in FIG. In the examples of FIGS. 8 and 10, the node N1 is hatched and illustrated in a manner different from the other nodes N2 to N18 to indicate that the node N1 is the root node. The generation device 100 causes the node N1, which is a root node, to belong to the first layer.

Then, the generation unit 133 sets the layer directly below the layer of the root node (step S203). The term “directly below a layer” as used herein means a layer below the layer, and may be the next layer following the layer. For example, the layer immediately below the first layer is the second layer. In the example of FIG. 10, the generation device 100 sets the layer below the first layer of the root node to the second layer.

Then, the generation unit 133 selects a target node belonging to the layer being set from the unprocessed nodes (step S204). In the example of FIG. 10, after selecting the node N1 as the root node, the nodes N2 to N18 are unprocessed nodes.

Here, the generation device 100 determines the number of nodes belonging to the hierarchy based on a predetermined standard. In the example of FIG. 10, the generation device 100 determines twice the number of nodes belonging to the upper layer closest to the layer as the number of nodes belonging to the layer. In the example of FIG. 10, the generation device 100 determines that the number of nodes belonging to the second layer is “2 (=1×2)” because the number of nodes in the first layer immediately above the second layer is “1”. To decide. In this case, assuming that the layer number is L, the number of nodes belonging to the layer is set to 2 (L-1) power, but L×2, L×3, L squared, log(L), etc. Either is fine. Note that the generation device 100 may determine the number of nodes belonging to the hierarchy by appropriately using various criteria.

For example, the generation device 100 may determine the number of nodes belonging to each layer so that the number of layers is equal to or less than a predetermined threshold. For example, in the generation device 100, when the number of target objects (the number of nodes) is 1 million and the threshold value of the number of layers is “5”, the average number of nodes belonging to each layer is “200,000 (=1 million). /5)”, the number of nodes belonging to each layer may be determined. Note that the generation device 100 may determine the number of nodes in each layer so that the number of nodes belonging to each layer increases as the layer becomes lower, or the number of nodes belonging to each layer decreases as the layer becomes lower. The number may be determined.

Then, the generation device 100 selects nodes having the number of nodes belonging to the hierarchy. In the example of FIG. 10, the generation device 100 randomly selects nodes having the number of nodes belonging to the hierarchy. Note that the generation device 100 may randomly select nodes having the number of nodes belonging to the hierarchy, and if the distance between the nodes is shorter than a predetermined distance, one may be randomly selected again. Further, the generation device 100 may select each node so that each node is the farthest. Further, the generation device 100 may perform clustering and select the node closest to the center of each cluster. For example, the generation device 100 selects two nodes N2 and N3 as target nodes belonging to the second layer, as shown in step S42 in FIG.

Then, the generation unit 133 connects, to the target node, the directed edges from a predetermined number of nodes in the node group belonging to a layer higher than the layer being set and having a closer distance to the target node ( Step S205). In the example of FIG. 10, the generation device 100 sets the predetermined number to “2”, and selects two nodes from a node group belonging to a layer higher than the layer being set, from a node having a closer distance to the target node. The case where the directed edge of is connected to the target node is shown.

Here, as shown in the graph information GR41-1 in FIG. 10, the node group belonging to the higher hierarchy (first hierarchy) than the second hierarchy includes only the node N1 which is the root node. In this case, the generation device 100 determines that the directed edge from the node N1 is connected to the node N2 and the directed edge from the node N1 is connected to the node N3, as shown in step S43 in FIG. For example, the generation device 100 may determine the node connected to the target node by performing proximity search for the target node using graph information such as index information during generation.

In this way, the generation device 100 performs the concatenation process of concatenating the directed edges from a predetermined number of nodes, out of the nodes belonging to the layer higher than the layer being processed, to the target node. In addition, when the number of nodes belonging to a layer higher than the processing target layer does not reach a predetermined number, the generation device 100 selects from all nodes belonging to a layer higher than the processing target layer. The directed edge may be connected to the target node. In the example of FIG. 10, since only one node N1 belongs to the hierarchy higher than the second hierarchy, it is determined that the directed edges from the node N1 are connected to the nodes N2 and N3 of the second hierarchy.

Then, the generation device 100 connects the directed edge from the node N1 to the node N2 and connects the directed edge from the node N1 to the node N3, as shown in step S44 in FIG. In this way, the generation device 100 can speed up the processing by collectively performing the connection processing regarding the nodes in the same hierarchy.

Then, when there is an unprocessed node (step S206: Yes), the generation unit 133 updates the layer being set to the layer immediately below it (step S207), and returns to step S203 to repeat the process. For example, after the connection processing with the nodes N2 and N3 belonging to the second layer as the target nodes, the generation device 100 updates the layer being set to the third layer immediately below the second layer.

Then, the generation unit 133 selects a target node belonging to the layer being set from the unprocessed nodes (step S204). In the example of FIG. 10, after the connection processing of the nodes N2 and N3 belonging to the second layer, the nodes N4 to N18 are unprocessed nodes.

In the example of FIG. 10, the generation device 100 sets the number of nodes belonging to the third layer to “4 (=2×2)” because the number of nodes in the second upper layer immediately preceding the third layer is “2”. To decide. For example, the generation device 100 selects four nodes N4, N5, N6, and N7 as nodes belonging to the third layer, as shown in step S45 in FIG.

Then, the generation unit 133 connects, to the target node, the directed edges from a predetermined number of nodes in the node group belonging to a layer higher than the layer being set and having a closer distance to the target node ( Step S205). In the example of FIG. 10, the generation device 100 sets the predetermined number to “2”, and selects two nodes from a node group belonging to a layer higher than the layer being set, from a node having a closer distance to the target node. The case where the directed edge of is connected to the target node is shown.

Here, as shown in the graph information GR41-2 in FIG. 10, three nodes N1 to N3 are included in the node group that belongs to a higher hierarchy (first hierarchy, second hierarchy) than the third hierarchy. In this case, the generation device 100 determines that the directed edges from the two nodes, which are closer to the nodes N4 to N7 among the nodes N1 to N3, are connected to the respective target nodes. For example, the generating device 100 determines that the directed edge from the node N2 is connected to the node N4 and the directed edge from the node N1 is connected to the node N5, as shown in step S46 in FIG. Further, the generation device 100 determines to connect the directed edge from the node N3 to the node N4 and to connect the directed edge from the node N2 to the node N5. Further, the generation device 100 determines to connect the directed edges from the nodes N2 and N3 to the node N6, and to connect the directed edges from the nodes N1 and N3 to the node N7.

Then, as illustrated in step S47 in FIG. 10, the generation device 100 connects the nodes by the directed edge determined in step S46.

Note that the generation device 100 may connect, to the target node, the directed edge from the node that belongs to only the highest hierarchy immediately adjacent to the hierarchy to which the target node belongs. For example, when the nodes N4 to N7 of the third layer are the target nodes, the generation device 100 determines the directed edges from the nodes N2 and N3 belonging to the second layer, which is the immediately upper layer of the third layer, as the target node. May be connected to. That is, when the nodes N4 to N7 of the third layer are the target nodes, the generation device 100 may exclude the node N1 belonging to the first layer from the target.

Then, when there is an unprocessed node (step S206: Yes), the generation unit 133 updates the layer being set to the layer immediately below it (step S207), and returns to step S203 to repeat the process. For example, after the linking process with the nodes N4 to N7 belonging to the third layer as the target nodes, the generation device 100 updates the layer being set to the fourth layer immediately below the third layer. Then, the generation device 100 performs the connection process sequentially with the nodes N4 to N7 belonging to the third layer as the target nodes and the nodes N8 to N18 that are unprocessed nodes as the target nodes after the connection process. In this way, the generation device 100 generates the graph information GR41 by repeating the connection process for each layer.

Then, when there is no unprocessed node (step S206: No), the generation unit 133 ends the process. For example, the generation device 100 may provide various services using the generated graph information. For example, the providing unit 134 may provide the graph information generated by the generating unit 133 to an external information processing device. For example, the providing unit 134 may provide the graph information GR41 to an information processing device that provides a predetermined search service. When the generating device 100 provides the search service, the providing unit 134 may provide the terminal device with the search result corresponding to the search query acquired from the terminal device by the acquisition unit 131.

For example, the generation device 100 performs the following processing. For example, the generation device 100 selects an arbitrary node from a node set (hereinafter, also referred to as “set S”) corresponding to an object to be registered as a root node and excludes it from the set S. Then, the generation device 100 calculates the node number n(i) of the layer from the node number n(i-1) of the upper layer. Here, the "function n()" of "the number of nodes n(*)" means a function that outputs the number of nodes corresponding to the hierarchy of "* (arbitrary numerical value)". For example, “n(2)” corresponds to the number of nodes in the second layer (“2” in the example of FIG. 8). For example, the generation device 100 may use the “function n()” that satisfies the relationship of “n(i)=n(i−1)×2”.

Then, the generation device 100 arbitrarily selects n(i) objects from the set S to form a sub-set L, sets them as nodes of the layer, and excludes nodes belonging to the sub-set L from the set S. .. Then, the generation device 100 acquires any one object (node) from the sub-set L. Excluding the node of the layer, that is, performing a neighborhood search for k nodes from the nodes above the upper layer, and setting an edge (link) from the k searched nodes to the node at this point without setting Record as information.

Then, the generation device 100 repeats the process of acquiring any one node from the sub-set L and storing the above-mentioned setting information if the sub-set L is not empty. If the sub-set L is empty, the generation device 100 sets an edge for one layer based on the recorded edge setting information.

If the set S is not empty, the generator 100 repeats the process from selecting a new sub-set L until the set S becomes empty, after descending by one layer. As described above, since the generation device 100 adds layers one by one, the maximum depth in the generated graph information is guaranteed.

[4. Search example)
Here, an example of the search using the above-mentioned graph information will be shown. The search using the generated graph information is not limited to the following, and may be performed by various procedures. This point will be described with reference to FIG. 11 as an example. FIG. 11 is a flowchart showing an example of a search process using graph information. Further, the object described below may be read as a node. In the following description, the generation device 100 is described as performing the search process, but the search process may be performed by another device.

Here, the neighborhood object set N(G, y) is a set of neighborhood objects that are related by the edge assigned to the node y. “G” may be predetermined graph information (for example, the graph information GR11 or the graph information GR41). For example, the generation device 100 executes a k-nearest neighbor search process.

For example, the generation device 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 generation device 100 may extract the object (node) selected as the root node as the subset S. Further, for example, the hypersphere is a virtual sphere that indicates the 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 as the search result at the same time.

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

Next, the generation device 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 expansion element, and r(1+ε) is a value indicating the radius of the search range (only the nodes within this range are searched. The accuracy can be improved by making it larger than the search range). is there. When the distance d(s, y) between the object s and the object y exceeds r(1+ε) (step S304: Yes), the generation device 100 outputs the object set R as a neighboring object set of the object y (step S305). ), the processing ends.

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 generation device 100 sets the neighborhood object set N(G, s) of the object s. One object that is not included in the object set C is selected from the objects that are the elements, 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 generation device 100 determines whether or not the distance d(u, y) between the object u and the object y is equal to or smaller than r(1+ε) (step S307). When the distance d(u, y) between the object u and the object y is equal to or less than r(1+ε) (step 307: Yes), the generation device 100 adds the object u to the object set S (step S308).

Next, the generation device 100 determines whether or not the distance d(u, y) between the object u and the object y is equal to or less than r (step S309). When the distance d(u, y) between the object u and the object y exceeds r (step S309: No), the generation device 100 performs the determination (process) of step S315.

When the distance d(u, y) between the object u and the object y is equal to or smaller than r (step S309: Yes), the generation device 100 adds the object u to the object set R (step S310). Then, the generation device 100 determines whether the number of objects included in the object set R exceeds ks (step S311). The predetermined number ks is a natural number that is arbitrarily determined. For example, ks=2 may be used.

When the number of objects included in the object set R exceeds ks (step S311: Yes), the generation device 100 selects from the object set R the object that has the longest distance to the object y among the objects included in the object set R. It is excluded (step S312).

Next, the generation device 100 determines whether 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 is equal to ks (step S313: Yes), the generation device 100 determines that among the objects included in the object set R, the object having the longest distance from the object y and the object y. Is set to a new r (step S314).

Then, the generation device 100 determines whether or not all the objects have been selected from the objects that are the elements of the neighboring object set N(G,s) of the object s and stored in the object set C (step S315). When all the objects have not been selected from the objects that are the elements of the neighboring object set N(G,s) of the object s and stored in the object set C, the generation device 100 returns to step S306 and repeats the processing.

When all objects have been selected from the objects that are the elements of the neighboring object set N(G,s) of the object s and stored in the object set C, the generation device 100 determines whether the object set S is an empty set. Is determined (step S316). When the object set S is not an empty set, the generation device 100 returns to step S302 and repeats the processing. When the object set S is an empty set (step S316: Yes), the generation device 100 outputs the object set R and ends the process (step S317). For example, the generation device 100 may provide an object (node) included in the object set R as a search result corresponding to the search query (input object y) to the terminal device or the like that has performed the search.

[5. effect〕
As described above, the generation device 100 acquires a node group including a plurality of nodes corresponding to each search target in data search. Then, the generation device 100 selects a predetermined node from the acquired node group as the root node to be used as the first starting point when searching. Then, the generation device 100 selects a node other than the processed node group including the root node and the nodes reachable by tracing the directed edge from the root node as the target node, and the processed node group Among them, the graph information is generated by the connecting process of connecting the directed edges from the predetermined number of nodes to the target node. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target.

Further, the generation device 100 generates graph information by a connection process of connecting directed edges from a predetermined number of nodes selected according to the distance from the target node in the processed node group to the target node. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by connecting the directed edges according to the distance between the nodes.

In addition, the generation device 100 generates graph information by a connection process that connects directed edges from a predetermined number of nodes from the closer distance to the target node in the processed node group to the target node. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by connecting edges having a short distance with a directed edge.

In addition, in the repetition of the connection process, the generation device 100 generates the graph information by the connection process that connects the directed edge to the target node as a node that belongs to a layer that increases according to the number of times of the connection process. Therefore, the generation device 100 can generate graph information having a hierarchical structure to generate graph information that enables an efficient search for a predetermined target.

In addition, the generation device 100 generates graph information by the concatenation process in which the root node is the node of the highest layer and the layer of the target node is the node of the layer lower than the layer of the nodes of the processed node group. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by connecting edges based on a hierarchical structure.

In addition, the generation device 100 generates the graph information by performing the connection process so that the number of layers becomes equal to or less than the predetermined threshold. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by performing a generation process so that the number of layers falls within a predetermined range.

In addition, the generation device 100 generates graph information by determining the number of target nodes in each connection process so that the number of layers becomes equal to or less than a predetermined threshold. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by determining the number of nodes in each hierarchy so that the number of layers falls within a predetermined range. ..

In addition, the generation device 100 generates the graph information so that the number of nodes included in each hierarchy changes. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by changing the number of nodes included in each hierarchy.

In addition, the generation device 100 generates graph information by connecting the directed edges from the nodes belonging to the hierarchy higher than the hierarchy to which the target node belongs to the target node. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by connecting edges based on a hierarchical structure.

In addition, the generation device 100 generates graph information by connecting the directed edge from the node belonging to the next higher hierarchy to the target node to the target node. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by connecting edges based on a hierarchical structure.

Further, the generation device 100 generates the graph information by repeating the connection process until there are no unprocessed nodes in the node group that are not connected to other nodes. Therefore, the generation device 100 can generate graph information that can reach all nodes from the root node by the edge.

Further, the generation device 100 selects one node from the node group as the root node. For this reason, the generation device 100 can generate the graph information that enables an efficient search for a predetermined target while suppressing an increase in the amount of data by using one root node.

Further, the generation device 100 selects a plurality of nodes as the root node from the node group. Therefore, the generation device 100 can generate graph information that enables an efficient search for a predetermined target by using a plurality of root nodes. For example, since the generation device 100 can perform a search in parallel from a plurality of starting points, it is possible to improve the search accuracy.

In addition, the generation device 100 performs a concatenation process such that the target node is included in any of the plurality of pieces of graph information corresponding to each of the plurality of root nodes, so that the plurality of graphs corresponding to each of the plurality of root nodes are generated. By generating the information, it is possible to improve the search accuracy.

Further, the generation device 100 may be configured such that, among the nodes other than the processed node group, the node closest to the target node in the concatenation process immediately before the one concatenation process or the target node in the concatenation process immediately before the one concatenation process. By selecting the farthest node as the target node in the one concatenation process, it is expected to speed up the search process.

Further, the generation device 100 generates the graph information by performing the neighborhood search of the target node using the index information regarding the processed node group, thereby performing the neighborhood search processing similar to that at the time of the search, thereby performing high-speed processing. Can be converted.

Further, among the respective processes described in the above-described embodiment and modification, all or part of the processes described as being automatically performed may be manually performed, or described as manually performed. It is also possible to automatically carry out all or part of the processing performed by a known method. In addition, the processing procedures, specific names, information including various data and parameters shown in the above-mentioned documents and drawings can be arbitrarily changed unless otherwise specified. For example, the various kinds of information shown in each drawing are not limited to the illustrated information.

Further, each constituent element of each illustrated device is functionally conceptual, and does not necessarily have to be physically configured as illustrated. That is, the specific form of distribution/integration of each device is not limited to that shown in the figure, and all or a part of the device may be functionally or physically distributed/arranged in arbitrary units according to various loads or usage conditions. It can be integrated and configured.

Further, the above-described embodiments and modified examples can be appropriately combined within a range in which the processing content is not inconsistent.

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

1 Information Processing System 100 Generation Device 121 Object Information Storage Unit 122 Graph Information Storage Unit 130 Control Unit 131 Acquisition Unit 132 Selection Unit 133 Generation Unit 134 Providing Unit N Network

Claims (18)

An acquisition unit that acquires a node group including a plurality of nodes corresponding to each of the search targets in the data search,
Of the node group acquired by the acquisition unit, a selection unit that selects a predetermined node as a root node to be used as a starting point at the time of searching,
Of the node group, the root node, and select a node other than the processed node group including a node reachable by tracing a directed edge from the root node as a target node, among the processed node group, A generation unit that generates graph information by a connection process that connects directed edges from a predetermined number of nodes to the target node,
A generating device comprising: The generator is
The graph information is generated by a connection process of connecting directed edges from a predetermined number of nodes selected according to the distance from the target node from the processed node group to the target node. The generating device according to claim 1. The generator is
The graph information is generated by a connection process of connecting directional edges from a predetermined number of nodes from the closer distance to the target node in the processed node group to the target node. The generating device according to claim 2. The generator is
In the repetition of the connection processing, the graph information is generated by the connection processing of connecting the directed edge to the target node as a node belonging to a hierarchy that increases according to the number of times of the connection processing. Item 4. The generation device according to any one of Items 1 to 3. The generator is
The graph information is generated by the concatenation process in which the root node is a node in the highest hierarchy and the hierarchy of the target node is a node in a hierarchy lower than the hierarchy of the nodes in the processed node group. The generating device according to claim 4. The generator is
The generation device according to claim 4 or 5, wherein the graph information is generated by performing the connection processing so that the number of layers becomes equal to or less than a predetermined threshold. The generator is
The generation device according to claim 6, wherein the graph information is generated by determining the number of the target nodes in each connection process so that the number of layers becomes equal to or less than a predetermined threshold value. The generator is
The generation device according to claim 4, wherein the graph information is generated so that the number of nodes included in each of the layers changes. The generator is
9. The graph information is generated by connecting a directed edge from a node belonging to a hierarchy higher than the hierarchy to which the target node belongs to the target node, to generate the graph information. The generating device according to. The generator is
The generation device according to claim 9, wherein the graph information is generated by connecting a directed edge from a node that belongs to a hierarchy immediately above the hierarchy to which the target node belongs to the target node. The generator is
The graph information is generated by repeating the linking process until there are no unprocessed nodes that are not linked to other nodes in the node group. Generator. The selection unit,
The generation device according to claim 1, wherein one of the node groups is selected as the root node. The selection unit,
The generation device according to claim 1, wherein a plurality of nodes are selected as the root node from the node group. The generator is
Generating the plurality of graph information corresponding to each of the plurality of root nodes by performing the connection processing so that the target node is included in any of the plurality of graph information corresponding to each of the plurality of root nodes The generating device according to claim 13, wherein The generator is
Of the nodes other than the processed node group, the node closest to the target node in the connection process immediately before the one connection process or the farthest from the target node in the connection process immediately before the one connection process. The node is selected as a target node in the one concatenation process. The generating device according to any one of claims 1 to 14. The generator is
The generation device according to claim 1, wherein the graph information is generated by performing a neighborhood search of the target node using index information regarding the processed node group. A computer-implemented generation method,
An acquisition step of acquiring a node group including a plurality of nodes corresponding to respective search targets in the data search;
A selection step of selecting a predetermined node as a root node to be used as a starting point at the time of searching from the node group acquired by the acquisition step;
Of the node group, the root node, and select a node other than the processed node group including a node reachable by tracing a directed edge from the root node as a target node, among the processed node group, A generation step of generating graph information by a connection process of connecting directed edges from a predetermined number of nodes to the target node;
A generating method comprising: An acquisition procedure for acquiring a node group including a plurality of nodes corresponding to respective search targets in data search,
Of the node group acquired by the acquisition procedure, a selection procedure for selecting a predetermined node as a root node to be used as a starting point at the time of search,
Of the node group, the root node, and select a node other than the processed node group including a node reachable by tracing a directed edge from the root node as a target node, among the processed node group, A generation procedure of generating graph information by a connection process of connecting directed edges from a predetermined number of nodes to the target node,
A generation program characterized by causing a computer to execute.

Images