# US 12,182,201 B2 · Graph data storage method, system and electronic device > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,182,201 B2 - Document ID: US12182201B2 - Status: Granted - Kind: B2 - Application number: 17/160,172 - Filed: 2021-01-27 - Published: 2021-05-20 - Granted: 2024-12-31 - Earliest claimed: 2018-07-27 - Assignees: Zhejiang Tmall Technology Co., Ltd. - Applicants: Zhejiang Tmall Technology Co., Ltd. - Inventors: Wenfei Fan; Wenyuan Yu; Jingbo Xu; Xiaojian Luo - Web page: https://patentgrep.com/patent/US12182201B2 ## CPC - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 12/0813: with a network or matrix configuration - G06F 2212/2542: Non-uniform memory access [NUMA] architecture - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A graph data storage method for non-uniform memory access architecture (NUMA) processing system is provided. The processing system includes at least one computing device, each computing device corresponding to multiple memories, and each memory corresponding to multiple processors. The method includes: performing three-level partitioning on graph data to obtain multiple third-level partitions based on a communication mode among computing device(s), memories, and processors; and separately storing graph data of the multiple third-level partitions in NUMA nodes corresponding to the processors. A graph data storage system and an electronic device are further provided. ## Claims ### Claim 1 A method implemented by a system, the method comprising: performing three-level partitioning on graph data to obtain multiple third-level partitions based on a communication mode among one or more computing devices, multiple memories, and multiple processors; and separately storing graph data of the multiple third-level partitions in non-uniform memory access architecture (NUMA) nodes corresponding to the multiple processors, the separately storing the graph data of the multiple third-level partitions in the NUMA nodes corresponding to the multiple processors comprising: storing a content of a first part of the graph data into the memories by way of the three-level partitioning on the graph data, the first part including a graph structure, data, and context; and storing a content of a second part of the graph data into the memories in a first interleaved mode, the content of the second part of the graph data being controlled by the multiple processors to control from which NUMA node each memory block is allocated, the content of the second part of the content including information that notifies different third-level partitions needing to synchronize state information; and storing a content of a third part of the graph data into the memories in a second interleaved mode different from the first interleaved mode, the content of the third part of the graph data being controlled by a graph computing engine to control from which NUMA node each memory block is allocated according to an access frequency and a load balance, the content of the third part including a partition table. ### Claim 2 (depends on 1) The method recited in claim 1, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode among the one or more computing devices, the multiple memories, and the multiple processors comprises: partitioning the graph data according to a number of the one or more computing devices and a communication overhead between the one or more computing devices to obtain multiple first-level partitions. ### Claim 3 (depends on 2) The method recited in claim 2, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode among the one or more computing devices, the multiple memories, and the multiple processors further comprises: dividing each first-level partition into multiple second-level partitions according to a number of NUMA nodes in each computing device and a communication overhead between NUMA nodes. ### Claim 4 (depends on 3) The method recited in claim 3, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode among the one or more computing devices, the multiple memories, and the multiple processors further comprises: dividing each second-level partition into a plurality of third-level partitions according to a number of working nodes in each NUMA node and a communication overhead between each working node, the working nodes including a processor of the multiple processors or a thread on the processor. ### Claim 5 (depends on 1) The method recited in claim 1, wherein the graph data comprises multiple data blocks, and each data block is alternately stored on a different NUMA node in an interleaved mode. ### Claim 6 One or more computer readable media storing executable instructions that, when executed by a processing system, cause the processing system to perform acts comprising: performing three-level partitioning on graph data to obtain multiple third-level partitions based on a communication mode among one or more computing devices, multiple memories, and multiple processors; and separately storing graph data of the multiple third-level partitions in non-uniform memory access architecture (NUMA) nodes corresponding to the multiple processors, the separately storing the graph data of the multiple third-level partitions in the NUMA nodes corresponding to the multiple processors comprising: storing a content of a first part of the graph data into the memories by way of the three-level partitioning on the graph data, the first part including a graph structure; and storing a content of a second part of the graph data into the memories in an first interleaved mode, the content of the second part of the content including information that notifies different third-level partitions needing to synchronize state information. ### Claim 7 (depends on 6) The one or more computer readable media recited in claim 6, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode among the one or more computing devices, the multiple memories, and the multiple processors further comprises: partitioning the graph data according to a number of the one or more computing devices and a communication overhead between the one or more computing devices to obtain multiple first-level partitions; and dividing each first-level partition into multiple second-level partitions according to a number of NUMA nodes in each computing device and a communication overhead between NUMA nodes. ### Claim 8 (depends on 7) The one or more computer readable media recited in claim 7, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode among the one or more computing devices, the multiple memories, and the multiple processors further comprises: dividing each second-level partition into a plurality of third-level partitions according to a number of working nodes in each NUMA node and a communication overhead between each working node, the working nodes including a processor of the multiple processors or a thread on the processor. ### Claim 9 (depends on 6) The one or more computer readable media recited in claim 6, wherein the first part further includes data, and context. ### Claim 10 (depends on 9) The one or more computer readable media recited in claim 9, wherein the content of the second part of the graph data is controlled by the multiple processors to control from which NUMA node each memory block is allocated. ### Claim 11 (depends on 10) The one or more computer readable media recited in claim 10, wherein the separately storing the graph data of the multiple third-level partitions in the NUMA nodes corresponding to the multiple processors further comprises: storing content of a third part of the graph data into the memories in another interleaved mode, where from which NUMA node each memory block is allocated is controlled according to an access frequency and a load balance, and the content of the third part includes a partition table. ### Claim 12 (depends on 6) The one or more computer readable media recited in claim 6, wherein the graph data comprises multiple data blocks, and each data block is alternately stored on a different NUMA node in an interleaved mode. ### Claim 13 An electronic device comprising: multiple processors; and multiple memories storing executable instructions that, when executed by the multiple processors, cause the multiple processors to perform acts comprising: performing three-level partitioning on graph data to obtain multiple third-level partitions based on a communication mode between the multiple memories and the multiple processors; and separately storing graph data of the multiple third-level partitions in non-uniform memory access architecture (NUMA) nodes corresponding to the multiple processors, the separately storing the graph data of the multiple third-level partitions in the NUMA nodes corresponding to the multiple processors comprising: storing a content of a first part of the graph data into the memories by way of the three-level partitioning on the graph data, the first part including a graph structure; and storing a content of a second part of the graph data into the memories in an interleaved mode, the content of the second part of the content including information that notifies different third-level partitions needing to synchronize state information. ### Claim 14 (depends on 13) The electronic device recited in claim 13, wherein the multiple processors and the multiple memories adopt a NUMA mode. ### Claim 15 (depends on 13) The electronic device recited in claim 13, wherein the separately storing the graph data of the multiple third-level partitions in the NUMA nodes corresponding to the processors further comprises: storing content of a first part of the graph data into the memory by way of the three-level partitioning of the graph data, wherein the first part includes a graph structure, data, and context; storing content of a second part of the graph data into the memory in an interleaved mode, wherein the processor controls from which NUMA node each memory block is allocated, and the content of the second part of the content includes information; and storing content of a third part of the graph data into the memory in an interleaved mode, wherein from which NUMA node each memory block is allocated is controlled according to an access frequency and a load balance, and the content of the third part includes a partition table. ### Claim 16 (depends on 2) The electronic device recited in claim 2, wherein the content of the third part of the graph data is controlled by a graph computing engine to control from which NUMA node each memory block is allocated according to the access frequency and the load balance. ### Claim 17 (depends on 13) The electronic device recited in claim 13, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode between the multiple memories and the multiple processors comprises: partitioning the graph data according to a number of one or more computing devices and a communication overhead between the one or more computing devices to obtain multiple first-level partitions. ### Claim 18 (depends on 17) The electronic device recited in claim 17, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode between the multiple memories and the multiple processors further comprises: dividing each first-level partition into multiple second-level partitions according to a number of NUMA nodes in each computing device and a communication overhead between NUMA nodes. ### Claim 19 (depends on 18) The electronic device recited in claim 18, wherein the performing the three-level partitioning on the graph data to obtain the multiple third-level partitions based on the communication mode between the multiple memories and the multiple processors further comprises: dividing each second-level partition into a plurality of third-level partitions according to a number of working nodes in each NUMA node and a communication overhead between each working node, the working nodes including a processor or a thread on the processor. ### Claim 20 (depends on 13) The electronic device recited in claim 13, wherein the content of the second part of the graph data is controlled by the multiple processors to control from which NUMA node each memory block is allocated, the content of the second part of the content including information that notifies different third-level partitions needing to synchronize state information.