Distributed graph databases that facilitate streaming data insertion and queries by efficient throughput edge addition

• US 10,394,891 B2
• Filed: 08/05/2016
• Issued: 08/27/2019
• Est. Priority Date: 08/05/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Chun-Fu, Crawford, Jason L., Lin, Ching-Yung, Lu, Jie, Nutter, Mark R., Suzumura, Toyotaro, Tanase, Ilie G., Yeh, Danny L.
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US15/230,054
• Publication Number:
  US 20180039710A1
• Time in Patent Office: 1,117 Days
• Field of Search: 707798, 717149, 717156
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A novel distributed graph database is provided that is designed for efficient graph data storage and processing on modern computing architectures. In particular a single node graph database and a runtime & communication layer allows for composing a distributed graph database from multiple single node instances.

Claims

1. A computer-implemented method for efficient throughput edge addition, comprising:

determining, by a device operatively coupled to a processor, vertex placement, based on a hash or an arbitrary placement function;

placing, by the device, outgoing edge requests into appropriate queues of a firehose; and

placing, by the device, incoming edge requests into appropriate queues of the firehose, wherein for each queue, in parallel, the device;

sends requests to add vertices for all sources in an outgoing edges set, and all targets in an incoming edges set, and wait for vertex ids of all added vertices and MAXEID from each machine, respectively.

2. The computer-implemented method of claim 1, further comprising preparing and sending edge tuples for insertion.

3. The computer-implemented method of claim 1, wherein an ingest process is divided into batches, and wherein the acts are executed for respective batches.

4. The computer-implemented method of claim 1, wherein for all vertices added insert into a map (hash table) the pairing from external vertex identifier to internal vertex identifier <

A,VIDA>

, <

B,VIDB>

, <

C,VIDC> and

<

D,VIDD>

.

5. The method of claim 1, wherein for all outgoing and incoming edges map from external ids to internal ids and edge identifiers.

6. The method of claim 5, wherein upon receiving the ids for all vertices added the firehose will build for each queue, for all the tuples in each queue the following info:

{VIDS, VIDT, LID, EID}.

7. The method of claim 5, further comprising sending edge quads to respective machines for insertion.

8. The method of claim 7, wherein mapping from external to internal is can be cached for use in a next iteration.

9. The method of claim 1, further comprising preparing and sending edge tuples for insertion.

10. A system, comprising:

a memory that stores computer executable components; and

a processor that executes the computer executable components stored in the memory, wherein the computer executable components comprise;

a graph database component that;

determines vertex placement, based on a hash or an arbitrary placement function;

places outgoing edge requests into appropriate queues of a firehose; and

places incoming edge requests into appropriate queues of the firehose, wherein for each queue, in parallel, sends requests to add vertices for all sources in an outgoing edges set, and all targets in an incoming edges set, and waits for vertex ids of all added vertices and MAXEID from each machine, respectively.

11. The system of claim 10, wherein an ingest process is divided into batches, and wherein the operations are executed for respective batches.

12. The system of claim 10, wherein for all vertices added insert into a hash table the pairing from external vertex identifier to internal vertex identifier <

A,VIDA>

, <

B,VIDB>

, <

C,VIDC> and

<

D,VIDD>

.

13. The system of claim 10, wherein for all outgoing and incoming edges map from external ids to internal ids and edge identifiers.

14. The system of claim 10, wherein upon receiving the ids for all vertices added the firehose will build for each queue, for all the tuples in each queue the following info:

{VIDS, VIDT, LID, EID}.

15. A computer program product for efficient throughput edge addition, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processing component to cause the processing component to:

determine vertex placement, based on a hash or an arbitrary placement function;

place outgoing edge requests into appropriate queues of a firehose; and

place incoming edge requests into appropriate queues of the firehose, wherein for each queue, in parallel, the processing component is caused to;

send requests to add vertices for all sources in an outgoing edges set, and all targets in an incoming edges set, and wait for vertex ids of all added vertices and MAXEID from each machine, respectively.

16. The computer program product of claim 15, wherein the program instructions are further executable by the processing component to cause the processing component to prepare and send edge tuples for insertion.

17. The computer program product of claim 15, wherein the program instructions are further executable by the processing component to cause the processing component to divide an ingest process into batches.

18. The computer program product of claim 15, wherein the program instructions are further executable by the processing component to cause the processing component for all vertices added to insert into a map the pairing from external vertex identifier to internal vertex identifier <

A,VIDA>

, <

B,VIDB>

, <

C,VIDC> and

<

D,VIDD>

.

19. The computer program product of claim 15, wherein the program instructions are further executable by the processing component to cause the processing component for all outgoing and incoming edges map from external ids to internal ids and edge identifiers.

20. The computer program product of claim 19, wherein upon receiving the ids for all vertices added, the firehose builds for each queue, for all the tuples in each queue the following info:

{VIDS, VIDT, LID, EID}.