Generation method, search method, and generation device

A search method implemented by a computer including a processor, a first memory, and a second memory configured to operate faster than the first memory, the search method comprising:

• receiving a query;
• setting a candidate of a first node closest to the received query along a directed graph, the directed graph including multiple first nodes corresponding to vectors in a search range, index information related to the directed graph being stored in the first memory before the receiving the query, the index information including first information pieces, each of the first information pieces including a vector value of one first node and IDs of all out-neighbor nodes of the one first node, the index information being configured such that a first information piece related to a second node being that is one of the multiple first nodes and a first information piece related to an out-neighbor node of the second node are stored in each of one or more second storage areas out of first storage areas, each of the first storage areas being a unit of access to the first memory and having the same size,
• performing a first operation including:
• in a case where a second information piece that is a first information piece related to a node being that is the first node as the candidate is stored in a cache area of the second memory, acquiring the second information piece from the cache area,
• in a case where the second information piece is not stored in the cache area, acquiring third information pieces and storing the acquired third information pieces in the cache area, the third information pieces including the second information piece from a third storage area in which the second information piece is stored, the third storage area being part of the first storage areas,
• extracting all neighbor nodes of the third node from the third information pieces, and
• performing an approximate nearest neighbor search operation using information about the third node and the neighbor nodes, and
• in a case where the nearest point candidate of the query is decided, outputting information on a node as the nearest point candidate of the query, the node being determined by the approximate nearest neighbor search operation, and in a case where the nearest point candidate of the query is not decided, setting a new first node as a new candidate based on the third information piece and performing the first operation again.

A generation device comprising:

• a first interface configured to receive a directed graph;
• a second interface configured to be connectable to a storage device;
• and
• a processor configured to execute processing of:
• receiving, via the first interface, the directed graph,
• setting one of multiple first nodes as a second node, the multiple first nodes being included in a directed graph and corresponding to vectors included in a search range,
• selecting (M−1) fourth nodes (M is an integer of two or more) from among one or more third nodes on the basis of the directed graph, each of the third nodes being an out-neighbor node of the second node in the multiple first nodes,
• writing, to a first storage area of the storage device, an information piece related to the second node and information pieces related to the (M−1) fourth nodes, the information piece related to the second node and the information pieces related to the (M−1) fourth nodes each being an index element related to one first node in index information corresponding to the directed graph, the index element including a vector value of the one first node and IDs of all out-neighbor nodes of the one first node, the first storage area being one of second storage areas of the storage device, the second storage areas being a unit of access to the storage device and having the same size, and
• executing multiple times of first operations until the writing for index elements related to all the first nodes are completed, each of the multiple times of first operations including the setting, the selecting, and the writing, wherein
• M information pieces written to any second storage area by the executing is able to be, when searching by a computer that comprises a cache memory, collectively acquired and stored into the cache memory, the information pieces stored in the cache memory is used in the searching by the computer.