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

Description

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

Conventionally, techniques for searching (retrieving) various types of information have been provided. For example, in order to perform a search for a predetermined target, a technique is provided for generating graph data in which nodes corresponding to a search target are connected by edges. Also, such a technique is used, for example, for image retrieval.

Japanese Patent No. 6293335 Japanese Patent No. 6300982

However, with the conventional techniques described above, it may be difficult to generate an appropriate graph. For example, in the above conventional technology, search results using generated graphs are not taken into consideration, and searches using generated graphs may not produce desired results and appropriate graphs may not be generated. be. Therefore, it is desired to generate an appropriate graph.

The present application has been made in view of the above, and aims to provide an information processing apparatus, an information processing method, and an information processing program that generate an appropriate graph by adding edges.

An information processing apparatus according to the present application acquires correct data indicating a correct object close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges from among a plurality of objects. and adding an additional edge connected to a target node corresponding to a target object not included in the search result objects retrieved by the search processing of the graph using the query, among the correct objects indicated by the correct data. and an updating unit that updates the graph.

According to one aspect of the embodiment, there is an effect that an appropriate graph can be generated by adding edges.

FIG. 1 is a diagram illustrating an example of information processing according to an embodiment. FIG. 2 is a diagram showing an example of a tree used for information processing according to the embodiment. FIG. 3 is a diagram illustrating a configuration example of an information processing system according to the embodiment; FIG. 4 is a diagram illustrating a configuration example of an information processing apparatus according to the embodiment; 5 is a diagram illustrating an example of an object information storage unit according to the embodiment; FIG. 6 is a diagram illustrating an example of a tree information storage unit according to the embodiment; FIG. 7 is a diagram illustrating an example of a graph information storage unit according to the embodiment; FIG. 8 is a diagram illustrating an example of a correct data storage unit according to the embodiment; FIG. FIG. 9 is a flowchart illustrating an example of information processing according to the embodiment; FIG. 10 is a flowchart illustrating an example of search processing according to the embodiment. FIG. 11 is a diagram illustrating an example of information processing according to the modification. FIG. 12 is a diagram illustrating a configuration example of an information processing apparatus according to a modification; FIG. 13 is a diagram illustrating an example of a graph information storage unit according to a modification; FIG. 14 is a flowchart illustrating an example of search processing according to the modification. FIG. 15 is a hardware configuration diagram showing an example of a computer that implements the functions of the information processing apparatus.

Hereinafter, modes for implementing an information processing apparatus, an information processing method, and an information processing program (hereinafter referred to as "embodiments") according to the present application will be described in detail with reference to the drawings. The information processing apparatus, information processing method, and information processing program according to the present application are not limited to this embodiment. Also, in each of the following embodiments, the same parts are denoted by the same reference numerals, and overlapping descriptions 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 illustrating an example of information processing according to an embodiment. In FIG. 1, the information processing apparatus 100 (see FIG. 4) acquires graph data (simply referred to as “graph”) to which a new edge (also referred to as “additional edge”) is to be added, and adds an edge to the graph. A case of performing an adding process (hereinafter also referred to as an "update process") is shown. Note that the update process may be performed on a graph being generated by the information processing apparatus 100, or may be performed on a graph such as the k-nearest neighbor graph acquired from the information providing apparatus 50 (see FIG. 3) or the like. good.

The example of FIG. 1 shows a case where target information (object) is vectorized and a graph (graph index) for the vectorized object is generated (updated). That is, the example of FIG. 1 shows a case where the information processing apparatus 100 performs processing using a vector as an object value corresponding to an object. The information used by the information processing apparatus 100 is not limited to vectors, and may be information in any format as long as the information can express the similarity of each target. For example, the information processing apparatus 100 may use predetermined data or values corresponding to each target. For example, the information processing apparatus 100 may use a predetermined numerical value (for example, a binary value or a hexadecimal value) generated from each target. For example, the information processing apparatus 100 is not limited to vectors, and may use any form of data as long as the distance (similarity) between data is defined. In the following description, a case where image information is used as an object will be described as an example, but the object may be various objects such as moving image information and audio information.

The information processing apparatus 100 processes, for example, a graph including nodes corresponding to a huge amount of image information (for example, millions to hundreds of millions) within the range that the information processing apparatus 100 can process. Only part of it is illustrated. In the example of FIG. 1, seven nodes are illustrated to explain the outline of the processing in order to simplify the explanation. Specifically, the example of FIG. 1 shows the case where the graph GR11 including the nodes N1, N2, N3, etc. and the edge E1, etc. is processed. When "node N* (* is an arbitrary number)" is described in this way, it indicates that the node is identified by the node ID "N*". For example, when "node N1" is described, the node is identified by the node ID "N1".

Moreover, when "edge E* (* is an arbitrary numerical value)" is described as above, it indicates that the edge is identified by the edge ID "E*". For example, when "edge E1" is described, the edge is identified by the edge ID "E1". In the example of FIG. 1, the edge is an undirected edge to simplify the explanation, but the edge may be a directed edge. The undirected edge here means an edge (bidirectional edge) that allows data to be traced in both directions between connected nodes. An undirected edge (bidirectional edge) may be simply referred to as an "edge" below. For example, the edge E1 connecting the node N1 and the node N2 enables bidirectional tracing between the node N1 and the node N2. That is, edge E1 allows tracing from node N1 to node N2, and edge E1 allows tracing from node N2 to node N1.

Graphs GR11-1 and GR11-2 shown in FIG. 1 are diagrams schematically showing the generation (update) process of the graphs. Graph data. Further, hereinafter, the graphs GR11-1 and GR11-2 will be referred to as the graph GR11 when they are not distinguished from each other.

Graph GR11 shown in FIG. 1 is a conceptual diagram for explaining distances between vectors, etc., and graph GR11 is a multidimensional space. For example, the graph GR11 shown in FIG. 1 is illustrated in a two-dimensional manner because it is illustrated on a plane, but it is assumed to be a multi-dimensional space such as 100-dimensional space or 1000-dimensional space. The vector data corresponding to each node may be an N-dimensional real-valued vector.

Here, the distance between each node indicates the similarity of the node (image information), and the closer the distance, the more similar. In this embodiment, the distance of each node in the graph GR11 is used as the degree of similarity between corresponding objects. For example, it is assumed that the similarity of image information corresponding to each node is mapped as the distance between nodes in graph GR11. For example, it is assumed that the similarity between concepts corresponding to each node is mapped to the distance between each node. Here, in the example of FIG. 1, the similarity between objects with short distances between nodes in the graph GR11 is high, and the similarity between objects with long distances between nodes in the graph GR11 is low.

For example, in graph GR11 in FIG. 1, node N43 and node N2 are close to each other, that is, the distance is short (close). Therefore, it indicates that the object corresponding to the node N43 and the object corresponding to the node N2 have a high degree of similarity. Also, in the graph GR11 in FIG. 1, the node N43 and the node N53 are remote, that is, the distance is long (far). Therefore, it indicates that the object corresponding to the node N43 and the object corresponding to the node N53 have a low degree of similarity. Note that the distance as an index indicating similarity may be any distance as long as it can be applied as the distance between vectors (N-dimensional vectors). Various distances may be used.

From here, the processing of adding an edge to the graph GR11 by the information processing apparatus 100 will be specifically described with reference to FIG.

First, the information processing apparatus 100 acquires a graph in which a plurality of nodes corresponding to data search targets (objects) are connected by edges (step S11). In the example of FIG. 1, the information processing apparatus 100 acquires a graph GR11-1 including nodes N1, N2, N3, N38, N43, N53, N99, etc. and edges E1 to E3, etc. FIG. For example, the information processing apparatus 100 acquires the graph GR11 from the graph information storage unit 123 (see FIG. 7). Note that the information processing apparatus 100 may generate the graph GR11 using various conventional techniques as appropriate.

The information processing device 100 generates a plurality of queries (step S12). For example, the information processing apparatus 100 may generate a query based on objects registered as nodes in the graph GR11. The information processing apparatus 100 may use the average of a plurality of objects registered as nodes in the graph GR11 as a query. The information processing apparatus 100 selects each object registered as a node in the graph GR11, and performs a query using the selected object (also referred to as a "first object") and a second object different from the first object. may be generated. For example, the information processing apparatus 100 may generate a query using a second object corresponding to a node to which edges from a node corresponding to the first object (also referred to as a “first node”) are connected in the graph GR11. good.

For example, the information processing apparatus 100 generates a query using a second object corresponding to the farthest node or the nearest node from the first node in the node group to which edges from the first node are connected. Also, the information processing apparatus 100 may generate a query using a second object corresponding to a node randomly selected from a node group to which edges from the first node are connected. The information processing apparatus 100 selects each object included as a node in the graph GR11 as a first object, and uses a second object corresponding to the first object to generate a plurality of queries. For example, if the graph GR11 has 10 million nodes, the information processing apparatus 100 may generate 10 million queries, select a predetermined number (for example, 1 million) of objects as first objects, number of queries may be generated.

Note that the above is merely an example, and the information processing apparatus 100 may generate a query by various methods without being limited to the above. For example, the information processing apparatus 100 may use, as a query, objects of the same system that are not registered in the graph GR11. For example, the information processing apparatus 100 may use the query used for the search by the user when a search service using the graph GR11 has already been provided to the user. For example, the information processing apparatus 100 may use an object registered as a node in the graph GR11 as a query. Processing in this case will be described later.

For example, the information processing apparatus 100 generates a query using the second object corresponding to the farthest node from the first node in the node group to which the edges from the first node of the first object are connected. For example, when the object OB1 corresponding to the node N1 is selected as the first object, the information processing apparatus 100 selects the node N99, which is the farthest node from the node N1, among the nodes to which edges from the node N1 are connected. A query is generated with the corresponding object OB99 as the second object. In the example of FIG. 1, for the sake of explanation, the information processing apparatus 100 calculates (generates) the average of the first object and the second object corresponding to the node randomly selected from all the nodes on the graph GR11. , the average of which is the query. In the following, the information processing apparatus 100 treats the object OB1 as the first object, the randomly selected object OB43 as the second object, and processes the query QE1, which is the average of the objects OB1 and OB43, as an example. .

The information processing apparatus 100 acquires correct data for each query (step S13). The information processing apparatus 100 acquires correct data indicating the result of extracting k (k is an arbitrary number) nodes as neighboring nodes for each query. The information processing apparatus 100 may generate correct answer data, or may acquire the correct answer data from the information providing apparatus 50 . For example, the information processing device 100 compares each object included as a node in the graph GR11 with the query QE1 to generate correct data RD1 indicating k neighboring nodes (neighboring objects) corresponding to the query QE1. good too. The information processing apparatus 100 may use nearby correct data, but this point will be described later.

In the example of FIG. 1, the information processing apparatus 100 acquires correct data RD1 corresponding to the query QE1. As shown in the correct answer data RD1, the neighboring correct answer information corresponding to the query QE1 has a No of "1", which indicates that the closest node is the node corresponding to the object OB2. Further, the correct answer data corresponding to the query QE1 has a No of "6", which means that the sixth closest node (object) is the node corresponding to the object OB38. Also, the correct answer data corresponding to the query QE1 indicates that No is "k", that is, the farthest node (farthest object) is the node corresponding to the object OB55.

Further, the information processing apparatus 100 performs search processing using each query and acquires search results (step S14). The information processing apparatus 100 sets the value of the search range coefficient “ε” to “0” and performs search processing (also referred to as “first search processing”) using all edges included in the graph GR11 for each query. to get search results for each query. The information processing apparatus 100 sets the value of the search range coefficient “ε” to “0” and performs the search processing as shown in FIG. 10 using the graph GR11 for each query, thereby searching each query. Get results.

Here, the concept of the search range coefficient "ε" will be briefly explained. For example, the information processing device 100 searches the graph GR11 using a first range within a radius r centered on the query QE1 and a second range within a radius r (1+ε) centered on the query QE1, Extract neighboring nodes. In this way, the information processing apparatus 100 performs processing for extracting neighboring nodes by applying the search range coefficient “ε”. Details of the processing using the search range coefficient “ε” will be described with reference to FIG. 10 . .

In the example of FIG. 1 , the information processing apparatus 100 sets the value of the search range coefficient “ε” to “0”, and executes the search processing as shown in FIG. 10 using the graph GR11 for the query QE1. Get the result RS1. As shown in the search result RS1, the neighborhood correct information corresponding to the query QE1 has a No of "1", indicating that the nearest node is the node corresponding to the object OB2. Also, the search result corresponding to query QE1 indicates that No is "6", that is, the sixth closest node (object) is the node corresponding to object OB53. Also, the search result corresponding to query QE1 indicates that No is "k", that is, the farthest node (farthest object) is the node corresponding to object OB168. As described above, in the example of FIG. 1 , when the value of the search range coefficient “ε” is set to “0”, the information processing apparatus 100 performs the search process using the query QE1 on the object OB38 included in the correct data RD1. The corresponding node cannot be extracted as a neighbor node.

The information processing apparatus 100 specifies, as a target object, an object that is not included in the search result objects searched by the graph search process using the query, among the correct objects indicated by the correct answer data. In the example of FIG. 1, the information processing apparatus 100 compares the correct data RD1 and the search result RS1, and identifies, among the correct objects included in the correct data RD1, an object OB38 that is not included in the search result RS1 as a target object. . Accordingly, the information processing apparatus 100 adds an additional edge with the node N38 corresponding to the object OB38, which is the target object, as the target node. That is, the information processing apparatus 100 adds an edge connected to the missing object as an additional edge.

The information processing apparatus 100 also selects a node that connects with the target node (step S15). The information processing apparatus 100 then updates the graph by adding additional edges between the selected node and the target node (step S16). The information processing apparatus 100 selects an object (selection object) from the search result objects and adds an additional edge between the node (selection node) corresponding to the selected selection object and the target node. For example, the information processing apparatus 100 selects an object closest to the target object from among the search result objects as a selection object, and adds an additional edge between the node (selection node) corresponding to the selected selection object and the target node. do.

In the example of FIG. 1, the information processing apparatus 100 selects the object OB1 closest to the object OB38 among the objects (search result objects) in the search result RS1 as the selected object. Then, the information processing apparatus 100 generates the graph GR11-2 by adding an additional edge E11 connecting the node N1 corresponding to the object OB1 and the node N38 corresponding to the object OB38. Accordingly, the information processing apparatus 100 updates the graph GR11. For each query, the information processing apparatus 100 performs a process of adding the above-described additional edges to nodes corresponding to all search-missing objects. In the case of a directed edge, the information processing apparatus 100 creates a directed edge (starting at the selected node and ending at the target node) from the selected node corresponding to the selected object to the target node corresponding to the missing object (target object). ) is given.

As described above, the information processing apparatus 100 adds an additional edge connected to the target node corresponding to the target object, which is not included in the search result object among the correct objects indicated by the correct data, as the target object. In this way, the information processing apparatus 100 can appropriately generate a graph by adding additional edges that connect to nodes corresponding to objects that have not been searched.

For example, in a search using a graph, the search range (for example, the search range is also used internally in k-nearest neighbor search) is expanded by a search range coefficient "ε", which is an expansion coefficient, to improve search accuracy. be able to. On the other hand, if the search range coefficient "ε" is increased, the number of nodes to be searched increases, resulting in an increase in search time. Also, ideally, the nodes within the search range should form a connected graph within the connected range. Therefore, as a result of searching with a search range coefficient “ε” of 0 (no range expansion) using a certain query, if a node that was not searched and a node that was searched are connected, the search range coefficient “ε” will be 0. However, since the search can be performed without omission of search and the search range is not expanded, the increase in search time can be suppressed. Therefore, as described above, the information processing apparatus 100 performs this processing using a large number of queries for the base graph (GR11-1 in FIG. 1), thereby obtaining the structure of the graph (GR11 in FIG. 1). can be improved.

[1-1-1. Nearby Correct Data]
As described above, the correct data may be neighboring correct data (neighboring correct data). For example, the information processing apparatus 100 may generate neighborhood correct data by performing a search process using the graph GR11.

For example, to generate accurate correct data, it is necessary to calculate the distances to all objects, which requires processing time for large data sets. Therefore, when the information processing apparatus 100 generates correct data, instead of obtaining correct data for a query, a neighborhood search result (neighborhood correct data) may be obtained in advance using some evaluation target index. In the example of FIG. 1, the information processing apparatus 100 appropriately uses various techniques related to neighborhood search (nearby search) to generate neighborhood correct data corresponding to query QE1.

For example, the information processing apparatus 100 generates near-correct data corresponding to the query QE1 through the process illustrated in FIG. 10 . In this case, the information processing apparatus 100 sets the value of a search range coefficient “ε” described later to a value (called “value for correct answer generation”) that is greater than a predetermined value, and performs search processing as shown in FIG. Second search processing) is performed using the graph GR11 to generate neighborhood correct data corresponding to the query QE1. In this way, the information processing apparatus 100 generates neighborhood correct data by the second search process in which the value of the search range coefficient "ε" is set larger than that of the first search process. Thereby, the information processing apparatus 100 can shorten the processing time compared to the case of calculating the distances to all the objects and generating the correct answer data.

The information processing apparatus 100 may perform the processing of FIG. 1 using the generated neighborhood correct data as correct data. Accordingly, the information processing apparatus 100 can suppress an increase in processing time. Note that the above is just an example, and if the information processing apparatus 100 can generate neighborhood correct data in a shorter processing time than calculating distances to all objects and generating correct data, what kind of processing can be performed? may generate neighborhood correct data.

The derivation of the correct answer generating value of the above-mentioned coefficient "ε" will be described. First, when using the neighborhood correct data and the correct data, it is desirable to set the search range coefficient "ε" to a value for generating correct answers that is greater than a predetermined value. increase. Therefore, it is necessary to obtain a search range coefficient "ε" that can obtain sufficient accuracy and that has the smallest possible value. Therefore, the information processing apparatus 100 gradually increases the search range coefficient "ε", and sets the value of the search range coefficient "ε" at the time when no new object appears in the search results as a value for obtaining correct data. It is the value of the search range coefficient "ε". For example, the information processing apparatus 100 increases the value of the search range coefficient from the first value (for example, 0, 0.05, etc.) at a predetermined interval (for example, 0.05, 0.1, etc.), and the result of the neighborhood search is The second value at the time when no new objects appear is used as the value of the search range coefficient when generating neighborhood correct data. It should be noted that the derivation of the correct answer generation value of the search range coefficient "ε" may be performed at any time before the neighborhood correct data (correct answer data) is generated. good too.

[1-1-2. When the node itself is used as a query]
Further, as described above, the information processing apparatus 100 may use the object itself registered as a node in the graph GR11 as a query. In this case, the information processing apparatus 100 performs the following process for each target query (node) to be processed.

First, the information processing apparatus 100 deletes edges connected to each target query (node). For example, the information processing apparatus 100 deletes edges (edges E1, E2, and E3) connected to the node N1 from the graph G11 in a process using the node N1 as a query. Then, the information processing apparatus 100 performs the processing of FIG. 1 using the graph G11 from which the edge connected to the node N1 has been deleted.

Then, the information processing apparatus 100 attaches the deleted edge back to the node after completing the process of adding the additional edge using the node as a query. The information processing apparatus 100 adds back the deleted edges (edges E1, E2, and E3) after completing the process of adding additional edges using the node N1 as a query. The information processing apparatus 100 performs the above-described processing on all queries. In this manner, the information processing apparatus 100 repeats the above-described process for each query until the process for all queries is completed.

[1-1-3. Query generation method]
As described above, the information processing apparatus 100 may generate queries using various types of information as appropriate. For example, the information processing apparatus 100 may calculate (generate) an average between one node and the nearest or farthest node among neighboring nodes connected to the one node, and use the average as a query. . Further, the information processing apparatus 100 may calculate (generate) an average between one node and a node randomly selected from neighboring nodes connected to the one node, and use the average as a query. Further, as shown in FIG. 1, the information processing apparatus 100 may calculate (generate) an average of one node and nodes randomly selected from all nodes on the graph, and use the average as a query.

[1-2. tree information]
In the example described above, only the graph (graph information) is generated, but the information processing apparatus 100 may generate tree information corresponding to the generated graph. For example, the information processing apparatus 100 appropriately uses various tree-related techniques to generate tree information corresponding to the generated graph. For example, the information processing apparatus 100 may generate tree information IND11 as indicated by information group GINF11 in FIG. Then, the information processing apparatus 100 may speed up processing by using various indexes such as the generated tree information. For example, the information processing apparatus 100 may use tree information IND11 as shown in the information group GINF11 in FIG. 2 to determine a node that serves as the starting point of the search (hereinafter also referred to as "starting node"). FIG. 2 is a diagram showing an example of a tree used for information processing according to the embodiment. The tree information IND11 may be generated by the information processing device 100, or the information processing device 100 may acquire the tree information IND11 from another external device such as the information providing device 50. FIG.

For example, the information processing apparatus 100 may determine the origin node corresponding to the query QE1 based on the tree information IND11. The information processing apparatus 100 determines the starting node using the tree information IND11 stored in the tree information storage unit 122 (see FIG. 6). For example, tree information IND11 is a tree with a tree structure that can reach some nodes in graph GR11. In the example of FIG. 2, in order to simplify the explanation, the tree information IND11 shows only routes that reach five nodes N1 to N5, but there are many routes (eg, 500, 1000, etc.) to other nodes. The route to reach may be included.

For example, the information processing apparatus 100 determines the starting node in the graph GR11 using tree structure type tree information such as tree information IND11 in FIG. In the example of FIG. 1, the information processing apparatus 100 determines (identifies) the origin node that is a neighborhood candidate of the tree information IND11 by tracing the tree information IND11 from the top (root RT) to the bottom based on the query QE1. . Thereby, the information processing apparatus 100 can efficiently determine the origin node corresponding to the search query (query QE1).

For example, the information processing apparatus 100 may determine the origin node corresponding to the query QE1 by tracing the tree information IND11 from the root RT to leaf nodes (nodes in the graph GR11). For example, the information processing apparatus 100 may determine the reached leaf node as the origin node by tracing the tree information IND11 from the root RT to the leaf node using various conventional techniques related to the tree structure. For example, the information processing apparatus 100 may determine the starting node by tracing the tree information IND11 downward based on the degree of similarity with the query QE1. For example, the information processing apparatus 100 may determine which of the nodes VT1, VT2, etc. is to be traced from the root RT based on the degree of similarity between the query QE1 and the nodes VT1, VT2. For example, the information processing apparatus 100 may determine to trace from the root RT to the node VT2 having the highest similarity with the query QE1 among the nodes VT1, VT2, and the like. Further, for example, the information processing apparatus 100 may determine to trace from the node VT2 to the node VT2-2 having the highest degree of similarity with the query QE1 among the nodes VT2-1 to VT2-4.

The tree information (tree data) illustrated in the example of FIG. 2 is an example, and the information processing apparatus 100 may search for graph information using various types of tree information. The information processing apparatus 100 may generate a tree that is used to determine the starting node at the time of searching. Note that the use of a tree is merely an example, and the information processing apparatus 100 may use various types of information other than the tree as long as it is possible to speed up the determination of the starting node at the time of searching. For example, the information processing apparatus 100 generates a search tree (tree information) for searching high-dimensional vectors at high speed. The high-dimensional vector referred to here may be, for example, a vector with several hundred to several thousand dimensions, or a vector with more dimensions.

For example, the information processing apparatus 100 may generate tree information IND11 regarding a tree structure (tree structure) as shown in FIG. For example, the information processing apparatus 100 may generate a search tree for a kd-tree (k-dimensional tree). For example, the information processing apparatus 100 may generate a search tree related to a VP tree (Vantage-Point tree).

Also, for example, the information processing apparatus 100 may generate a tree having another tree structure. For example, the information processing apparatus 100 may generate various trees in which leaves of a tree structure are connected to a graph. For example, the information processing apparatus 100 may generate various trees in which the leaves of the trees in the tree structure correspond to the nodes in the graph. Further, when performing a search using such a tree, the information processing apparatus 100 may search the graph from leaves (nodes) reached by following the tree.

Note that the tree as described above is merely an example, and the information processing apparatus 100 may generate a tree with any data structure as long as the query in the graph can be identified at high speed. For example, the information processing apparatus 100 can generate a tree by appropriately using various conventional techniques such as a technique related to binary space division, as long as the node in the graph information corresponding to the query can be identified at high speed. good too. For example, the information processing apparatus 100 may generate a tree with any data structure as long as the tree can support high-dimensional vector searches. The information processing apparatus 100 can perform a more efficient search for a predetermined target by using the tree and graph as described above. That is, the information processing apparatus 100 can perform a faster search for a predetermined target by using the tree and graph as described above.

[2. Configuration of information processing system]
Next, the configuration of the information processing system 1 according to the embodiment will be described using FIG. FIG. 3 is a diagram illustrating a configuration example of an information processing system according to the embodiment; As shown in FIG. 3 , 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 via a predetermined network N so as to be communicable by wire or wirelessly. The information processing system 1 shown in FIG. 3 may include multiple terminal devices 10 , multiple information providing devices 50 , and multiple information processing devices 100 .

The terminal device 10 is an information processing device used by a user. The terminal device 10 accepts various operations by the user. In addition, below, the terminal device 10 may be described as a user. That is, hereinafter, the user can also be read as the terminal device 10 . The terminal device 10 described above is implemented by, for example, a smart phone, 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 that stores information for providing various information to users and the like. For example, the information providing device 50 stores object IDs based on character information and the like collected from various external devices such as web servers. For example, the information providing device 50 is an information processing device that provides an image search service to a user or 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 images for which an image search service is to be performed. Further, by transmitting a query to the information processing device 100 , 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 .

The information processing device 100 is a generation device that generates a graph in which nodes corresponding to each of a plurality of objects are connected to neighboring nodes by edges. Further, the information processing apparatus 100 targets a plurality of objects and adjusts the values of the parameters used for generating the graph based on the reference value at the time of the graph generation processing including the search processing using the graph being generated. A decision device for determining a value of a parameter by processing.

The information processing device 100 is a search device that extracts objects similar to a query. For example, upon receiving query information (query) from the terminal device 10 , the information processing device 100 searches for objects (eg, vector information) similar to the query, and provides the terminal device 10 with search results. Further, for example, the data provided by the information processing device 100 to the terminal device 10 may be data itself such as image information, or information for referring to corresponding data such as a URL (Uniform Resource Locator). may Data to be searched or queried may be any type of data such as image, voice, and text data. In this embodiment, a case where the information processing apparatus 100 searches for images will be described as an example.

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

(Communication unit 110)
The communication unit 110 is realized by, for example, a NIC (Network Interface Card) or the like. The communication unit 110 is connected to a network (for example, network N in FIG. 3) by wire or wirelessly, and transmits and receives information to and from the terminal device 10 and the information providing device 50 .

(storage unit 120)
The storage unit 120 is realized by, for example, a semiconductor memory device such as a RAM (Random Access Memory) or a flash memory, or a storage device such as a hard disk or an optical disk. The storage unit 120 according to the embodiment has an object information storage unit 121, a tree information storage unit 122, a graph information storage unit 123, and a correct data storage unit 124, as shown in FIG.

(Object information storage unit 121)
The object information storage unit 121 according to the embodiment stores various information about objects. For example, the object information storage unit 121 stores an object ID and vector data for each data set. 5 is a diagram illustrating an example of an object information storage unit according to the embodiment; FIG. The object information storage unit 121 shown in FIG. 5 includes items such as "data set ID", "object ID", and "vector information".

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

In the example of FIG. 5, the data set (data set DS1) identified by the data set ID "DS1" includes a plurality of objects (objects) identified by the object IDs "OB1", "OB2", "OB3", etc. is included. The object (object OB1) identified by the object ID "OB1" is associated with multidimensional vector information "10, 24, 54, 2...". The object (object OB2) identified by the object ID "OB2" is associated with multidimensional vector information "32, 1, 120, 31...".

It should be noted that the object information storage unit 121 may store various types of information, not limited to the above, depending on the purpose.

(Tree information storage unit 122)
The tree information storage unit 122 according to the embodiment stores various types of information about trees. 6 is a diagram illustrating an example of a tree information storage unit according to the embodiment; FIG. Specifically, in the example of FIG. 6, the tree information storage unit 122 shows tree information of a tree structure. In the example of FIG. 6, the tree information storage unit 122 includes items such as "root layer", "first layer", "second layer", and "third layer". It should be noted that not only "first hierarchy" to "third hierarchy" but "fourth hierarchy", "fifth hierarchy", "sixth hierarchy", etc. may be included according to the number of hierarchies of the tree.

The “root hierarchy” indicates the root (top) hierarchy that is the starting point for determining the origin node using the tree. "First layer" stores information for identifying (specifying) a node (node or vector in graph information) belonging to the first layer of the tree. A node stored in the "first layer" is a node corresponding to a layer directly connected to the root of the tree.

"Second layer" stores information that identifies (specifies) a node (node or vector in graph information) belonging to the second layer of the tree. A node stored in the "second layer" is a node corresponding to the immediately lower layer connected to a node in the first layer. "Third layer" stores information for identifying (specifying) a node (node or vector in graph information) belonging to the third layer of the tree. A node stored in the "third layer" is a node corresponding to the immediately lower layer linked to a node in the second layer.

In the example shown in FIG. 6, the tree information storage unit 122 stores information corresponding to the tree information IND11 in FIG. For example, the tree information storage unit 122 indicates that the nodes of the first layer are the nodes VT1 to VT3. Numerical values in parentheses under each node indicate vector values corresponding to each node.

Also, the tree information storage unit 122 indicates that the nodes of the second layer immediately below the node VT2 are the nodes VT2-1 to VT2-4. Also, the tree information storage unit 122 indicates that the node in the third layer immediately below the node VT2-1 is a node (vector) in the graph GR11 of the nodes N1 and N2. The tree information storage unit 122 indicates that the nodes in the third layer immediately below the node VT2-2 are the nodes (vectors) in the graph GR11 of the nodes N3, N4, and N5.

Note that the tree information storage unit 122 may store various types of information, not limited to the above, depending on the purpose.

(Graph information storage unit 123)
The graph information storage unit 123 according to the embodiment stores various kinds of information about graphs. For example, the graph information storage unit 123 stores graph information used for information processing such as search processing. In the example of FIG. 7, the graph information storage unit 123 stores neighborhood graph data. 7 is a diagram illustrating an example of a graph information storage unit according to the embodiment; FIG. The graph information storage unit 123 shown in FIG. 7 has items such as "node ID", "object ID", and "edge information". "Edge information" includes information such as "edge ID" and "reference destination".

“Node ID” indicates identification information for identifying each node (object) in graph data. "Object ID" indicates identification information for identifying an object.

"Edge information" indicates information about edges connected to the corresponding node. In the example of FIG. 7, "edge information" indicates information about undirected edges (bidirectional edges) connected to the corresponding node. "Edge ID" indicates identification information for identifying an edge connecting nodes. "Reference destination" indicates information indicating a reference destination (node) connected by an edge. That is, in the example of FIG. 7, a node ID identifying a node is associated with information identifying an object (target) corresponding to the node and a reference destination (node) to which an edge from the node is connected. registered with

The example of FIG. 7 indicates that the node (node N1) identified by the node ID "N1" corresponds to the object (target) identified by the object ID "OB1". Further, from node N1, an edge (edge E1) identified by edge ID "E1" is connected to a node (node N2) identified by node ID "N2". That is, the example of FIG. 7 indicates that the node N2 can be traced from the node N1 in the graph information by the edge E1. Also, from node N1, an edge (edge E2) identified by edge ID "E2" is connected to a node (node N53) identified by node ID "N53". That is, the example of FIG. 7 indicates that the node N53 can be traced from the node N1 in the graph information through the edge E2.

Also, the example of FIG. 7 indicates that the node (node N2) identified by the node ID "N2" corresponds to the object (target) identified by the object ID "OB2". Further, from the node N2, the edge (edge E1) identified by the edge ID "E1" is connected to the node (node N1) identified by the node ID "N1". That is, the example of FIG. 7 indicates that the node N1 can be traced from the node N2 by the edge E1 in the graph information.

It should be noted that the graph information storage unit 123 may store various types of information, not limited to the above, depending on the purpose. For example, the graph information storage unit 123 may store lengths of edges connecting nodes (vectors). That is, the graph information storage unit 123 may store information indicating distances between nodes (vectors). The graph information storage unit 123 may store not only graph information connected by undirected edges but also various kinds of graph information. The graph information storage unit 123 may store graph information connected by directed edges.

(Correct answer data storage unit 124)
The correct data storage unit 124 according to the embodiment stores various types of information regarding correct data. The correct data storage unit 124 stores correct data used for measuring accuracy of search processing when using each query. For example, the correct data storage unit 124 stores k neighboring nodes of each query as correct objects in association with each query. 8 is a diagram illustrating an example of a threshold storage unit according to the embodiment; FIG. The correct data storage unit 124 shown in FIG. 8 has items such as "query ID", "vector information", and "correct answer object". The "correct answer object" includes items such as "No" and "object".

“Query ID” indicates identification information for identifying a query. For example, "query ID" indicates identification information for identifying an evaluation query. "Vector information" indicates vector information of the corresponding query. The "correct answer object" stores a correct answer object used as correct answer data for the corresponding query. "No" indicates the rank of each neighboring node of the corresponding query. "Object" indicates a neighboring node (object) of corresponding rank.

The example of FIG. 8 indicates that the query (query QE1) identified by the query ID "QE1" is multidimensional vector information of "7, 35, 13, 93...". The correct answer data corresponding to the query QE1 has No of "1", which means that the nearest node is the node corresponding to the object OB2. Further, the correct answer data corresponding to the query QE1 has a No of "6", which means that the sixth closest node (object) is the node corresponding to the object OB38. Also, the correct answer data corresponding to the query QE1 indicates that No is "k", that is, the farthest node (farthest object) is the node corresponding to the object OB55.

Note that the correct data storage unit 124 may store various types of information, not limited to the above, depending on the purpose. When using a plurality of pieces of graph information, the correct data storage unit 124 may store threshold values in association with graph information using the threshold values. For example, when graph information other than the graph GR11 is used, the correct data storage unit 124 may associate and store the graph information using each threshold value and the corresponding threshold value. Further, the correct data storage unit 124 may store the aforementioned near correct data.

(control unit 130)
Returning to the description of FIG. 4, the control unit 130 is a controller, and is stored in a storage device inside the information processing apparatus 100 by, for example, a CPU (Central Processing Unit) or MPU (Micro Processing Unit). Various programs (corresponding to an example of an information processing program) are executed by using the RAM as a work area. Also, the control unit 130 is a controller, and is implemented by an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array).

As shown in FIG. 4, the control unit 130 includes an acquisition unit 131, a generation unit 132, a selection unit 133, an update unit 134, and a provision unit 135, and has functions and actions of information processing described below. realize or perform Note that the internal configuration of the control unit 130 is not limited to the configuration shown in FIG. 4, and may be another configuration as long as it performs information processing to be described later.

(Acquisition unit 131)
Acquisition unit 131 acquires various types of information. Acquisition unit 131 acquires various types of information from storage unit 120 . The acquisition unit 131 acquires various types of information from the object information storage unit 121, the tree information storage unit 122, the graph information storage unit 123, the correct data storage unit 124, and the like. The acquisition unit 131 also acquires various types of information from an external information processing device. The acquisition unit 131 acquires various types of information from an external device such as the terminal device 10 . The acquisition unit 131 acquires graph information from the graph information storage unit 123 . The acquisition unit 131 acquires tree information from the tree information storage unit 122 .

The acquiring unit 131 acquires correct data indicating a correct object close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges from among the plurality of objects. The acquisition unit 131 acquires correct data indicating correct objects searched by a second search process different from the first search process, which is a search process.

The acquisition unit 131 acquires correct data indicating correct objects searched by the second search process in which the value of the search range coefficient, which is a coefficient for determining the search range, is set larger than that of the first search process. The acquisition unit 131 acquires correct data indicating correct objects retrieved by comparing the query with each of the plurality of objects.

Acquisition unit 131 acquires information about a search query. The acquisition unit 131 acquires a search query related to image search. The acquisition unit 131 acquires a query from the terminal device 10 used by the user. The acquisition unit 131 may acquire the query from the information providing device 50 that has received the query from the terminal device 10 .

In the example of FIG. 1 , the acquisition unit 131 acquires the graph GR11 from the graph information storage unit 123. FIG. The obtaining unit 131 obtains the graph GR11-1 including the nodes N1, N2, N3, N38, N43, N53, N99, etc. and the edges E1 to E3, etc. FIG. Acquisition unit 131 acquires tree information IND11 from tree information storage unit 122 .

(Generating unit 132)
The generator 132 generates various types of information. The generation unit 132 generates various information based on various information stored in the storage unit 120 . The generation unit 132 generates various types of information based on the object information storage unit 121, the tree information storage unit 122, the graph information storage unit 123, the correct data storage unit 124, and the like.

The generation unit 132 generates various information based on the various information acquired by the acquisition unit 131 . The generator 132 generates various information based on the various information selected by the selector 133 . The generation unit 132 generates various information based on the various information updated by the update unit 134 . The generator 132 may generate graph information.

The generation unit 132 generates a query based on objects selected from a plurality of objects. The generation unit 132 generates a query using an object group selected from a plurality of objects. The generation unit 132 generates a query by calculating the average of objects selected from a plurality of objects.

The generating unit 132 generates a query using a first object selected from a plurality of objects and a second object different from the first object among the plurality of objects. The generation unit 132 generates a query using a second object corresponding to a node to which edges from a first node corresponding to the first object are connected in the graph. The generation unit 132 generates a query using a second object corresponding to the farthest node or the nearest node from the first node among the nodes connected to the edge from the first node. The generation unit 132 generates a query using a second object corresponding to a node randomly selected from a node group to which edges from the first node are connected.

The generating unit 132 generates multiple queries. The generation unit 132 may generate a query based on objects registered as nodes in the graph GR11. The generation unit 132 generates correct data RD1 indicating k neighboring nodes (objects) corresponding to the query QE1 by comparing each object included as a node in the graph GR11 with the query QE1. The generation unit 132 generates neighborhood correct data as correct data.

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

The selection unit 133 selects various information based on the various information acquired by the acquisition unit 131 . The selection unit 133 determines various information based on the various information acquired by the acquisition unit 131 . The selection unit 133 selects various information based on the various information updated by the update unit 134 .

The selection unit 133 selects a selection object from the search result objects based on a predetermined criterion. The selection unit 133 selects an object closest to the target object from among the search result objects as a selection object.

The selection unit 133 selects the object OB1 closest to the object OB38 from among the objects (search result objects) in the search result RS1 as the selected object.

(Update unit 134)
The updating unit 134 updates various information. The update unit 134 updates various information based on various information stored in the storage unit 120 . The update unit 134 updates the graph stored in the graph information storage unit 123. FIG.

The updating unit 134 extracts similar nodes that are nodes similar to the search query. The update unit 134 also functions as a search unit that executes search processing using a graph.

The update unit 134 adds an additional edge connected to a target node corresponding to a target object that is not included in the search result objects searched by the graph search process using the query among the correct objects indicated by the correct data. , to update the graph. The update unit 134 executes search processing using the query generated by the generation unit 132 . The update unit 134 executes search processing using a graph in which edges from the first node to other nodes are deleted.

The updating unit 134 adds an additional edge connecting the selected node, which is the node corresponding to the selection object selected from the search result objects, and the target node. The updating unit 134 adds an additional edge connected to the target node corresponding to the target object not included in the search result objects searched by the first search process with the search range coefficient set to a value smaller than that of the second search process. do. The updating unit 134 adds an additional edge connected to a target node corresponding to a target object not included in the search result objects searched by the first search process in which the value of the search range coefficient is set to 0.

The update unit 134 generates the graph GR11-2 by adding an additional edge E11 connecting the node N1 corresponding to the object OB1 and the node N38 corresponding to the object OB38.

(Providing unit 135)
The providing unit 135 provides various information. The providing unit 135 provides various types of information to the terminal device 10 and the information providing device 50 . The providing unit 135 transmits various types of information to the terminal device 10 and the information providing device 50 .

The providing unit 135 provides the object ID corresponding to the query as a search result. The providing unit 135 provides information on similar nodes determined by the selecting unit 133 . The providing unit 135 provides the terminal device 10 and the information providing device 50 with the object ID indicating the similar node determined by the selecting unit 133 .

The providing unit 135 provides information on similar nodes extracted by the updating unit 134 . The providing unit 135 transmits information about similar nodes to the terminal device 10 used by a predetermined user. The providing unit 135 provides search results to the sender of the query.

[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. 9 . FIG. 9 is a flowchart illustrating an example of information processing according to the embodiment;

As shown in FIG. 9, the information processing apparatus 100 collects correct data indicating correct objects close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges, out of the plurality of objects. (step S101). For example, the information processing apparatus 100 acquires correct data RD1 from the correct data storage unit 124 (see FIG. 8).

Then, the information processing apparatus 100 adds an additional edge connected to the target node corresponding to the target object not included in the objects retrieved by the graph retrieval process using the query among the correct objects indicated by the correct data ( step S102). For example, the information processing apparatus 100 adds an additional edge E11 connected to the target node N38 corresponding to the target object OB38, which is not included in the objects searched by the search processing, from the correct data RD1.

[5. Flow of search processing]
Next, the flow of search processing by the information processing apparatus 100 will be described with reference to FIG. 10 as an example. FIG. 10 is a flowchart illustrating an example of search processing according to the embodiment. Specifically, FIG. 10 is a flowchart showing an example of search processing using graph data. Note that the search processing shown in FIG. 10 also includes selection processing. The search processing described below is performed by the information processing apparatus 100 . Also, the object referred to below may be read as a node. Note that the search using the graph data by the information processing apparatus 100 is not limited to the following, and may be performed by various procedures.

Here, the neighborhood set N(G,y) is the set of neighborhood objects that are related by the edges attached to node y. For example, a neighborhood set N(G, y) is a set of objects (nodes) to which edges are connected with node y. Also, when the nodes of the graph are connected by directed edges, the neighborhood set N(G, y) is a set of objects (nodes) to which output edges from node y are connected. "G" may be predetermined graph data (for example, graph GR11, etc.). For example, the information processing apparatus 100 executes k-nearest neighbor search processing.

For example, the information processing apparatus 100 sets the radius r of the hypersphere to ∞ (infinity) (step S201), and extracts the set S from the existing object set (step S202). For example, the information processing apparatus 100 may extract, as a set S, objects (nodes) determined (selected) as origin nodes. Also, for example, a hypersphere is a virtual sphere that indicates a search range. Note that the objects (nodes) included in the set S extracted in step S202 are also included in the initial set of the set R of the search results (extraction candidates). Also, the objects (nodes) included in the set S extracted in step S202 may be included in the set C. FIG. Set C is provided for convenience in order to avoid duplicate searches, and may be set to an empty set at the start of processing.

Next, the information processing apparatus 100 extracts an object having the shortest distance from the object y, where y is the search query object, among the objects included in the set S, and sets it as an object s (step S203). For example, in the example of FIG. 1, the information processing apparatus 100 extracts one node as the object s (target node) from the set S including the node N2, which is the origin node corresponding to the query QE1, which is the object y. . Next, the information processing apparatus 100 excludes the object s from the set S (step S204). For example, in the example of FIG. 1, the information processing apparatus 100 excludes from the set S the node N2, which is the starting node.

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 S205). Here, ε is an expansion factor, and r(1+ε) is a value that indicates the radius of the search range (only nodes within this range are searched; making it larger than the search range increases the accuracy). be. If the distance d(s, y) between object s and object y exceeds r(1+ε) (step S205: Yes), information processing apparatus 100 outputs set R as a neighborhood set of object y (step S206). , terminate the process.

When the distance d(s, y) between the object s and the search query object y does not exceed r(1+ε) (step S205: No), the information processing apparatus 100 determines the neighborhood set N(G, s) of the object s. One object that is not included in set C is selected from the element objects based on a predetermined criterion, and the selected object u is stored in set C (step S207). For example, in the example of FIG. 1, the information processing apparatus 100 selects the node (for example, node N43) closest to the query QE1 among the nodes N1, N43, etc., which are the connecting nodes of the node N2, as the object u.

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 S208). If the distance d(u, y) between the object u and the object y is less than or equal to r(1+ε) (step S208: Yes), the information processing apparatus 100 adds the object u to the set S (step S209). If the distance d(u, y) between the object u and the object y is not less than r(1+ε) (step S208: No), the information processing apparatus 100 performs determination (processing) in step S210.

Next, the information processing apparatus 100 determines whether or not the distance d(u, y) between the object u and the object y is less than or equal to r (step S210). When the distance d(u, y) between the object u and the object y exceeds r, the information processing apparatus 100 performs determination (processing) in step S216. If the distance d(u, y) between the object u and the object y is not equal to or less than r (step S210: No), the information processing apparatus 100 performs determination (processing) in step S216.

When the distance d(u, y) between the object u and the object y is less than or equal to r (step S210: Yes), the information processing apparatus 100 adds the object u to the set R (step S211). The information processing apparatus 100 then determines whether or not the number of objects included in the set R exceeds ks (step S212). The predetermined number ks is an arbitrarily determined natural number. For example, ks indicates the number of extractions in a search, and may be any value such as "3", "20", or "100". When the number of objects included in the set R does not exceed ks (step S212: No), the information processing apparatus 100 performs determination (processing) in step S214.

When the number of objects included in the set R exceeds ks (step S212: Yes), the information processing apparatus 100 selects an object having the longest (farthest) distance from the object y among the objects included in the set R. (step S213).

Next, the information processing apparatus 100 determines whether or not the number of objects included in the set R matches ks (step S214). If the number of objects included in the set R does not match ks (step S214: No), the information processing apparatus 100 performs determination (processing) in step S216. If the number of objects included in the set R matches ks (step S214: Yes), the information processing apparatus 100 selects the object with the longest (farthest) distance from the object y among the objects included in the set R. , to the object y is set to a new r (step S215).

Then, the information processing apparatus 100 determines whether or not all objects have been selected from objects that are elements of the neighborhood set N(G, s) of the object s (step S216). If all the objects that are elements of the neighborhood set N(G, s) of the object s have not been selected (step S216: No), the information processing apparatus 100 returns to step S207 and repeats the process. Note that the information processing apparatus 100 is not limited to selecting all of the objects that are elements of the neighborhood set N(G, s) of the object s. You may choose.

When all objects are selected from the objects that are elements of the neighborhood set N(G, s) of the object s (step S216: Yes), the information processing apparatus 100 determines whether the set S is an empty set. (Step S217). If the set S is not an empty set (step S217: No), the information processing apparatus 100 returns to step S203 and repeats the process. If the set S is an empty set (step S217: Yes), the information processing apparatus 100 outputs the set R and ends the process (step S218). For example, the information processing apparatus 100 may select objects (nodes) included in the object set R as neighboring nodes corresponding to the target node (input object y). For example, in the example of FIG. 1, the information processing apparatus 100 outputs nodes N2, N43, N1, etc. included in the set R as search results corresponding to the query QE1 (input object y). Further, for example, the information processing apparatus 100 may provide objects (nodes) included in the set R as search results corresponding to the search query (input object y) to the terminal apparatus 10 or the like that performed the search.

[6. Modification]
The information processing system 1 according to the above-described embodiments may be implemented in various different modes other than the above-described embodiments. For example, a process of adding a node (hereinafter also referred to as a “virtual node”) that is not associated with any object to be searched may be performed. Therefore, another embodiment of the above information processing system 1 will be described below. Note that the same reference numerals are assigned to the same points as in the above-described embodiment, and the description thereof is omitted as appropriate. For example, the information processing system 1 according to the embodiment and the information processing system according to the modified example have the same configuration except for the difference between the information processing device 100 and the information processing device 100A. Information processing by the information processing apparatus 100A will be described below.

[6-1. information processing]
First, information processing in the information processing system according to the modification will be described with reference to FIG. 11 . FIG. 11 is a diagram illustrating an example of information processing according to the modification. Specifically, FIG. 11 describes an example of processing for adding a virtual node.

11 that are the same as those in FIG. 1 are denoted by the same reference numerals, and description thereof will be omitted as appropriate. Steps S11 to S14 in FIG. 11 are the same processing as in FIG. 1, so description thereof will be omitted. In FIG. 11, the information processing apparatus 100A adds the virtual node and the additional edge with the node N38 corresponding to the object OB38, which is the target object, as the target node.

The information processing device 100A selects a node to be connected with the virtual node connected to the target node (step S25). Then, the information processing device 100A arranges a virtual node between the selected node and the target node, adds an additional edge between the target node and the virtual node, and adds an edge between the selected node and the virtual node. is added to update the graph (step S26).

In the example of FIG. 11, the information processing device 100A selects the object OB1 closest to the object OB38 among the objects (search result objects) in the search result RS1 as the selected object. Information processing apparatus 100A arranges a virtual node between node N1 corresponding to object OB1 and node N38 corresponding to object OB38. Information processing apparatus 100A arranges a virtual node at a position corresponding to the average vector of object OB1 and object OB38. In the example of FIG. 11, the information processing device 100A adds the virtual node VN1 to the midpoint between the node N1 and the node N38, as shown in the graph GR11-3.

The information processing apparatus 100A then adds an edge E101, which is an additional edge connecting between the node N38 corresponding to the object OB38 and the virtual node VN1. The information processing apparatus 100A also adds an edge E102 connecting the virtual node VN1 and the node N1 corresponding to the object OB1. Thus, the information processing device 100A generates the graph GR11-3 by adding the virtual node VN1, the edge E101, and the edge E102. Accordingly, the information processing device 100A updates the graph GR11.

Note that the method of adding virtual nodes is not limited to the above, and virtual nodes may be added by various methods. For example, the information processing apparatus 100A may place the virtual node at an appropriate position, not limited to the middle point between the selected node and the target node. Further, the information processing apparatus 100A may connect an edge to the virtual node VN1 in addition to the edge E101 and the edge E102. For example, the information processing device 100A may search the graph GR11 using the virtual node VN1 as a query, and add an edge between the virtual node VN1 and a node that approximates the virtual node VN1.

As described above, the information processing apparatus 100A sets an object, which is not included in the search result object, among the correct objects indicated by the correct answer data as the target object, and adds an additional edge or virtual node connected to the target node corresponding to the target object. to add. In this manner, the information processing apparatus 100A can appropriately generate a graph by adding virtual nodes and additional edges for connecting to nodes corresponding to missing objects.

[6-2. Configuration of Information Processing Device]
Next, the configuration of the information processing apparatus 100A according to the modification will be described using FIG. FIG. 12 is a diagram illustrating a configuration example of an information processing apparatus according to a modification; As shown in FIG. 12, the information processing device 100A has a communication section 110, a storage section 120A, and a control section 130A. Regarding the information processing apparatus 100A, descriptions of the same points as those of the information processing apparatus 100 according to the embodiment will be omitted as appropriate.

(Storage unit 120A)
The storage unit 120A is realized by, for example, a semiconductor memory device such as a RAM (Random Access Memory) or a flash memory, or a storage device such as a hard disk or an optical disk. The storage unit 120A according to the embodiment has an object information storage unit 121, a tree information storage unit 122, a graph information storage unit 123AA, and a correct data storage unit 124, as shown in FIG.

(Graph information storage unit 123A)
123 A of graph information storage parts which concern on embodiment memorize|store various information regarding a graph. For example, the graph information storage unit 123A stores graph information used for information processing such as search processing. In the example of FIG. 13, the graph information storage unit 123A stores graph data including virtual nodes. FIG. 13 is a diagram illustrating an example of a graph information storage unit according to a modification; The graph information storage unit 123A shown in FIG. 13 has items such as "node ID", "object ID", "edge information", and "real node flag". "Edge information" includes information such as "edge ID" and "reference destination".

“Node ID” indicates identification information for identifying each node (object) in graph data. "Object ID" indicates identification information for identifying an object.

"Edge information" indicates information about edges connected to the corresponding node. In the example of FIG. 13, "edge information" indicates information about undirected edges (bidirectional edges) connected to the corresponding node. "Edge ID" indicates identification information for identifying an edge connecting nodes. "Reference destination" indicates information indicating a reference destination (node) connected by an edge. That is, in the example of FIG. 13, a node ID identifying a node is associated with information identifying an object (object) corresponding to the node and a reference destination (node) to which an edge from the node is connected. registered with

"Real node flag" indicates whether or not the node is a virtual node. That is, the "real node flag" indicates whether or not the node is associated with an object. A node associated with an object, that is, a node that is not a virtual node may be referred to as a "real node". The "real node flag" indicates that the node is a virtual node when the value is "0", and indicates that the node is not a virtual node when the value is "1". That is, when the "real node flag" is "1", it indicates that the node is associated with an object and has a corresponding object. Also, when the "real node flag" is "0", it indicates that the node is not associated with any object and has no corresponding object.

In the example of FIG. 13, the nodes (nodes N1 to N3) identified by the node IDs "N1" to "N3" each have a real node flag of "1" and are associated with objects instead of virtual nodes. indicates that it is a real node with

Also, in the example of FIG. 13, the node (node VN1) identified by the node ID "VN1" has an object ID of "null", indicating that there is no associated object. Also, from the node VN1, an edge (edge E101) identified by the edge ID "E101" is connected to a node (node N38) identified by the node ID "N38". That is, the example of FIG. 13 indicates that the node N38 can be traced from the node VN1 in the graph information through the edge E101. The node VN1 has a real node flag of "0", indicating that it is a virtual node.

It should be noted that the graph information storage unit 123A may store various types of information, not limited to the above, depending on the purpose. For example, the graph information storage unit 123A may store lengths of edges connecting nodes (vectors). That is, the graph information storage unit 123A may store information indicating distances between nodes (vectors). The graph information storage unit 123A may store not only graph information connected by undirected edges but also various kinds of graph information. Graph information connected by directed edges may be stored in the graph information storage unit 123A.

(Control section 130A)
Returning to the description of FIG. 12, the control unit 130A is a controller, and various programs (corresponding to an example of an information processing program) stored in a storage device inside the information processing apparatus 100 are executed by, for example, a CPU, an MPU, or the like. It is realized by being executed using RAM as a work area. Also, the control unit 130A is a controller, and is implemented by an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array).

As shown in FIG. 12, the control unit 130A includes an acquisition unit 131, a generation unit 132, a selection unit 133A, an update unit 134A, and a provision unit 135, and has information processing functions and actions described below. realize or perform Note that the internal configuration of the control unit 130A is not limited to the configuration shown in FIG. 12, and may be another configuration as long as it performs the information processing described later.

(Selection unit 133A)
133 A of selection parts which concern on a modification perform the same process as the selection part 133 which concerns on embodiment. 133 A of selection parts select a selection object from a search result object based on a predetermined reference|standard. The selection unit 133A selects an object closest to the target object from among the search result objects as a selection object.

The selection unit 133A selects a node that connects with the virtual node that is connected to the target node. The selection unit 133A selects the object OB1 closest to the object OB38 from among the objects (search result objects) in the search result RS1 as the selected object.

(Update unit 134A)
The updating unit 134A according to the modification performs the same processing as the updating unit 134 according to the embodiment. The updating unit 134A adds a virtual node, which is a node not associated with a plurality of objects, to the graph, and adds an additional edge connecting the virtual node and the target node. The updating unit 134A adds an edge connecting between a selection node, which is a node corresponding to a selection object selected from search result objects, and a virtual node.

The updating unit 134A arranges a virtual node between the node N1 corresponding to the object OB1 and the node N38 corresponding to the object OB38. The updating unit 134A arranges the virtual node at the position corresponding to the average vector of the object OB1 and the object OB38. The updating unit 134A adds the virtual node VN1 to the midpoint between the node N1 and the node N38, as shown in the graph GR11-3. The updating unit 134A adds an edge E101, which is an additional edge connecting between the node N38 corresponding to the object OB38 and the virtual node VN1. The updating unit 134A adds an edge E102 connecting the virtual node VN1 and the node N1 corresponding to the object OB1. The update unit 134A performs processing for adding additional edges by the search processing shown in FIG. Further, when performing a search service using a graph including virtual nodes, the update unit 134A extracts objects to be provided to the user as search results by the search processing shown in FIG.

[6-3. Flow of search processing]
When providing a search service using a graph to which virtual nodes are added as described above, the information processing apparatus 100A performs a search according to a search processing flow as shown in FIG. This point will be described with reference to FIG. FIG. 14 is a flowchart illustrating an example of search processing according to the modification. FIG. 14 is a flowchart showing a processing procedure for searching for real nodes using a graph including virtual nodes, which is executed by the information processing apparatus 100A according to the modification. The object referred to below may be read as a node. Note that the search for real nodes using graph data having virtual nodes by the information processing apparatus 100A is not limited to the following, and may be performed by various procedures.

Here, the neighborhood set N(G,y) is the set of neighborhood objects that are related by the edges attached to node y. For example, a neighborhood set N(G, y) is a set of objects (nodes) to which edges are connected with node y. Also, when the nodes of the graph are connected by directed edges, the neighborhood set N(G, y) is a set of objects (nodes) to which output edges from node y are connected. "G" may be predetermined graph data (for example, graph G1, graph G2). For example, the information processing device 100A executes k-nearest neighbor search processing.

For example, the information processing device 100A sets the radius r of the hypersphere to ∞ (infinity) (step S301), and extracts the set S from the existing object set (step S302). For example, the information processing device 100A may extract, as a set S, objects (nodes) determined (selected) as starting nodes. Also, for example, a hypersphere is a virtual sphere that indicates a search range. The objects (nodes) included in the set S extracted in step S302 are also included in the initial set of the set R of the search results (extraction candidates). Also, the objects (nodes) included in the set S extracted in step S302 may be included in the set C. Set C is provided for convenience in order to avoid duplicate searches, and may be set to an empty set at the start of processing.

Next, the information processing apparatus 100A extracts an object having the shortest distance from the object y, where y is the search query object, among the objects included in the set S, and sets it as an object s (step S303). In the specific example described above with reference to FIG. 1, the search query object is the image feature of an image of a floral yukata. Next, the information processing device 100A excludes the object s from the set S (step S304).

Next, the information processing device 100A determines whether or not the distance d(s, y) between the object s and the object y exceeds r(1+ε) (step S305). Here, ε is an expansion factor, and r(1+ε) is a value that indicates the radius of the search range (only nodes within this range are searched; making it larger than the search range increases the accuracy). be. When the distance d(s, y) between the object s and the object y exceeds r(1+ε) (step S305: Yes), the information processing device 100A outputs the set R as a neighborhood set of the object y (step S306). , terminate the process. In the particular example described above with reference to FIG. 1, the neighborhood set is the set of nodes corresponding to fashion items that look similar to the floral yukata depicted in the image.

When the distance d(s, y) between the object s and the search query object y does not exceed r(1+ε) (step S305: No), the information processing device 100A determines the neighborhood set N(G, s) of the object s. One object that is not included in set C is selected from the element objects based on a predetermined criterion, and the selected object u is stored in set C (step S307).

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

Next, the information processing device 100A determines whether or not the object u is a real node (that is, the object u is not a virtual node) (step S310). If the object u is not a real node (step S310: No), the information processing device 100A performs determination (processing) in step S317.

If the object u is a real node (step S310: Yes), the information processing device 100A determines whether or not the distance d(u, y) between the object u and the object y is less than or equal to r (step S311). . When the distance d(u, y) between the object u and the object y exceeds r, the information processing device 100A performs determination (processing) in step S317. If the distance d(u, y) between the object u and the object y is not equal to or less than r (step S311: No), the information processing device 100A performs determination (processing) in step S317.

If the distance d(u, y) between the object u and the object y is less than or equal to r (step S311: Yes), the information processing device 100A adds the object u to the set R (step S312). Then, the information processing device 100A determines whether or not the number of objects included in the set R exceeds ks (step S313). The predetermined number ks is an arbitrarily determined natural number. For example, ks indicates the number of extractions in a search, and may be any value such as "3", "20", or "100". When the number of objects included in the set R does not exceed ks (step S313: No), the information processing apparatus 100A performs determination (processing) in step S315.

When the number of objects included in the set R exceeds ks (step S313: Yes), the information processing apparatus 100A selects an object having the longest (farthest) distance from the object y among the objects included in the set R. (step S314).

Next, the information processing device 100A determines whether or not the number of objects included in the set R matches ks (step S315). When the number of objects included in the set R does not match ks (step S315: No), the information processing apparatus 100A performs determination (processing) in step S317. Further, when the number of objects included in the set R matches ks (step S315: Yes), the information processing apparatus 100A selects the object having the longest (farthest) distance from the object y among the objects included in the set R. , to the object y is set to a new r (step S316).

Then, the information processing device 100A determines whether or not all objects have been selected from objects that are elements of the neighborhood set N(G, s) of the object s (step S317). If all the objects that are elements of the neighborhood set N(G, s) of the object s have not been selected (step S317: No), the information processing device 100A returns to step S307 and repeats the process. Note that the information processing apparatus 100A is not limited to selecting all of the objects that are elements of the neighborhood set N(G, s) of the object s. You may choose.

When all objects are selected from the objects that are elements of the neighborhood set N(G, s) of the object s (step S317: Yes), the information processing device 100A determines whether the set S is an empty set. (Step S318). If the set S is not an empty set (step S318: No), the information processing device 100A returns to step S303 and repeats the process. If the set S is an empty set (step S318: Yes), the information processing device 100A outputs the set R and ends the process (step S319). For example, the information processing device 100A may select objects (nodes) included in the object set R as neighboring nodes corresponding to the target node (input object y). For example, the information processing device 100A may provide objects (nodes) included in the set R as search results corresponding to the search query (input object y) to the terminal device 10 or the like that requested the search.

[7. effect〕
As described above, the information processing apparatuses 100 and 100A according to the embodiments or modifications have the acquisition unit 131 and the update units 134 and 134A. The acquiring unit 131 acquires correct data indicating a correct object close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges from among the plurality of objects. The updating units 134 and 134A add additional edges connected to target nodes corresponding to target objects not included in the search result objects searched by the graph search process using the query among the correct objects indicated by the correct data. to update the graph.

As described above, the information processing apparatus 100 or 100A according to the embodiment or the modified example performs the search process, and among the correct objects, the additional nodes corresponding to the target objects that are not included in the retrieved search result objects are connected to the target nodes. By adding an edge, the graph can be updated appropriately by adding an edge that traces to the target node. Therefore, the information processing apparatuses 100 and 100A can generate an appropriate graph by adding edges.

Further, the information processing apparatuses 100 and 100A according to the embodiment or modifications have a generation unit 132 . The generation unit 132 generates a query based on objects selected from a plurality of objects. The updating units 134 and 134A execute search processing using the query generated by the generating unit 132. FIG.

As described above, the information processing apparatus 100 or 100A according to the embodiment or the modified example adds additional edges based on the search results using the generated query, thereby generating an appropriate graph by adding edges. can.

In addition, in the information processing apparatuses 100 and 100A according to the embodiments or modifications, the generation unit 132 generates a query using an object group selected from a plurality of objects.

In this way, the information processing apparatuses 100 and 100A according to the embodiments or modifications can appropriately generate queries by generating queries using a plurality of objects.

In addition, in the information processing apparatuses 100 and 100A according to the embodiments or modifications, the generation unit 132 generates a query by calculating the average of objects selected from a plurality of objects.

In this way, the information processing apparatuses 100 and 100A according to the embodiments or modifications can appropriately generate queries by generating queries using the average of multiple objects.

Further, in the information processing device 100 or 100A according to the embodiment or the modification, the generation unit 132 generates a first object selected from a plurality of objects and a second object different from the first object among the plurality of objects. to generate a query.

In this way, the information processing apparatuses 100 and 100A according to the embodiment or the modification use a first object selected from a plurality of objects and a second object different from the first object to generate a query, Able to properly generate queries.

Further, in the information processing device 100 or 100A according to the embodiment or the modification, the generation unit 132 uses the second object corresponding to the node to which the edge from the first node corresponding to the first object in the graph is connected, Generate queries.

In this way, the information processing apparatuses 100 and 100A according to the embodiment or the modified example correspond to the first object selected from a plurality of objects and the node where the edges from the first node corresponding to the first object are connected. By using the second object to generate the query, the query can be generated appropriately.

Further, in the information processing apparatuses 100 and 100A according to the embodiment or the modification, the generation unit 132 selects the farthest node or the nearest node from the first node in the node group to which the edge from the first node is connected. A query is generated using the corresponding second object.

In this way, the information processing device 100 or 100A according to the embodiment or the modification uses the second object corresponding to the farthest or nearest node in the node group to which the edge from the first object is connected, and executes the query. By generating it, you can properly generate the query.

Further, in the information processing device 100 or 100A according to the embodiment or the modification, the generation unit 132 uses a second object corresponding to a node randomly selected from a node group to which edges from the first node are connected, Generate queries.

In this way, the information processing device 100 or 100A according to the embodiment or modification generates a query using the second object corresponding to the node randomly selected from the node group to which the edge from the first object is connected. so that you can properly generate the query.

In addition, in the information processing apparatuses 100 and 100A according to the embodiments or modifications, the update units 134 and 134A execute search processing using graphs in which edges from the first node to other nodes are deleted.

As described above, the information processing apparatus 100 or 100A according to the embodiment or the modification performs search processing using a graph in which edges from the first node corresponding to the first object used in the query are deleted, thereby obtaining appropriate search results. , and the addition of edges can generate a suitable graph.

Further, in the information processing apparatus 100 according to the embodiment, the update unit 134 adds an additional edge connecting the selected node, which is the node corresponding to the selected object selected from the search result objects, and the target node.

As described above, the information processing apparatus 100 according to the embodiment can generate an appropriate graph by connecting the selected node corresponding to the selection object selected from the search result objects and the target node with the additional edge. .

The information processing apparatus 100 according to the embodiment also has a selection unit 133 . The selection unit 133 selects a selection object from the search result objects based on a predetermined criterion.

As described above, the information processing apparatus 100 according to the embodiment can connect appropriate nodes with additional edges by selecting selected objects from search result objects based on a predetermined criterion, and generates an appropriate graph. be able to.

Further, in the information processing apparatus 100 according to the embodiment, the selection unit 133 selects an object closest to the target object from among the search result objects as the selection object.

As described above, the information processing apparatus 100 according to the embodiment selects an object closest to the target object from among the search result objects as a selected object, thereby connecting appropriate nodes with additional edges. Graphs can be generated.

Further, in the information processing device 100A according to the modification, the update unit 134A adds a virtual node, which is a node not associated with a plurality of objects, to the graph, and adds an additional edge connecting the virtual node and the target node. Add

As described above, the information processing apparatus 100A according to the modification adds a virtual node that is a node that is not associated with a plurality of objects, and connects the virtual node and the target node with an additional edge. graphs can be generated.

Further, in the information processing apparatus 100A according to the modification, the updating unit 134A adds an edge connecting between the selected node, which is the node corresponding to the selected object selected from the search result objects, and the virtual node.

In this way, the information processing apparatus 100A according to the modification can generate an appropriate graph by connecting the selection node corresponding to the selection object selected from the search result objects and the virtual node with edges. .

Further, the information processing device 100A according to the modification has a selection unit 133A. 133 A of selection parts select a selection object from a search result object based on a predetermined reference|standard.

In this way, the information processing apparatus 100A according to the modification can connect appropriate nodes with additional edges by selecting selected objects from the search result objects based on a predetermined criterion, thereby generating an appropriate graph. be able to.

Further, in the information processing apparatus 100A according to the modification, the selection unit 133A selects an object closest to the target object from among the search result objects as the selection object.

As described above, the information processing apparatus 100A according to the embodiment selects an object closest to the target object from among the search result objects as the selection object, thereby connecting appropriate nodes with the additional edge. Graphs can be generated.

In addition, in the information processing apparatuses 100 and 100A according to the embodiments or modifications, the acquisition unit 131 acquires correct data indicating correct objects searched by a second search process different from the first search process, which is a search process. .

In this manner, the information processing apparatus 100, 100A according to the embodiment or the modified example can appropriately generate a graph by updating the graph using the correct object searched by the predetermined search process.

Further, in the information processing device 100 or 100A according to the embodiment or the modified example, the obtaining unit 131 sets the value of the search range coefficient, which is a coefficient for determining the search range, to be larger than that of the first search process. Acquire correct data indicating the correct object searched by the search process. The updating units 134 and 134A add additional edges connected to target nodes corresponding to target objects that are not included in the search result objects searched by the first search process whose search range coefficient is set to a value smaller than that of the second search process. Add

As described above, the information processing apparatus 100 or 100A according to the embodiment or the modified example generates correct data in the second search process in which the value of the search range coefficient is larger than that in the first search process, and performs the search in the first search process. By using it for comparison with the result, edges can be added to nodes that are omitted from the search when the search range coefficient is small. Therefore, the information processing apparatuses 100 and 100A according to the embodiments or modifications can generate an appropriate graph by adding edges.

In addition, in the information processing apparatuses 100 and 100A according to the embodiment or the modification, the updating units 134 and 134A are not included in the search result objects searched by the first search process in which the value of the search range coefficient is set to 0. Add additional edges that connect to the target node corresponding to the target object.

In this way, the information processing device 100 or 100A according to the embodiment or modification can add edges to nodes that are omitted from the search when the value of the search range coefficient is set to 0. Therefore, the information processing apparatuses 100 and 100A according to the embodiments or modifications can generate an appropriate graph by adding edges.

In addition, in the information processing apparatuses 100 and 100A according to the embodiment or the modification, the acquisition unit 131 acquires correct data indicating correct objects retrieved by comparing the query with each of the plurality of objects.

In this way, the information processing apparatuses 100 and 100A according to the embodiment or the modification update the graph using the correct data retrieved by comparing the query with each of the plurality of objects, so that the graph is appropriately updated. can be generated.

Further, in the information processing apparatuses 100 and 100A according to the embodiment or the modified examples, the update units 134 and 134A are configured to perform search processing in which the value of the search range coefficient, which is a coefficient for determining the search range, is set to 0. Add additional edges connecting target nodes corresponding to target objects not included in the search result objects.

In this way, the information processing device 100 or 100A according to the embodiment or modification can add edges to nodes that are omitted from the search when the value of the search range coefficient is set to 0. Therefore, the information processing apparatuses 100 and 100A according to the embodiments or modifications can generate an appropriate graph by adding edges.

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

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

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

The CPU 1100 controls output devices such as displays and printers, and input devices such as keyboards and mice, through an input/output interface 1600 . CPU 1100 acquires data from an input device via input/output interface 1600 . CPU 1100 also outputs the generated data to an output device via input/output interface 1600 .

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

For example, when the computer 1000 functions as the information processing apparatus 100 according to the embodiment, the CPU 1100 of the computer 1000 implements the functions of the control unit 130 by executing programs 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 via the network N from another device.

As described above, some of the embodiments of the present application have been described in detail based on the drawings, but these are merely examples, and various modifications, It is possible to carry out the invention in other forms with modifications.

[9. others〕
Further, among the processes described in the above embodiments, all or part of the processes described as being automatically performed can be manually performed, or the processes described as being performed manually can be performed manually. All or part of this can also be done automatically by known methods. 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 drawing is not limited to the illustrated information.

Also, each component of each device illustrated is functionally conceptual, and does not necessarily need to be physically configured as illustrated. In other words, the specific form of distribution and integration of each device is not limited to the one shown in the figure, and all or part of them can be functionally or physically distributed and integrated in arbitrary units according to various loads and usage conditions. Can be integrated and configured.

Further, each process described in each embodiment described above can be appropriately combined within a range in which the contents of the process are 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 acquisition means or an acquisition circuit.

1 information processing system 100, 100A information processing device 120, 120A storage unit 121 object information storage unit 122 tree information storage unit 123, 123A graph information storage unit 124 correct data storage unit 130, 130A control unit 131 acquisition unit 132 generation unit 133, 133A selecting unit 134, 134A updating unit 135 providing unit 10 terminal device 50 information providing device N network

Claims (18)

an acquisition unit that acquires correct data indicating a correct object close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges, from among a plurality of objects;
By adding an additional edge connected to a target node corresponding to a target object not included in the search result objects searched by the search processing of the graph using the query, among the correct objects indicated by the correct data, an updating unit that updates the graph;
with
The updating unit
a first process of adding the additional edge connecting between a selected node, which is a node corresponding to a selected object selected from the search result object, and the target node, or a process associated with the plurality of objects; adding to the graph a virtual node that is a non-existent node; adding the additional edge connecting between the virtual node and the target node; An information processing apparatus, characterized by executing at least one of a second process of adding an edge connecting between a node and the virtual node . a generator that generates the query based on an object selected from the plurality of objects;
further comprising
The updating unit
The information processing apparatus according to claim 1, wherein the search processing is executed using the query generated by the generation unit. The generating unit
The information processing apparatus according to claim 2, wherein the query is generated using an object group selected from the plurality of objects. The generating unit
The information processing apparatus according to claim 3, wherein the query is generated by calculating an average of an object group selected from the plurality of objects. The generating unit
3. The query is generated using a first object selected from the plurality of objects and a second object different from the first object among the plurality of objects. 5. The information processing device according to 4. The generating unit
6. The information processing according to claim 5, wherein said query is generated using said second object corresponding to a node to which edges from a first node corresponding to said first object are connected in said graph. Device. The generating unit
generating the query by using the second object corresponding to the farthest node or the nearest node from the first node among the nodes to which edges from the first node are connected; The information processing device according to claim 6 . The generating unit
7. The information processing apparatus according to claim 6, wherein said query is generated using said second object corresponding to a node randomly selected from a group of nodes to which edges from said first node are connected. . The updating unit
9. The information processing apparatus according to any one of claims 6 to 8, wherein said search processing is executed using said graph in which edges from said first node to other nodes are deleted. a selection unit that selects the selected object from the search result objects based on a predetermined criterion;
The information processing apparatus according to any one of claims 1 to 9, further comprising: The selection unit
11. The information processing apparatus according to claim 10 , wherein an object closest to the target object is selected from among the search result objects as the selected object. The acquisition unit
The information according to any one of claims 1 to 11 , wherein the correct data indicating the correct object searched by a second search process different from the first search process, which is the search process, is obtained. processing equipment. The acquisition unit
obtaining the correct data indicating the correct object searched by the second search process in which the value of the search range coefficient, which is a coefficient for determining the search range, is set larger than that of the first search process;
The updating unit
The additional edge connected to the target node corresponding to the target object not included in the search result objects searched by the first search process with the search range coefficient set to a value smaller than that of the second search process. The information processing apparatus according to claim 12 , characterized by adding. The updating unit
adding the additional edge connected to the target node corresponding to the target object not included in the search result objects searched by the first search process in which the value of the search range coefficient is set to 0. 14. The information processing apparatus according to claim 13 . The acquisition unit
The information processing apparatus according to any one of claims 1 to 14 , wherein the correct data indicating the correct object retrieved by comparing the query with each of the plurality of objects is obtained. The updating unit
The additional edge connected to the target node corresponding to the target object not included in the search result objects searched by the search processing with a search range coefficient value set to 0, which is a coefficient for determining the search range. The information processing apparatus according to claim 15 , further comprising: A computer-executed information processing method comprising:
an obtaining step of obtaining correct data indicating a correct object close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges among a plurality of objects;
By adding an additional edge connected to a target node corresponding to a target object not included in the search result objects searched by the search processing of the graph using the query, among the correct objects indicated by the correct data, an updating step of updating the graph;
including
The updating step includes:
a first process of adding the additional edge connecting between a selected node, which is a node corresponding to a selected object selected from the search result object, and the target node, or a process associated with the plurality of objects; adding to the graph a virtual node that is a non-existent node; adding the additional edge connecting between the virtual node and the target node; performing at least one of a second process of adding an edge connecting between a node and the virtual node
An information processing method characterized by: an acquisition procedure for acquiring correct data indicating a correct object close to a query used for searching a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges among a plurality of objects;
By adding an additional edge connected to a target node corresponding to a target object not included in the search result objects searched by the search processing of the graph using the query, among the correct objects indicated by the correct data, an update procedure for updating the graph;
on the computer, and
The update procedure includes:
a first process of adding the additional edge connecting between a selected node, which is a node corresponding to a selected object selected from the search result object, and the target node, or a process associated with the plurality of objects; adding to the graph a virtual node that is a non-existent node; adding the additional edge connecting between the virtual node and the target node; An information processing program, characterized by executing at least one of a second process of adding an edge connecting between a node and the virtual node .

Images