Generation method, search method, and generation device
According to an embodiment, a generation method includes setting and writing. The setting is to set one of multiple first nodes as a second node. The multiple first nodes are included in a directed graph and are each assigned with an ID. The multiple first nodes respectively correspond to multiple first vectors included in a search range. The writing is to write an information piece that is an element related to the second node out of elements of index information corresponding to the directed graph. The information piece includes a second vector that is a first vector corresponding to a second node out of the multiple first vectors. The information piece includes an ID and a third vector for each of third nodes. The third nodes are all out-neighbor nodes of the second node. The third vector corresponds to one of the third nodes.
1 . A generation method implemented by a computer including a first interface configured to receive a directed graph, a processor configured to perform processing on data represented by the directed graph, and a second interface configured to output data based on the processing, the method comprising:
receiving the directed graph via the first interface;
setting one of multiple first nodes as a second node, the multiple first nodes being included in the directed graph and each being assigned with an ID, the multiple first nodes respectively corresponding to multiple first vectors included in a search range;
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 a storage device connected to the computer, 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; and
executing multiple times of first operations, each of the multiple times of first operations including the setting and the writing, wherein
the writing in each of the multiple times of first operations is performed by writing the information piece to 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.
2 . The generation method according to claim 1 , wherein the third vector includes the first vector corresponding to the third node, or a vector generated by compressing the first vector corresponding to the third node.
3 . The generation method according to claim 1 , wherein
the setting in each of the multiple times of first operations includes setting, as the second node, a first node not yet been set as the second node out of the multiple first nodes, and
the multiple times of first operations are executed until there is no first node not yet been set as the second node.
4 . The generation method according to claim 1 , wherein the writing includes adding, to the information piece, information about the number of out-neighbor nodes of the second node.
5 . The generation method according to claim 1 , wherein the writing includes adding, to the information piece, a fourth vector generated by compressing the second vector.
6 . The generation method according to claim 1 , wherein the writing includes generating the information piece in which the second vector is arranged at a head.
7 . The generation method according to claim 1 , wherein the information piece includes no ID of the second vector.
8 . 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.
9 . The search method according to claim 8 , wherein the third vector includes the first vector corresponding to the second node, or a vector generated by compressing the first vector corresponding to the second node.
10 . The search method according to claim 8 , further comprising:
after the second information piece is stored in the memory, calculating a distance between the first node as the candidate and the query by using the first vector included in the stored second information piece; and
determining a vector closest to the query based on the distances between each of the first nodes having been set as the candidate and the query.
11 . The search method according to claim 8 , wherein the storage device includes a NAND flash memory and the memory includes a DRAM.
12 . 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.
13 . The generation device according to claim 12 , wherein the third vector include the first vector corresponding to the third node, or a vector generated by compressing the first vector corresponding to the third node.
14 . The generation device according to claim 12 , wherein
the setting in each of the multiple times of first operations includes setting, as the second node, a first node not yet been set as the second node out of the multiple first nodes, and
the processor is further configured to execute the multiple times of first operations until there is no first node not yet been set as the second node.
15 . The generation device according to claim 12 , wherein the processor is configured to add, to the information piece, information about the number of out-neighbor nodes of the second node.
16 . The generation device according to claim 12 , wherein the writing includes adding, to the information piece, a fourth vector generated by compressing the second vector.
17 . The generation device according to claim 12 , wherein the writing includes generating the information piece in which the second vector is arranged at a head.
18 . The generation device according to claim 12 , wherein the information piece includes no ID of the second vector.