Generation method, search method, and generation device

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

• acquiring a query;
• and
• setting a candidate of a first node closest to the query along a directed graph defined by index information, the directed graph including multiple first nodes corresponding to multiple first vectors included in a search range, the index information being stored in the storage device and including multiple first information pieces, each of the multiple first information pieces including
• a second vector being a first vector corresponding to one first node out of the multiple first vectors, and
• an ID and a third vector for each of one or more second nodes, the second nodes being all out-neighbor nodes of the one first node of the multiple first nodes, the third vector being a vector corresponding to the second node,
• wherein the setting of the candidate includes:
• reading a second information piece from a storage region of the storage device and storing the second information piece in the memory, the second information piece being the first information piece related to a third node that is the first node as the candidate, the storage region corresponding to a unit of access to the storage device;
• and
• setting the first node as a new candidate based on one or more of the third vectors included in the second information piece stored in the memory.

A generation device comprising:

• a first interface configured to receive a directed graph and multiple first vectors, the directed graph including multiple first nodes each assigned with an ID, the multiple first nodes respectively corresponding to the multiple first vectors, the multiple first vectors being included in a search range;
• a second interface configured to output data to a storage device connected to the generation device;
• and
• a processor configured to execute
• setting one of the multiple first nodes as a second node;
• and
• writing an information piece being an element related to the second node out of elements of index information corresponding to the directed graph, the information piece being written via the second interface to the storage device, the information piece including
• a second vector being a first vector corresponding to the second node out of the multiple first vectors, and
• an ID and a third vector for each of one or more third nodes, the third nodes being all out-neighbor nodes of the second node out of the multiple first nodes, the third vector corresponding to one of the third nodes, wherein
• the processor is configured to execute multiple times of first operations, each of the multiple times of first operations including the setting and the writing,
• the writing in each of the multiple times of first operations is performed by writing the information piece in a different storage region among multiple storage regions in the storage device, and
• each of the multiple storage regions corresponds to a unit of access to the storage device.