JP7208955B2 - Information processing device, information processing method, information processing program, information retrieval device, information retrieval method, and information retrieval program - Google Patents

Description

Application of Patent Law Article 30, Paragraph 2 Publication date March 25, 2020 Page that publishes software related to this application as of August 7, 2020 https://github. com/yahoojapan/NGT/releases/tag/v1.10.0

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

Conventionally, techniques for performing approximate searches using various indexes have been provided. For example, there is provided a technique for performing approximate search using a graph index in which nodes are connected by directed edges and undirected edges. Such approximate retrieval techniques are used, for example, in image retrieval.

JP 2011-090351 A Japanese Patent No. 5208001 Japanese Patent No. 6293335

However, with the above-described conventional techniques, it may be difficult to perform an approximate search using appropriate parameter values. For example, a user who performs an approximate search usually has standards (evaluation indices) that require desired search accuracy, search time, and the like. Therefore, in order to perform an approximate search that satisfies the user's desired evaluation index, it is necessary to repeat trial and error, such as adjusting the parameters and measuring the evaluation index, to obtain the parameters that provide the desired search accuracy and search time. . As described above, it is very costly for the user to obtain the parameters for satisfying the evaluation index desired by the user, and there is a possibility that appropriate parameters cannot be obtained depending on the method of trial and error.

The present application has been made in view of the above, and provides an information processing device, an information processing method, an information processing program, an information search device, an information search method, and information that enable approximate search using appropriate parameter values. The purpose is to provide a search program.

An information processing apparatus according to the present application includes a designated value for designating an evaluation index value for approximate search using an index for searching a plurality of objects, and a parameter value used in the approximate search corresponding to the evaluation index value. and a conversion unit for converting the specified value of the evaluation index into the value of the parameter used in the approximate search based on the conversion information acquired by the acquisition unit. and

According to one aspect of the embodiment, there is an effect that it is possible to perform an approximate search using appropriate parameter values.

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

Embodiments for implementing the information processing device, information processing method, information processing program, information retrieval device, information retrieval method, and information retrieval program according to the present application (hereinafter referred to as "embodiments") are described below with reference to the drawings. will be described in detail. The information processing apparatus, information processing method, information processing program, information search apparatus, information search method, and information search program according to the present application are not limited to the embodiments. 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]
Information processing executed by the information processing apparatus 100 will be described below with reference to FIGS. 1 and 2 . In the following, an approximate search using a graph index (also simply referred to as a "graph") will be described as an example of an approximate search using an index. Any approximate search may be used. For example, approximate search using an index (simply referred to as "approximate search") includes approximate search using Cartesian product quantization, approximate search using hash, and tree structure index (also referred to as "tree index"). It may be an approximate search or the like. That is, the index used for approximate search is not limited to graphs, but may be tree indexes, indexes used for approximate search using direct product quantization such as codebooks, or indexes used for approximate search using hash such as hash tables. good too.

For example, an approximate search is a search that can cause search omissions, and is a search that approximates correct search results. Approximate search is a concept including approximate neighborhood search in which, for a search query (also simply referred to as “query”), objects close to the query are searched from multiple objects to be searched, and search omissions may occur. In the following, an approximate neighborhood search for retrieving an object having a vector similar to the vector of the search target object from a plurality of search target objects for a search target object used as a query is shown as an example of approximate search.

In addition, although the details will be described later, the recall rate will be described as an example of the search accuracy of approximate search using an index, but the search accuracy is not limited to the recall rate. may be Note that the evaluation index is not limited to search accuracy, and various indices such as search time, number of distance calculations, number of node accesses, and the like may be used. In the following, the search range coefficient will be described as an example of a parameter used in approximate search, but the parameter is not limited to the search range coefficient. number of edges). Details of the search range coefficient will be described later.

In the following, an example of information (also referred to as "conversion information") indicating parameter values used in approximate search corresponding to evaluation index values is shown in a lookup table that indicates the correspondence relationship between search accuracy and search range coefficient. shown as The conversion information is not limited to a lookup table, as long as the value of the evaluation index can be converted to the value of the parameter. It may be various information.

[2-1. Generation process]
From now on, the process of generating a lookup table, which is an example of conversion information (also referred to as "generation process"), will be described with reference to FIG. FIG. 1 is a diagram illustrating an example of information processing according to an embodiment.

In the example of FIG. 1, the information processing apparatus 100 uses a data set DS1 that includes a plurality of objects such as objects OB1, OB2, OB3, and OB101, and uses a lookup table that converts search accuracy values into search range coefficient values. Generate TB1 (see FIG. 2). Each object in the data set DS1 is vectorized, and various processes such as a search process, which will be described later, are performed on the vectorized object (vector information). The information (object) contained in the data set DS1 to be searched may be any information as long as it can be expressed as a vector. In the following description, vector information for image information (also simply referred to as "image") will be described, but vector information may be for other objects such as moving image information and audio information.

Further, the information used by the information processing apparatus 100 is not limited to vectors, and may be information of any format as long as it is information that can express the similarity of each target. For example, the information processing apparatus 100 may use graph information in which objects are graph-structured using predetermined data and values corresponding to each object. For example, the information processing apparatus 100 may use graph information in which an object is graph-structured using a predetermined numerical value (for example, a binary value or a hexadecimal value) generated from each object. For example, instead of vectors, any form of data may be used as long as the distance (similarity) between data is defined. For example, the information processing device 100 acquires the data set DS1 from the object information storage unit 121 (see FIG. 6).

First, the information processing apparatus 100 determines an evaluation query (step S1). The information processing device 100 generates a query object set from a given data set. The information processing apparatus 100 determines an object randomly selected from a data set or an average value of two or more randomly selected objects as a query object (evaluation query). Thereby, the information processing apparatus 100 can set an object not included in the data set as an evaluation query.

In the example of FIG. 1, the information processing apparatus 100 selects an object to be used for generating an evaluation query from the data set DS1. For example, the information processing apparatus 100 randomly selects a predetermined number of two or more objects as evaluation objects from the data set DS1. The information processing apparatus 100 selects two objects, an object OB500 and an object OB1000, from the data set DS1 as evaluation objects. Then, the information processing apparatus 100 generates multidimensional vector information of "7, 35, 13, 93..." which is the average of the object OB500 and the object OB1000. Thus, in the example of FIG. 1, the information processing apparatus 100 generates the query QE1 based on the object OB500 and the object OB1000, as shown in the evaluation query RQ1. As a result, the information processing apparatus 100 determines the query QE1, which is multidimensional vector information of “7, 35, 13, 93, . . . ”, as an evaluation query.

Note that the above is just an example, and the information processing apparatus 100 may determine an evaluation query using various types of information as appropriate. The information processing apparatus 100 may use the average of a plurality of nearby points as the evaluation query. The information processing apparatus 100 may determine the average value of more than two objects, for example three objects, as the query object (evaluation query). The plurality of objects for which the average value is to be obtained may be one randomly selected object and one or more selected objects close to the object.

The information processing apparatus 100 may also generate a query object (evaluation query) using one object (selected object) selected from the data set DS1 and objects other than the selected object. When there is a generated graph, the information processing apparatus 100 uses a node (selection node) corresponding to a selected object and an object corresponding to a node to which an edge from the selected node is connected to generate an evaluation query. may be generated. For example, the information processing apparatus 100 generates an evaluation query using a node (selection node) corresponding to a selection object and an object (connection object) corresponding to a node to which an edge from the selection node is connected. may For example, the information processing apparatus 100 may determine the average value of the selected object and the closest object among the connection objects as the evaluation query. For example, the information processing apparatus 100 may determine the average value of the selected object and the farthest object among the connected objects as the evaluation query. For example, the information processing apparatus 100 may determine the average value of the selected object and all connected objects as the evaluation query. Note that the information processing apparatus 100 may select the selection object at random, or may select it based on a predetermined criterion.

Further, for example, when some objects in the data set are used for graph generation, which will be described later, the information processing apparatus 100 may use objects in the data set that are not included in the graph as the evaluation query. The information processing apparatus 100 may prepare an object that is not registered in the graph (index) and use it as an evaluation query. The information processing apparatus 100 may delete nodes corresponding to some objects from the generated graph and use the objects corresponding to the deleted nodes as the evaluation query. Alternatively, a vector may be generated after generating random data according to the data distribution for each dimension.

The information processing device 100 then generates a graph (step S2). The information processing apparatus 100 creates a graph for all or part of the given data set. For example, the information processing apparatus 100 may generate a graph using all objects in the data set DS1, or may generate a graph using some objects in the data set DS1. As described above, the information processing apparatus 100 may generate a graph using a group of objects in the data set DS1 excluding objects used as evaluation objects. The information processing apparatus 100 may generate a graph using an object group excluding the object OB500 and the object OB1000 in the data set DS1 used as the object for evaluation.

In the example of FIG. 1, the information processing apparatus 100 uses all objects in the data set DS1 to generate the graph GR11. The information processing apparatus 100 appropriately uses various techniques related to graph generation to generate the graph GR11. Here, graph GR11 will be described. A graph GR11 shown in FIG. 1 represents graph information in which nodes corresponding to objects included in the data set DS1 are connected by directed edges. Graph information such as graph GR11 in FIG. 1 is not limited to the case where information processing apparatus 100 generates graph information, and information processing apparatus 100 generates graph information such as graph GR11 in FIG. 50 (see FIG. 4) or other external device.

Also, the term "directed edge" used herein means an edge that allows data to be traced in only one direction. In the following description, the source traced by the edge, that is, the node that is the starting point, is the reference source, and the destination that is traced by the edge, that is, the node that is the end point, is the reference destination. For example, a directed edge connecting a predetermined node "A" to a predetermined node "B" indicates an edge having a reference source of node "A" and a reference destination of node "B". Edges connecting nodes are not limited to directed edges, and may be various edges. For example, the edge connecting each node may be a directionless edge connecting the nodes. For example, the edges connecting each node may be mutually referable edges. For example, all edges connecting nodes may be undirected edges (bidirectional edges).

For example, an edge having node "A" as a reference in this way is called an output edge of node "A". Further, for example, an edge having the node "B" as a reference in this way is referred to as an input edge of the node "B". In other words, the term "output edge" and "input edge" as used herein refers to the difference in which of the two nodes to which one directed edge connects is regarded as the center. An edge becomes an outgoing edge and an incoming edge. In other words, an output edge and an input edge are relative concepts. For one directed edge, it is an output edge when the reference node is regarded as the center, and the reference node is regarded as the center. is an input edge. Note that, in the present embodiment, directed edges such as output edges and input edges are targeted for edges, and therefore directed edges may be simply referred to as "edges" below. Also, each node here corresponds to each object. For example, each of the multiple local features extracted from the image may be an object. Also, for example, various data in which distances between objects are defined may be objects.

Graph GR11 in FIG. 1 includes a large number of objects (nodes) in data set DS1, but only some of them are illustrated in the drawing. For example, the information processing apparatus 100 generates graph information including a plurality of nodes (vectors) such as nodes N1 to N3, N43, and N53, as indicated by graph GR11 in FIG. In the example of FIG. 1, to simplify the explanation, five nodes are illustrated to explain the outline of the processing, but the graph GR11 includes the number of nodes corresponding to the number of objects in the data set DS1. .

In the example of FIG. 1, for example, the information processing apparatus 100 generates the graph GR11 such that a predetermined number or more of output edges from each node corresponding to each object are connected to other edges. The information processing apparatus 100 generates the graph GR11 such that each node in the graph GR11 is connected to a predetermined number of edges (output edges) from the closest node to the node. For example, the predetermined number may be various values such as 2, 5, 10, 100, etc., depending on the number of objects or the purpose and application of the graph. For example, if the predetermined number is 2, output edges from the node N1 are connected to the closest node and the second closest two nodes from the node N1. Note that the distance as an index indicating similarity may be any distance as long as it is applicable as the distance between vectors (N-dimensional vectors). For example, various distances such as Euclidean distance and Mahalanobis distance may be used. For example, the distance may be any information that reflects the degree of similarity between two objects, such as angle information such as cosine similarity.

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".

In graph GR11 in FIG. 1, node N1 is connected to edge E2, which is a directed edge toward node N53. That is, node N1 is connected to node N53 by edge E2. When "edge E* (* is an arbitrary numerical value)" is described in this way, it indicates that the edge is identified by the edge ID "E*". For example, when "edge E31" is described, the edge is identified by the edge ID "E31". For example, it is possible to trace from the node N1 to the node N53 by the edge E2 connecting the node N1 as the reference source and the node N53 as the reference destination. In this case, edge E2, which is a directed edge, is an output edge when identified centering on node N1, and an input edge when identified centering on node N53.

In other words, edge E2, which is a directed edge, is an edge with an arrow pointing to another edge, that is, an outward edge when viewed from the node N1 side, and viewed from the node N53 side. , it is an edge with an arrow pointing toward it, that is, an inward edge. In other words, the output edge here can be read as an outward edge, and the input edge can be read as an inward edge. Although not shown in FIG. 1, the node N53 may be connected to a directed edge (referred to as edge E531) directed to the node N1. Thus, edge E531, which is an output edge from node N53, may be connected to node N1. In this case, there are two edges between the node N1 and the node N53: an edge E2 that is a directed edge from the node N1 to the node N53 and an edge E531 that is a directed edge from the node N53 to the node N1. are concatenated.

Graph GR11 in FIG. 1 may be Euclidean space. 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.

In the example of FIG. 1, in the graph GR11, the illustration of "node N* (* is an arbitrary number)" is omitted as appropriate, and "* ” value. That is, "*" in "node N*" corresponds to a matching node. For example, the upper left "o" in the graph GR11 and "o" with "43" inside corresponds to the node (node N43) identified by the node ID "N43".

Here, the distance between each node indicates the similarity of the nodes (images), 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 images 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 above is just an example, and the information processing apparatus 100 may generate graphs using various conditions. For example, the information processing apparatus 100 may generate the graph GR11 such that a predetermined number or more of input edges from each node corresponding to each object are connected from other edges.

Then, the information processing device 100 acquires an approximate correct search result (step S3). The information processing apparatus 100 acquires approximate correct search results for the query QE1. The information processing apparatus 100 uses the query QE1 to acquire an approximate correct search result indicating a result of extracting k (k is an arbitrary number) nodes as approximate nodes. The information processing apparatus 100 acquires the approximate correct search result corresponding to the query QE1 from the approximate correct search result information storage unit 124 (see FIG. 9).

Here, to generate an accurate correct search result, it is necessary to calculate the distances to all objects, which cannot be done in a realistic amount of time for large datasets. Therefore, when the information processing apparatus 100 generates approximate correct search results, instead of obtaining correct search results for evaluation queries, approximate search results are obtained in advance using some evaluation target index. For example, the information processing apparatus 100 appropriately uses various techniques related to approximate search (neighborhood search) to generate approximate correct search results corresponding to query QE1.

For example, the information processing apparatus 100 generates an approximate correct search result corresponding to the query QE1 through the process shown in FIG. In this case, the information processing apparatus 100 sets the value of the search range coefficient “ε” (to be described later) to a value greater than or equal to a predetermined value (referred to as “value for correct answer generation”), and performs a search as shown in FIG. By performing processing using the graph GR11, an approximate correct search result corresponding to the query QE1 is generated. Thereby, the information processing apparatus 100 can shorten the processing time compared to the case where the correct information is generated by calculating the distances to all the objects. Note that the above is just an example, and if the information processing apparatus 100 can generate approximate correct search results in a shorter processing time than calculating the distances to all objects and generating correct information, what kind of The processing may generate approximate correct search results.

Here, the concept of the search range coefficient "ε" will be briefly explained. Graph GR11-1 in FIG. 1 is the graph GR11, and only the nodes are illustrated to illustrate the range AR1 and the range AR2 corresponding to the query QE1 in which "Q" is written in "○". Illustration is omitted. The information processing apparatus 100 searches the graph GR11 using a range AR1 centered on the query QE1 within a radius r and a range AR2 centered on the query QE1 within a radius r(1+ε) to extract approximate nodes. do. In this way, the information processing apparatus 100 performs processing for extracting approximate nodes by applying the search range coefficient “ε”. Details of the processing using the search range coefficient “ε” will be described with reference to FIG. 12 . .

The derivation of the correct answer generating value of the above-mentioned coefficient "ε" will be described. First, when using the approximate correct search result and the correct answer data, it is desirable to set the search range coefficient "ε" to a value for correct answer generation larger than a predetermined value. increases. Therefore, it is necessary to obtain a search range coefficient "ε" that can obtain sufficient accuracy and that has a value as small as possible. 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 to the approximate correct search result (correct answer). data) is the value of the search range coefficient “ε” used when obtaining the data. 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 approximate search is The second value when no new objects appear is used as the value of the search range coefficient when generating approximate correct search results. 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 approximate correct search result (correct answer data) is generated, and is performed by an apparatus other than the information processing apparatus 100. may

In the example of FIG. 1, the information processing device 100 generates an approximate correct search result RR1 corresponding to the query QE1. As shown in the approximate correct search result RR1, the approximate correct answer information corresponding to the query QE1 has a No of "1", indicating that the closest node is the node corresponding to the object OB101. Also, the approximate correct answer information corresponding to query QE1 indicates that No is "k", that is, the farthest node (farthest object) is the node corresponding to object OB55. The information processing apparatus 100 uses the approximate correct search result RR1 to perform processing such as measurement processing, which will be described later.

Then, the information processing device 100 sets the value of the parameter (step S4). The information processing apparatus 100 sets the value of the search range coefficient “ε”, which is a parameter, to an initial value (for example, 0 or 0.01). Hereinafter, the values of the set parameters may be used as measurement target values. In FIG. 1, the information processing apparatus 100 sets the measurement target value of the search range coefficient "ε" to "VL21".

Then, the information processing apparatus 100 performs a measurement process of measuring the evaluation index of the graph GR11 using the set parameter value (measurement target value) (step S5). Thereby, the information processing apparatus 100 can obtain the value of the evaluation index of the graph GR11 when the parameter is set as the measurement target value. In the example of FIG. 1, the information processing apparatus 100 performs a measurement process of measuring the retrieval accuracy, which is the reproducibility of the graph GR11, using the set value of the retrieval range coefficient "ε".

The recall here is obtained by "(result actually searched among correct search results)/(correct search result)". That is, the recall rate is calculated by dividing the "results actually searched among the correct search results" in the search process whose accuracy is to be measured by the "correct search results". Note that parameters other than the search range coefficient “ε” may be set values (default values) when the graph GR11 is used. For example, the number of reference edges may be set to a value covering all edges, or may be set to a predetermined value.

The information processing apparatus 100 performs a search process on the evaluation query using the measurement target values of the set parameters, and calculates the recall rate as the search accuracy using the extracted search results. The information processing apparatus 100 may measure the time of the search processing. Specifically, the information processing apparatus 100 performs the search process shown in FIG. 12 to acquire approximate nodes of the evaluation query. Then, the information processing apparatus 100 compares the approximate node acquired by the search process with the approximate correct search result, thereby obtaining the value of the search accuracy (recall rate) for the set search range coefficient “ε” as the measurement target value. to measure. In FIG. 1, the information processing apparatus 100 measures the value of the search accuracy (recall rate) to be “VL11” when the value of the search range coefficient “ε” is “VL21”.

Then, the information processing apparatus 100 associates and stores the parameter value and the evaluation index value (step S6). As shown in lookup table TB1-1, information processing apparatus 100 associates value "VL21" of search range coefficient "ε" with value "VL11" of search accuracy, which is a recall rate, and stores them.

The information processing apparatus 100 also determines whether or not the generation of conversion information has been completed (step S7). For example, the information processing apparatus 100 uses a threshold value (for example, 10 times or 50 times) and determines that conversion information has been generated when the number of times the measurement process is repeated is equal to or greater than the threshold value.

When the information processing apparatus 100 determines that the generation of the conversion information has not been completed (step S7: No), the information processing apparatus 100 changes the parameter value (step S8). For example, the information processing apparatus 100 changes the measurement target value of the parameter. In FIG. 1, the information processing apparatus 100 changes the measurement object value of the search range coefficient "ε" by increasing the measurement object value of the search range factor "ε" by a predetermined value. For example, the information processing apparatus 100 changes the measurement target value of the search range coefficient "ε" from "VL21" to "VL22". Then, the information processing apparatus 100 returns to step S5 and repeats the process using the changed measurement object value. The information processing apparatus 100 ends the process when the generation of the conversion information is completed (step S7: Yes). As a result, the information processing apparatus 100 generates a lookup table TB1 (see FIG. 2) showing the correspondence relationship between the search accuracy and the search range coefficient. In this way, the information processing apparatus 100 changes the value of the search range coefficient “ε”, which is a parameter for searching, to obtain search accuracy and creates a lookup table.

As described above, the information processing apparatus 100 changes the value of the parameter and repeats the process of measuring the evaluation index, so that the change-necessary information for deriving the value of the parameter corresponding to the value of the evaluation index can be obtained appropriately. can be generated to Note that the lookup table generated by the information processing apparatus 100 is not limited to a lookup table of one evaluation index and one parameter, that is, a two-dimensional lookup table as shown in FIG. It may be a multi-dimensional lookup table that is larger than the dimension. For example, the information processing apparatus 100 converts the value of the evaluation index “retrieval accuracy” into a combination of the value of the first parameter “retrieval range coefficient” and the values of the second parameters “reference edge count” and “retrieval count”. A three-dimensional lookup table may be generated for use in Thus, when there are two parameters, the information processing apparatus 100 may change the two parameters, measure the search accuracy, and generate a three-dimensional lookup table. Note that the above is an example, and the information processing apparatus 100 may perform various processes to generate various lookup tables.

[2-2. Search processing]
Search processing using the lookup table TB1 generated by the generation processing shown in FIG. 1 will now be described with reference to FIG. FIG. 2 is a diagram illustrating an example of information processing according to the embodiment; The example of FIG. 2 shows a case where the information processing device 100 provides search results to the terminal device 10 in response to a query acquired from the terminal device 10 . For example, the information processing apparatus 100 provides an image search service for searching (extracting) k (for example, 5) vectors that are close to the query.

In the example of FIG. 2, the information processing apparatus 100 performs an approximate search using a graph generated for the data set DS1 shown in the graph data GD1. The graph of graph data GD1 may be graph GR11.

First, the information processing device 100 acquires information indicating the specified value of the evaluation index for approximate search using a graph from the terminal device 10 used by the user U1 (step S21). In the example of FIG. 2, the information processing apparatus 100 acquires the designated value “VL11-2” of the search precision (recall rate) from the terminal device 10. In the example of FIG. For example, the information processing device 100 acquires an image from the terminal device 10 as the query QE21.

Based on the lookup table TB1, the information processing apparatus 100 converts the designated value "VL11-2" of the search precision into the value of the search range coefficient "ε" (step S22). For example, when the lookup table TB1 includes a specified value of search accuracy, the information processing apparatus 100 uses the value of the search range coefficient "ε" associated with the specified value.

Further, when the lookup table TB1 does not include the specified value of the search accuracy, the information processing apparatus 100 generates the value of the search range coefficient "ε" corresponding to the specified value based on the lookup table TB1. The information processing apparatus 100 refers to the lookup table TB1 by the specified value "VL11-2" of the search accuracy specified at the time of the search, and performs an interpolation process of interpolating the discrete values of the lookup table TB1 to obtain the search range coefficient "ε". to find the value of Note that the interpolation processing may be linear interpolation. Further, the information processing apparatus 100 may calculate an approximation function in advance from the lookup table TB1, and obtain the value of the search range coefficient "ε" using the approximation function. In this case, the information processing apparatus 100 acquires the approximation function stored in the storage unit 120 (see FIG. 5) as the conversion information, and uses the acquired approximation function to set the specified value of the search accuracy to the search range coefficient "ε ” value. Accordingly, the information processing apparatus 100 may obtain the value of the search range coefficient “ε” from the designated value of the search precision using an approximation function.

In FIG. 2, since the lookup table TB1 does not include the specified value of the search accuracy, the information processing apparatus 100 performs the interpolation process from the specified value of the search accuracy “VL11-2” to the value of the search range coefficient “ε”. VL21-2” is obtained. As a result, the information processing apparatus 100 converts the search accuracy designation value "VL11-2" into the value "VL21-2" of the search range coefficient "ε", as shown in the post-conversion information CV.

Then, the information processing device 100 acquires a query from the terminal device 10 used by the user U1 (step S23). In the example of FIG. 2, the information processing device 100 acquires the query QE21 from the terminal device 10. In the example of FIG. For example, the information processing device 100 acquires an image from the terminal device 10 as the query QE21. Note that the information processing apparatus 100 may collectively acquire (receive) the specified value of the search accuracy and the query from the terminal apparatus 10 .

Then, the information processing apparatus 100 sets the value of the search range coefficient "ε" to "VL21-2", and executes approximate search processing using the graph of the graph data GD1 for the query QE21 (step S24). . The information processing apparatus 100 sets the value of the search range coefficient “ε” to “VL21-2”, performs the search processing shown in FIG. Get a node. For example, the information processing apparatus 100 extracts a predetermined number (for example, 5) of approximate nodes (approximate objects) for the query QE21 by searching the graph of the graph data GD1.

Then, the information processing device 100 provides information indicating the extracted approximate object to the terminal device 10 as a search result (step S25). For example, the information processing apparatus 100 provides the terminal device 10 with a predetermined number (for example, 5) of extracted images that are similar objects as images similar to the query QE21 specified by the user U1.

In this way, the user designates the value of the evaluation index such as the desired search accuracy or the search time instead of designating the parameter at the time of the search. Convert to parameter value. Thereby, the information processing apparatus 100 can perform an approximate search using appropriate parameter values. For example, even if the user himself/herself cannot set a parameter value for satisfying the criteria of the desired evaluation index, the information processing apparatus 100 uses an appropriate parameter value according to the user's request. can enable approximate searches.

Then, the information processing apparatus 100 searches using the converted parameter values. That is, the information processing apparatus 100 performs a search after converting the specified values of search accuracy and search time specified by the user into parameter values. Accordingly, the information processing apparatus 100 can execute an approximate search using appropriate parameter values. Note that the above is just an example, and the information processing apparatus 100 may use various conversion information such as a conversion function instead of the lookup table.

[2-3. tree index]
In the above example, only graphs are used, but the information processing apparatus 100 may use various indexes such as a tree index to speed up processing. For example, the information processing apparatus 100 may use a tree index IND11 as shown in the information group GINF11 in FIG. 3 to determine a node serving as the starting point of the search (hereinafter also referred to as "starting node"). FIG. 3 is a diagram showing an example of a tree index. Note that the tree index IND11 may be generated by the information processing device 100, or the information processing device 100 may acquire the tree index IND11 from another external device such as the information providing device 50 or the like.

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

For example, the information processing apparatus 100 determines the starting node in the graph GR11 using a tree structure type tree index such as the tree index 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 index IND11 by tracing the tree index 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 index 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 index 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 down the tree index IND11 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 index (tree data) shown in the example of FIG. 3 is an example, and the information processing apparatus 100 may search for graph information using various tree indexes. 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 index) 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 a tree index IND11 relating to 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).

Further, 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.

Further, the information processing apparatus 100 may perform an approximate search using only a tree-structured index such as the tree index IND11. For example, the information processing apparatus 100 performs an approximate search using a tree index (tree index TX) in which each of a plurality of search targets is a leaf of the tree. In this case, for the query QE1, a leaf node reached by following the tree index TX is extracted as an approximate node. That is, when the query QE1 is given, the information processing apparatus 100 performs approximate search for searching for nodes that are similar to the query QE1 by tracing the tree index TX from the root to the leaves. In this case, the parameter may be the number of branches to follow (the number of branches).

[3. Configuration of information processing system]
As shown in FIG. 4 , the information processing system 1 includes a terminal device 10 , an information providing device 50 and an information processing device 100 . The terminal device 10, the information providing device 50, and the information processing device 100 are connected via a predetermined network N so as to be communicable by wire or wirelessly. FIG. 4 is a diagram illustrating a configuration example of an information processing system according to the embodiment; The information processing system 1 shown in FIG. 4 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 processing apparatus 100 is a computer that converts a designated value that designates an evaluation index value for an approximate search using an index that searches for a plurality of objects into a parameter value that is used for the approximate search. Further, the information processing apparatus 100 is an information retrieval apparatus that executes an approximate retrieval using an index using a parameter value obtained by converting a designated value of an evaluation index.

The information processing apparatus 100 stores information for providing various information to users and the like. For example, the information processing apparatus 100 provides an image search service to users and the like. In this case, the information processing apparatus 100 stores each information for providing an image search service. For example, the information processing apparatus 100 provides an image search service for searching for images related to transaction objects traded in electronic commerce services provided by the information providing apparatus 50 . That is, the data set DS1 may be an object related to a transaction subject to be traded in the electronic commerce service provided by the information providing device 50. FIG.

The information processing apparatus 100 extracts objects similar to the query by approximate search. For example, when 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 search results to the terminal device. The information processing device 100 performs an approximate search using the query received from the terminal device 10 and transmits the result to the terminal device 10 .

The data provided by the information processing device 100 to the terminal device may be data itself such as an image, or may be information for referring to corresponding data such as a URL (Uniform Resource Locator). 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.

The information providing device 50 is an information processing device that provides electronic commerce services to users. The information providing device 50 provides various information to the information processing device 100 . The information providing device 50 provides the information processing device 100 with information on the transaction objects traded in the electronic commerce service. The information providing device 50 provides the information processing device 100 with an image of a transaction object to be traded in the electronic commerce service and vector data of the image.

Note that the information providing device 50 may be integrated with the information processing device 100 . The information providing device 50 may also store object IDs based on images and the like collected from various external devices such as web servers. For example, the information providing device 50 may provide the information processing device 100 with vector information corresponding to an image for which an image search service is to be performed.

[4. Configuration of Information Processing Device]
Next, the configuration of the information processing apparatus 100 according to the embodiment will be described using FIG. FIG. 5 is a diagram illustrating a configuration example of the information processing apparatus 100 according to the embodiment. As shown in FIG. 5, 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. 4) 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. As shown in FIG. 5, the storage unit 120 according to the embodiment includes an object information storage unit 121, a tree information storage unit 122, a graph information storage unit 123, an approximate correct search result information storage unit 124, and conversion information. and a storage unit 125 .

(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. 6 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. 6 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. 6, 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. 6, 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. 7 is a diagram illustrating an example of a tree information storage unit according to the embodiment; FIG. Specifically, in the example of FIG. 7, the tree information storage unit 122 indicates a tree index of a tree structure. In the example of FIG. 7, 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. 7, 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. 8, the graph information storage unit 123 stores neighborhood graph data. 8 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. 8 has items such as "node ID", "object ID", and "directed edge information". "Directed 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.

"Directed edge information" indicates information about edges connected to the corresponding node. In the example of FIG. 8, "directed edge information" indicates information about the output edge output from 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. 8, for a node ID that identifies a node, a reference destination ( node) are associated and registered.

The example of FIG. 8 indicates that the node (node N1) identified by the node ID "N1" corresponds to the object (object) 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. 8 indicates that the node N2 can be traced from the node N1 in the graph information through the edge E1.

Also, the example of FIG. 8 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 node N2, an edge (edge E21) identified by edge ID "E21" is connected to a node (node N1) identified by node ID "N1". That is, the example of FIG. 8 indicates that the node N1 can be traced from the node N2 by the edge E21 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 directed edges, but also various kinds of graph information. The graph information storage unit 123 may store graph information connected by undirected edges.

(approximate correct search result information storage unit 124)
The approximate correct search result information storage unit 124 according to the embodiment stores various types of information regarding approximate correct search. The approximate correct search result information storage unit 124 stores approximate correct answer information used for measuring accuracy of search processing when using each query. For example, the approximate correct search result information storage unit 124 stores k approximate nodes of the query in association with each query as approximate correct search results. 9 is a diagram illustrating an example of an approximate correct search result information storage unit according to the embodiment; FIG. The approximate correct search result information storage unit 124 shown in FIG. 9 has items such as "query ID", "vector information", and "approximate correct search result". The "approximate correct search result" 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. "Approximate correct search result" stores the approximate correct search result used as approximate correct answer information of the corresponding query. "No" indicates the rank of each approximate node of the corresponding query. "Object" indicates an approximate node (object) of corresponding rank.

The example of FIG. 9 indicates that the query (query QE1) identified by the query ID "QE1" is multidimensional vector information of "7, 35, 13, 93...". The approximate correct answer information corresponding to query QE1 indicates that No is "1", that is, the nearest node is the node corresponding to object OB101. Also, the approximate correct answer information corresponding to query QE1 indicates that No is "k", that is, the farthest node (farthest object) is the node corresponding to object OB55.

It should be noted that the approximate correct search result information storage unit 124 may store various information not limited to the above, depending on the purpose. When using a plurality of pieces of graph information, the approximate correct search result information 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 approximate correct search result information storage unit 124 may associate and store the graph information using each threshold value and the corresponding threshold value.

(Conversion information storage unit 125)
The conversion information storage unit 125 according to the embodiment stores various types of information used to convert evaluation index values into parameter values. 10 is a diagram illustrating an example of a conversion information storage unit according to the embodiment; FIG. In the example of FIG. 10, the conversion information storage unit 125 stores a lookup table showing the correspondence between evaluation index values and parameter values.

The conversion information storage unit 125 stores a lookup table TB1 used for converting the value of the evaluation index "search accuracy" into the value of the parameter "search range coefficient", and stores the value of the evaluation index "processing time" as the parameter "search range coefficient , look-up table TB2 and the like used for conversion into values of . Note that the lookup table is not limited to a lookup table of one evaluation index and one parameter, that is, a two-dimensional lookup table, but may be a multidimensional lookup table larger than two dimensions, such as a three-dimensional lookup table. good too.

As shown in FIG. 6, the lookup table is used to convert the value of the evaluation index "retrieval accuracy" into a combination of the value of the first parameter "retrieval range coefficient" and the value of the second parameter "number of reference edges". A three-dimensional lookup table such as the lookup table TB3 used may be used. Also, the lookup table is a three-dimensional lookup table used to convert the combination of the value of the first evaluation index "search accuracy" and the value of the second evaluation index "processing time" into the value of the parameter "search range coefficient". It may be an up table. Note that the above is just an example, and the conversion information storage unit 125 stores various lookup tables.

A lookup table TB1 in FIG. 10 shows a lookup table showing the correspondence relationship between the value of the evaluation index "search accuracy" and the value of the parameter "search range coefficient".

The column of the evaluation index "retrieval accuracy" of the lookup table TB1 stores, for example, "VL11", "VL12", "VL13", "VL14", etc., which are retrieval accuracy values, which are recall rates. Note that in the example of FIG. 10, an abstract code such as "VL11" is used, but the search accuracy value is a specific numerical value (eg, 0.65, 0.9, etc.).

In addition, in the column of the parameter "search range coefficient" of the lookup table TB1, "VL21", "VL22", "VL23", "VL24", etc., which are the values of the search range coefficient such as "ε", are stored. be. In the example of FIG. 10, an abstract code such as "VL21" is used, but the value of the search range coefficient is a specific numerical value (for example, 0.05 or 0.2).

Thus, in the lookup table TB1, the search precision value "VL11" is associated with the search range coefficient value "VL21", and the search precision value "VL12" is associated with the search range coefficient value "VL22". Indicates that it is associated.

In the column of the evaluation index "processing time" of the lookup table TB2, "PT11", etc., which is the value of the processing time, which is the time required for the search processing, is stored. Note that in the example of FIG. 10, an abstract code such as "PT11" is used, but the value of the processing time is a specific numerical value (for example, 0.5 seconds, 30 seconds, etc.).

Also, in the column of the parameter "search range coefficient" of the lookup table TB2, "VL31", etc., which is the value of the search range coefficient, for example, "ε", is stored.

Thus, the lookup table TB2 indicates that the processing time value "PT11" is associated with the search range coefficient value "VL31".

Note that the conversion information storage unit 125 may store various types of information, not limited to the above, depending on the purpose. The conversion information storage unit 125 may store function information generated from each of the tables TB1 to TB3. For example, the conversion information storage unit 125 stores a function generated based on the correspondence relationship between the value of the evaluation index "search accuracy" and the value of the parameter "search range coefficient" in each table TB1. You can also store it with it.

(control unit 130)
Returning to the description of FIG. 5, 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 an 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. 5, the control unit 130 includes an acquisition unit 131, a generation unit 132, a conversion unit 133, a determination unit 134, a search unit 135, and a provision unit 136, and has information described below. Realize or perform the function or action of a process. Note that the internal configuration of the control unit 130 is not limited to the configuration shown in FIG. 5, and may be another configuration as long as it performs information processing 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 approximate correct search result information storage unit 124, the conversion information storage unit 125, and the like.

Acquisition unit 131 also receives 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 acquisition unit 131 acquires an index for searching a plurality of objects. The acquisition unit 131 acquires a designated value that designates a value of an evaluation index for approximate search using an index that searches for a plurality of objects. The acquisition unit 131 acquires conversion information indicating parameter values used in approximate search corresponding to evaluation index values.

The acquisition unit 131 acquires a designated value for approximate search using a graph in which a plurality of nodes corresponding to each of a plurality of objects are connected by edges as an index. The acquisition unit 131 acquires, as conversion information, a lookup table that indicates the correspondence between each value of the evaluation index and each value of the parameter. The acquisition unit 131 acquires, as conversion information, a function for inputting the value of the evaluation index and outputting a value to the parameter corresponding to the input value of the evaluation index.

The acquisition unit 131 acquires the graph GR11 from the graph information storage unit 123. FIG. The acquisition unit 131 acquires the data set DS1 from the object information storage unit 121 (see FIG. 6). Acquisition unit 131 acquires tree information IND11 from tree information storage unit 122 .

The acquisition unit 131 acquires an approximate correct search result. The acquisition unit 131 acquires approximate correct search results for the query QE1. The acquisition unit 131 acquires an approximate correct search result indicating a result of extracting k (k is an arbitrary number) nodes as approximate nodes using the query QE1. The obtaining unit 131 obtains the approximate correct search result corresponding to the query QE1 from the approximate correct search result information storage unit 124 (see FIG. 9).

The acquisition unit 131 acquires the designated value “VL11-2” of the search accuracy (recall rate) from the terminal device 10 . The acquisition unit 131 acquires the query QE21 from the terminal device 10 used by the user U1.

(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 approximate correct search result information storage unit 124, the conversion information storage unit 125, and the like. Generate.

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 converted by the converter 133 . The generation unit 132 generates various information based on the various information determined by the determination unit 134 . The generation unit 132 generates various information based on the various information extracted by the search unit 135 . The generator 132 may generate graph information.

The generation unit 132 generates a lookup table by generation processing including search processing using an index. The generation unit 132 generates a lookup table by generation processing including search processing using an evaluation query based on an evaluation object selected from a plurality of objects. The generation unit 132 generates a lookup table by a generation process including a search process using an evaluation query generated using a plurality of evaluation objects selected from a plurality of objects. The generation unit 132 generates a lookup table by a generation process including a search process that uses the average of a plurality of evaluation objects as an evaluation query.

The generation unit 132 generates an approximate correct search result that is a result of an approximate search using the evaluation query, and generates a lookup table by a generation process including a measurement process of measuring an evaluation index using the generated approximate correct search result. to generate When the index is a graph, the generation unit 132 generates an approximate correct search result by adjusting a search range coefficient, which is a coefficient for determining the search range in search processing using the graph. The generation unit 132 increases the value of the search range coefficient from the first value, and uses the second value at the time when no new object appears in the approximate search result as the search range coefficient when generating the approximate correct search result. used as the value of

The generation unit 132 generates a lookup table by a generation process including a search process using an index that searches for a group of objects excluding the evaluation object from the plurality of objects. The generation unit 132 generates a lookup table by generation processing that associates each of the plurality of values of the evaluation index obtained by the search processing using each of the plurality of values of the parameter with each of the plurality of values of the corresponding parameter. Generate.

The generation unit 132 uses a lookup table to generate a function that receives an evaluation index value and outputs a value to a parameter corresponding to the input evaluation index value. For example, the generation unit 132 inputs the value of the evaluation index “search accuracy” based on the correspondence relationship between the value of the evaluation index “search accuracy” and the value of the parameter “search range coefficient” in each table TB1, Generate a function (approximation function) that outputs the value of the parameter "search range coefficient" corresponding to the value. For example, the information processing apparatus 100 appropriately uses various techniques related to function fitting, receives the value of the evaluation index "search accuracy" as an input, and outputs the value of the parameter "search range coefficient" corresponding to the value. may be generated. Note that the above is merely an example, and the information processing apparatus 100 may generate a function by any process as long as the value of the evaluation index can be converted into the value of the parameter. Also, the approximate function generated by the information processing apparatus 100 may be a linear function or a non-linear function.

The generator 132 generates a graph. The generation unit 132 may generate the graph using all objects in the data set DS1, or may generate the graph using some objects in the data set DS1. for example. The generation unit 132 may generate the graph using some objects such as the objects OB1, OB2, and OB101, excluding the object OB3 and the like, in the data set DS1. The generator 132 uses all the objects in the data set DS1 to generate the graph GR11. The generation unit 132 appropriately uses various techniques related to graph generation to generate the graph GR11. The generation unit 132 generates graph information including a plurality of nodes (vectors) such as nodes N1 to N3, N43, and N53, as shown in graph GR11 in FIG.

The generation unit 132 generates the graph GR11 such that a predetermined number or more of output edges from each node corresponding to each object are connected to other edges. The generation unit 132 generates the graph GR11 such that each node in the graph GR11 is connected to a predetermined number of edges (output edges) from the node closest to the node.

The generation unit 132 appropriately uses various techniques related to approximate search or neighborhood search to generate an approximate correct search result corresponding to the query QE1. For example, the generation unit 132 generates an approximate correct search result corresponding to the query QE1 by performing the process shown in FIG. 12 . In this case, the generation unit 132 increases the value of the search range coefficient “ε” (to be described later) by a predetermined value or more, and performs the process shown in FIG. Generate search results. The generation unit 132 generates an approximate correct search result RR1 corresponding to the query QE1.

(Converter 133)
The conversion unit 133 converts various information. The conversion unit 133 converts various information based on the various information stored in the storage unit 120 . The conversion unit 133 converts 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 approximate correct search result information storage unit 124, the conversion information storage unit 125, and the like. Convert. The conversion unit 133 converts various information based on the various information acquired by the acquisition unit 131 . The conversion unit 133 converts various information based on the various information generated by the generation unit 132 . The conversion unit 133 converts various information based on the various information extracted by the search unit 135 . The conversion unit 133 converts various information based on the various information determined by the determination unit 134 .

Based on the conversion information acquired by the acquisition unit 131, the conversion unit 133 converts the specified value of the evaluation index into the value of the parameter used in the approximate search. The conversion unit 133 converts the designated value of the evaluation index into the value of the parameter used in the approximate search using the graph. The conversion unit 133 refers to the lookup table and converts the specified value of the evaluation index into the value of the parameter used in the approximate search. The conversion unit 133 inputs the specified value of the evaluation index into the function, thereby converting the specified value of the evaluation index into the value of the parameter used in the approximate search.

If the lookup table does not include the specified value of the evaluation index, the conversion unit 133 obtains the value of the parameter from the specified value of the evaluation index by interpolation processing. The conversion unit 133 converts the designated value “VL11-2” of the search accuracy into the value “VL21-2” of the search range coefficient “ε” by interpolation processing.

(Determination unit 134)
The determination unit 134 determines various types of information. The determination unit 134 generates various information. The determination unit 134 selects various information. The determination unit 134 determines various information based on various information stored in the storage unit 120 . The determination unit 134 determines 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 approximate correct search result information storage unit 124, the conversion information storage unit 125, and the like. decide.

The determination unit 134 determines various information based on the various information acquired by the acquisition unit 131 . The determination unit 134 determines various information based on the various information acquired by the acquisition unit 131 . The determination unit 134 determines various information based on the various information converted by the conversion unit 133 . The determination unit 134 determines various information based on the various information searched by the search unit 135 .

The determination unit 134 determines an evaluation query. The determining unit 134 selects an object to be used for generating an evaluation query from the data set DS1. The determining unit 134 randomly selects a predetermined number of two or more objects from the data set DS1 as evaluation objects. The determination unit 134 selects two objects, the object OB500 and the object OB1000, from the data set DS1 as evaluation objects.

The decision unit 134 creates a query object from the given data set. The determination unit 134 generates a query object (evaluation query) that is an object randomly selected from the data set or an average value of two or more randomly selected objects. The determination unit 134 generates multidimensional vector information of "7, 35, 13, 93..." which is the average of the object OB500 and the object OB1000. The determination unit 134 generates a query QE1 based on the object OB500 and the object OB1000, as shown in the evaluation query RQ1.

(Search unit 135)
The search unit 135 performs approximate search processing using an index. The search unit 135 searches various information based on the various information stored in the storage unit 120 . The search unit 135 retrieves 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 approximate correct search result information storage unit 124, the conversion information storage unit 125, and the like. search for. The search unit 135 searches for various information based on the various information acquired by the acquisition unit 131 . The search unit 135 searches for various information based on the various information generated by the generation unit 132 . The search unit 135 searches various information based on the various information converted by the conversion unit 133 . The search unit 135 searches various information based on the various information determined by the determination unit 134 . The search unit 135 extracts various information by searching.

The search unit 135 executes the approximate search using the parameter values obtained by converting the specified values of the evaluation index based on the conversion information. The search unit 135 extracts an approximate node, which is a node that approximates (similar to) the query. The search unit 135 searches for objects by searching graph information. When the query acquired by the acquisition unit 131 is acquired, the retrieval unit 135 retrieves an object similar to the query by searching the graph information. The search unit 135 extracts objects similar to the query by searching the graph data. The search unit 135 extracts objects similar to the query by searching the graph data based on the processing procedure shown in FIG.

The search unit 135 searches the graph GR11 using a range AR1 centered on the query QE1 within a radius r and a range AR2 centered on the query QE1 within a radius r(1+ε) to extract approximate nodes. . The search unit 135 sets the value of the search range coefficient “ε” to “VL21-2” and executes approximate search processing using the graph of the graph data GD1 for the query QE21.

(Providing unit 136)
The providing unit 136 provides various information. The providing unit 136 provides various types of information to the terminal device 10 and the information providing device 50 . The providing unit 136 transmits various information to the terminal device 10 . The providing unit 136 provides various information based on the various information extracted by the searching unit 135 .

The providing unit 136 provides information on approximate nodes extracted by the searching unit 135 . The providing unit 136 provides information about approximate nodes to the terminal device 10 (see FIG. 4) used by a predetermined user. The providing unit 136 provides search results to the sender of the query. The providing unit 136 transmits the search result to the terminal device 10 used by the user U1.

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

As shown in FIG. 11, the information processing apparatus 100 acquires a designated value that designates the value of the evaluation index for approximate search using an index that searches for a plurality of objects (step S101). For example, the information processing device 100 acquires the data set DS1 from the object information storage unit 121 (see FIG. 6).

Then, the information processing apparatus 100 acquires conversion information indicating parameter values used in approximate search corresponding to the value of the evaluation index (step S102). For example, the information processing apparatus 100 acquires the lookup table TB1 from the conversion information storage unit (see FIG. 10).

Then, the information processing apparatus 100 converts the specified value of the evaluation index into the value of the parameter used in the approximate search based on the conversion information (step S103). The information processing apparatus 100 executes an approximate search using the converted parameter values (step S104).

[6. Flow of search processing]
Next, the flow of search processing by the information processing apparatus 100 will be described with reference to FIG. 12 as an example. FIG. 12 is a flowchart illustrating an example of information processing according to the embodiment; Specifically, FIG. 12 is a flowchart showing an example of search processing using graph data. Note that the search processing shown in FIG. 12 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, the neighborhood set N(G,y) is the set of objects (nodes) to which the outgoing 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 S300), and extracts the set S from the existing object set (step S301). 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. The objects (nodes) included in the set S extracted in step S301 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 S301 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 S302). Next, the information processing apparatus 100 excludes the object s from the set S (step S303).

Next, the information processing apparatus 100 determines whether or not the distance d(s, y) between the object s and the object y exceeds r(1+ε) (step S304). Here, ε is an 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 S304: Yes), information processing apparatus 100 outputs set R as a neighborhood set of object y (step S305). , terminate the process.

If the distance d(s, y) between the object s and the search query object y does not exceed r(1+ε) (step S304: No), the information processing device 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 S306).

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

Next, the information processing apparatus 100 determines whether or not the distance d(u, y) between the object u and the object y is less than or equal to r (step S309). 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 S315. If the distance d(u, y) between the object u and the object y is not equal to or less than r (step S309: No), the information processing apparatus 100 performs determination (processing) in step S315.

If the distance d(u, y) between the object u and the object y is less than or equal to r (step S309: Yes), the information processing apparatus 100 adds the object u to the set R (step S310). Then, the information processing apparatus 100 determines whether or not the number of objects included in the set R exceeds ks (step S311). 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 S311: No), the information processing apparatus 100 performs determination (processing) in step S313.

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

Next, the information processing apparatus 100 determines whether or not the number of objects included in the set R matches ks (step S313). When the number of objects included in the set R does not match ks (step S313: No), the information processing apparatus 100 performs determination (processing) in step S315. If the number of objects included in the set R matches ks (step S313: 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 S314).

Then, the information processing apparatus 100 determines whether the number of objects corresponding to the threshold has been selected from the objects that are elements of the neighborhood set N(G, s) of the object s (step S315). Note that, when the threshold is not used, the information processing apparatus 100 may determine whether or not all objects have been selected from objects that are elements of the neighborhood set N(G, s) of the object s. If the number of objects corresponding to the threshold has not been selected from the objects that are elements of the neighborhood set N(G, s) of the object s (step S315: No), the information processing apparatus 100 returns to step S306 to perform the process. repeat.

When the number of objects corresponding to the threshold is selected from the objects that are elements of the neighborhood set N(G, s) of the object s (step S315: Yes), the information processing apparatus 100 determines whether the set S is an empty set. is determined (step S316). It should be noted that the information processing apparatus 100 selects all objects in the neighborhood set N(G, s) of the object s even before selecting objects from the neighborhood set N(G, s) of the object s up to the number corresponding to the threshold value. If the object has been selected, the process of step S316 may be performed. That is, when the number of objects in the neighborhood set N(G, s) of the object s is equal to or less than the threshold and all objects in the neighborhood set N(G, s) are selected, the information processing apparatus 100 determines Yes in step S315. You may perform the process of step S316 similarly to the case where it is. If the set S is not an empty set (step S316: No), the information processing apparatus 100 returns to step S302 and repeats the process. If the set S is an empty set (step S316: Yes), the information processing apparatus 100 outputs the set R and ends the process (step S317). 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.

[7. effect〕
As described above, the information processing apparatus 100 according to the embodiment has the acquisition unit 131 and the conversion unit 133 . The acquisition unit 131 acquires a specified value that specifies the value of the evaluation index for approximate search using an index that searches for multiple objects, and conversion information that indicates the value of the parameter used in the approximate search corresponding to the value of the evaluation index. and get. Based on the conversion information acquired by the acquisition unit 131, the conversion unit 133 converts the specified value of the evaluation index into the value of the parameter used in the approximate search.

As described above, the information processing apparatus 100 according to the embodiment converts the value of the designated evaluation index into the value of the parameter used in the approximate search, thereby obtaining the value of the parameter corresponding to the value of the designated evaluation index. can be properly derived. Therefore, the information processing apparatus 100 can enable approximate retrieval using appropriate parameter values.

Further, in the information processing apparatus 100 according to the embodiment, the acquisition unit 131 acquires a designated value for approximate search using, as an index, a graph in which a plurality of nodes corresponding to each of a plurality of objects are connected by edges. The conversion unit 133 converts the designated value of the evaluation index into the value of the parameter used in the approximate search using the graph.

As described above, the information processing apparatus 100 according to the embodiment converts the value of the specified evaluation index into the value of the parameter used in the approximate search using the graph, thereby corresponding to the value of the specified evaluation index. Parameter values can be derived appropriately.

Further, in the information processing apparatus 100 according to the embodiment, the parameter is a search range coefficient that is a coefficient for determining a search range in search processing using a graph.

As described above, the information processing apparatus 100 according to the embodiment appropriately derives the value of the search range coefficient, which is a coefficient for determining the search range in the search process using the graph, from the value of the specified evaluation index. be able to. Therefore, the information processing apparatus 100 can perform approximate searches using appropriate search range coefficient values.

Further, in the information processing apparatus 100 according to the embodiment, the acquisition unit 131 acquires a lookup table indicating the correspondence between each value of the evaluation index and each value of the parameter as conversion information. The conversion unit 133 refers to the lookup table and converts the specified value of the evaluation index into the value of the parameter used in the approximate search.

As described above, the information processing apparatus 100 according to the embodiment refers to the lookup table and converts the specified value of the evaluation index into the value of the parameter used in the approximate search, thereby corresponding to the value of the specified evaluation index. It is possible to appropriately derive the values of the parameters to be used.

Further, the information processing apparatus 100 according to the embodiment has a generation unit 132 . The generation unit 132 generates a lookup table by generation processing including search processing using an index.

As described above, the information processing apparatus 100 according to the embodiment generates the lookup table, refers to the lookup table, and appropriately derives the parameter value corresponding to the designated evaluation index value. can be done.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 132 generates a lookup table by generation processing including search processing using an evaluation query based on an evaluation object selected from a plurality of objects.

As described above, the information processing apparatus 100 according to the embodiment can appropriately generate a lookup table through search processing using an evaluation query based on an evaluation object selected from a plurality of objects.

In addition, in the information processing apparatus 100 according to the embodiment, the generation unit 132 performs look Generate an uptable.

As described above, the information processing apparatus 100 according to the embodiment can appropriately generate a lookup table by a search process using an evaluation query generated from a plurality of evaluation objects selected from a plurality of objects. can.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 132 generates a lookup table by a generation process including a search process using the average of a plurality of evaluation objects as an evaluation query.

In this way, the information processing apparatus 100 according to the embodiment can appropriately generate a lookup table through search processing using an average of multiple evaluation objects as an evaluation query.

In addition, in the information processing apparatus 100 according to the embodiment, the generation unit 132 generates approximate correct search results that are results of approximate searches using the evaluation query, and measures an evaluation index using the generated approximate correct search results. A lookup table is generated by a generation process including a measurement process.

As described above, the information processing apparatus 100 according to the embodiment can appropriately generate a lookup table by measuring an evaluation index using approximate correct search results.

Further, in the information processing apparatus 100 according to the embodiment, when the index is a graph, the generation unit 132 adjusts the search range coefficient, which is a coefficient for determining the search range in search processing using the graph. , to generate approximate correct search results.

As described above, when the index is a graph, the information processing apparatus 100 according to the embodiment measures the evaluation index using the approximate correct search result generated by adjusting the search range coefficient, thereby appropriately adjusting the lookup table. can be generated to

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 132 increases the value of the search range coefficient from the first value, and sets the second value at the time when no new object appears in the approximate search result to Used as the value of the search range coefficient when generating approximate correct search results.

As described above, the information processing apparatus 100 according to the embodiment appropriately generates a lookup table by varying the value of the search range coefficient and deriving a search range coefficient suitable for generating approximate correct search results. be able to.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 132 generates a lookup table by a generation process including a search process using an index in which a group of objects excluding an evaluation object from a plurality of objects is a search target. Generate.

As described above, the information processing apparatus 100 according to the embodiment can appropriately generate a lookup table by a search process in which a group of objects other than the evaluation object is searched from the plurality of objects.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 132 converts each of the plurality of values of the evaluation index obtained by the search process using each of the plurality of values of the parameter into the plurality of values of the corresponding parameter. A lookup table is generated by a generation process associated with each of .

In this manner, the information processing apparatus 100 according to the embodiment can appropriately generate a lookup table by associating each parameter value with each evaluation index value.

Further, in the information processing apparatus 100 according to the embodiment, the generation unit 132 uses a lookup table to generate a function that outputs a value to a parameter corresponding to the input evaluation index value. Generate.

As described above, the information processing apparatus 100 according to the embodiment uses a lookup table to generate a function that receives an evaluation index value as an input and outputs a value to a parameter corresponding to the input evaluation index value. be able to.

Further, in the information processing apparatus 100 according to the embodiment, the acquisition unit 131 acquires, as conversion information, a function that outputs a value to a parameter corresponding to the input evaluation index value by inputting the value of the evaluation index. The conversion unit 133 inputs the specified value of the evaluation index into the function, thereby converting the specified value of the evaluation index into the value of the parameter used in the approximate search.

As described above, the information processing apparatus 100 according to the embodiment inputs the specified value of the evaluation index into the function, and converts the specified value of the evaluation index into the value of the parameter used in the approximate search. The value of the parameter corresponding to the value can be appropriately derived.

The information processing apparatus 100 according to the embodiment also has a search unit 135 . The search unit 135 executes the approximate search using the parameter values obtained by converting the specified values of the evaluation index based on the conversion information.

As described above, the information processing apparatus 100 according to the embodiment performs approximate search using parameter values obtained by converting specified values of evaluation indices based on conversion information, thereby obtaining appropriate parameter values. You can perform an approximate search using

Also, in the information processing apparatus 100 according to the embodiment, the evaluation index is the search accuracy of the search process using the index.

As described above, the information processing apparatus 100 according to the embodiment converts the search accuracy value of the search process using the index into the value of the parameter used in the approximate search, thereby corresponding to the designated search accuracy value. Parameter values can be derived appropriately. Therefore, the information processing apparatus 100 can enable approximate retrieval using appropriate parameter values.

Further, in the information processing apparatus 100 according to the embodiment, the evaluation index is the processing time of search processing using the index.

As described above, the information processing apparatus 100 according to the embodiment converts the value of the processing time of the search process using the index into the value of the parameter used in the approximate search, thereby corresponding to the value of the specified processing time. Parameter values can be derived appropriately. Therefore, the information processing apparatus 100 can enable approximate retrieval using appropriate parameter values.

Also, in the information processing apparatus 100 according to the embodiment, each of the plurality of objects corresponds to a transaction target traded in the electronic commerce service.

In this way, the information processing apparatus 100 according to the embodiment can execute an approximate search targeting a plurality of objects corresponding to transaction targets traded in an electronic commerce service, using appropriate parameter values. can be

An information retrieval device according to the embodiment (the information processing device 100 in the embodiment) has an acquisition unit 131 and a retrieval unit 135 . The acquisition unit 131 indicates an index for searching a plurality of objects, a specified value for specifying an evaluation index value for approximate search using the index, and a parameter value used in the approximate search corresponding to the evaluation index value. Acquire conversion information. The search unit 135 executes the approximate search using the parameter values obtained by converting the specified values of the evaluation index based on the conversion information.

As described above, the information processing apparatus 100 according to the embodiment executes an approximate search using an index using a parameter value obtained by converting a designated value of an evaluation index based on conversion information, thereby obtaining an appropriate Approximate search using parameter values can be enabled.

[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. 13, for example. FIG. 13 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 information processing device 120 storage unit 121 object information storage unit 122 tree information storage unit 123 graph information storage unit 124 approximate correct search result information storage unit 125 conversion information storage unit 130 control unit 131 acquisition unit 132 generation unit 133 conversion unit 134 determination unit 135 search unit 136 provision unit 10 terminal device 50 information provision device N network

Claims (24)

A specified value specifying a value of an evaluation index for an approximate search using an index that searches a plurality of objects, the specified value specified by the user requesting the approximate search being sent from the terminal device used by the user an acquisition unit that acquires , from a storage unit, conversion information indicating the value of a parameter used in the approximate search corresponding to the value of the evaluation index;
a conversion unit that converts the specified value specified by the user into the value of the parameter used in the approximate search for providing results to the user, based on the conversion information acquired by the acquisition unit;
An information processing device comprising: The acquisition unit
obtaining the specified value of the approximate search using a graph in which a plurality of nodes corresponding to each of the plurality of objects are connected by edges as the index;
The conversion unit
2. The information processing apparatus according to claim 1, wherein said designated value of said evaluation index is converted into a value of said parameter used in said approximate search using said graph. Said parameters are:
3. The information processing apparatus according to claim 2, wherein the search range coefficient is a coefficient for determining a search range in search processing using the graph. The acquisition unit
obtaining, as the conversion information, a lookup table indicating a correspondence relationship between each value of the evaluation index and each value of the parameter;
The conversion unit
4. The information processing apparatus according to any one of claims 1 to 3, wherein the designated value of the evaluation index is converted into the value of the parameter used in the approximate search by referring to the lookup table. . a generation unit that generates the lookup table by generation processing including search processing using the index;
5. The information processing apparatus according to claim 4, further comprising: The generating unit
6. The information processing apparatus according to claim 5, wherein the lookup table is generated by the generating process including the search process using the evaluation query based on the evaluation object selected from the plurality of objects. . The generating unit
6. The lookup table is generated by the generation process including the search process using the evaluation query generated using a plurality of evaluation objects selected from the plurality of objects. 7. The information processing apparatus according to claim 6. The generating unit
8. The information processing apparatus according to claim 7, wherein the lookup table is generated by the generating process including the search process using an average of the plurality of evaluation objects as the evaluation query. The generating unit
generating an approximate correct search result that is a result of the approximate search using the evaluation query; 9. The information processing apparatus according to any one of claims 6 to 8, wherein a table is generated. The generating unit
3. When the index is a graph, the approximate correct search result is generated by adjusting a search range coefficient, which is a coefficient for determining a search range in search processing using the graph. 10. The information processing device according to 9. The generating unit
The value of the search range coefficient is increased from the first value, and the second value at the time when no new object appears in the approximate search result is used as the search range coefficient when generating the approximate correct search result. 11. The information processing apparatus according to claim 10, wherein the value is used. The generating unit
6. The lookup table is generated by the generation process including the search process using the index for searching a group of objects excluding the evaluation object from the plurality of objects. 12. The information processing device according to any one of 11. The generating unit
The lookup table is generated by the generating process that associates each of the plurality of values of the evaluation index obtained by the search process using each of the plurality of values of the parameter with each of the corresponding plurality of values of the parameter. 13. The information processing apparatus according to any one of claims 5 to 12, characterized in that it generates . The generating unit
The method according to any one of claims 5 to 13, wherein the lookup table is used to generate a function that receives the value of the evaluation index as an input and outputs a value to the parameter corresponding to the input value of the evaluation index. The information processing apparatus according to any one of items 1 and 2. The acquisition unit
Acquiring, as the conversion information, a function that uses the value of the evaluation index as an input and outputs a value to the parameter corresponding to the input value of the evaluation index;
The conversion unit
4. The specified value of the evaluation index is converted into the value of the parameter used in the approximate search by inputting the specified value of the evaluation index into the function. The information processing device according to the item. a search unit that executes the approximate search using the parameter value obtained by converting the specified value of the evaluation index based on the conversion information;
16. The information processing apparatus according to any one of claims 1 to 15, characterized by: The evaluation index is
17. The information processing apparatus according to any one of claims 1 to 16, wherein the index is search accuracy of search processing using the index. The evaluation index is
The information processing apparatus according to any one of claims 1 to 16, characterized in that it is a processing time of search processing using said index. Each of the plurality of objects includes:
19. The information processing device according to any one of claims 1 to 18, which corresponds to a transaction object traded in an electronic commerce service. A computer-executed information processing method comprising:
A specified value specifying a value of an evaluation index for an approximate search using an index that searches a plurality of objects, the specified value specified by the user requesting the approximate search being sent from the terminal device used by the user an obtaining step of obtaining , from a storage unit, conversion information indicating the value of the parameter used in the approximate search corresponding to the value of the evaluation index;
a conversion step of converting the specified value specified by the user into a value of the parameter used in the approximate search for providing results to the user, based on the conversion information acquired by the acquisition step;
An information processing method comprising: A specified value specifying a value of an evaluation index for an approximate search using an index that searches a plurality of objects, the specified value specified by the user requesting the approximate search being sent from the terminal device used by the user an acquisition procedure for acquiring , from a storage unit, conversion information indicating the value of a parameter used in the approximate search corresponding to the value of the evaluation index;
a conversion step of converting the specified value specified by the user into a value of the parameter used in the approximate search for providing results to the user, based on the conversion information acquired by the acquisition step;
An information processing program characterized by causing a computer to execute an index for searching a plurality of objects and a specified value specifying a value of an evaluation index for approximate search using the index, the specified value specified by a user requesting the approximate search; an acquisition unit that acquires from a storage unit conversion information indicating the value of a parameter used in the approximate search corresponding to the value of the evaluation index, which is acquired from the terminal device to be used;
a search unit that performs the approximate search for providing the result to the user , using the value of the parameter obtained by converting the specified value specified by the user based on the conversion information;
An information retrieval device comprising: A computer implemented information retrieval method comprising:
an index for searching a plurality of objects and a specified value specifying a value of an evaluation index for approximate search using the index, the specified value specified by a user requesting the approximate search; an acquisition step of acquiring from a storage unit conversion information indicating the value of the parameter used in the approximate search corresponding to the value of the evaluation index, which is acquired from the terminal device to be used;
a search step of performing the approximate search for providing results to the user using the parameter value obtained by converting the specified value specified by the user based on the conversion information;
An information retrieval method comprising: an index for searching a plurality of objects and a specified value specifying a value of an evaluation index for approximate search using the index, the specified value specified by a user requesting the approximate search; an acquisition procedure for acquiring , from a storage unit, conversion information indicating a parameter value used in the approximate search corresponding to the value of the evaluation index, acquired from the terminal device to be used;
a search procedure for executing the approximate search for providing results to the user using the parameter values obtained by converting the specified values of the evaluation index based on the conversion information;
An information retrieval program characterized by causing a computer to execute

Images