Graph processing system
AssigneethatDot, Inc.
InventorRyan Wright
Life of this patent
Estimating the term…
Abstract
A graph comprising nodes and edges is stored by a distributed system as a collection of nodes and half-edges stored with their respective nodes. A message processor is associated with a node as needed to process messages passed between nodes, such that a given node has zero or one message processor assigned to it at a given time. Queries of the graph are resolved by processing a first portion of the query at a first node, and forwarding the results with the remaining portions of the query to a node linked by an edge to the present node.
Claims20
A system, comprising:
- a computing device comprising at least one processor and at least one memory, the at least one memory comprising instructions that, in response to execution by the at least one processor, cause the computing device to at least:
- receive at least one message indicative of storing data in a graph to comprise a first node linked to a second node;
- in response to determining that no message processor is assigned to the first node, assign a message processor to the first node, wherein the message processor processes messages directed to the first node in a defined order;
- store, based at least in part on the at least one message, a first record indicative of the first node, the first record comprising information indicative of a property of the first node and information indicative of a first half-edge associated with the second node;
- and
- store, based at least in part on the at least one message, in a second record indicative of the second node, information indicative of a second half-edge associated with the first node.
A computer-implemented method, comprising:
- storing a graph of data as a plurality of nodes, wherein an edge between a first node and a second node, of the plurality of nodes, is represented by at least a first half-edge associated with the first node;
- and
- associating each of the plurality of nodes with a message processor, wherein a message processor associated with a node processes messages directed to the respective node in a defined order.
A non-transitory computer-readable storage medium comprising instructions that, when executed by at least one processor of at least one computing device, cause the at least one computing device to:
- store a graph of data as a plurality of nodes, wherein an edge between a first node and a second node, of the plurality of nodes, is represented by at least a first half-edge associated with the first node;
- and
- associate each of the plurality of nodes with a message processor, wherein a message processor associated with a node processes messages directed to the respective node in a defined order.
Dependencies are inferred from the claim text.