# US 2017/0255708 A1 · Index structures for graph databases

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255708 A1
- Document ID: US20170255708A1
- Status: Published application
- Kind: A1
- Application number: 15/058,028
- Filed: 2016-03-01
- Published: 2017-09-07
- Earliest claimed: 2016-03-01
- Assignees: LinkedIn Corporation
- Applicants: LinkedIn Corporation
- Inventors: SungJu Cho; Jiahong Zhu; Yinyi Wang; Roman A. Averbukh; Scott M. Meyer; Shyam Shankar; Qingpeng Niu; Karan R. Parikh
- Web page: https://patentgrep.com/patent/US20170255708A1

## CPC

- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/2228: {Indexing structures}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The disclosed embodiments provide a system for processing queries of a graph database. During operation, the system executes a set of processes for accessing a lock-free hash table stored in memory on a computer system, wherein the processes include a write process and multiple read processes. Next, the system uses the processes and the lock-free hash table to index a graph database storing a graph. The system then uses the processes to access a compressed edge store containing a compact representation of the set of edges at a virtual time in the graph and a series of updates to the edges after the virtual time. During use of the processes and the lock-free hash table to index the graph database, the system references the set of edges in the compact representation from a set of entries in the lock-free hash table.

## Claims

### Claim 1

A method, comprising:
executing a set of processes for accessing a lock-free hash table stored in memory on a computer system, wherein the set of processes comprises a write process and multiple read processes; and
using the set of processes and the lock-free hash table to index a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
using the set of processes to access a compressed edge store comprising a compact representation of the set of edges at a virtual time in the graph and a series of updates to the edges after the virtual time; and
during use of the set of processes and the lock-free hash table to index the graph database, referencing the set of edges in the compact representation from a set of entries in the lock-free hash table.

### Claim 3 (depends on 2)

The method of claim 2, wherein referencing the set of edges in the compact representation from the set of entries in the lock-free hash table comprises:
storing, in the set of entries, a set of offsets associated with the edges from the compact representation.

### Claim 4 (depends on 1)

The method of claim 1, wherein using the set of processes and the lock-free hash table to index the graph database comprises:
adding, by the write process, an entry to the lock-free hash table by:
using a hash of one or more keys associated with the entry to identify a hash bucket in the hash table;
upon determining that the entry does not exceed a remaining capacity of the hash bucket, appending the one or more keys and a value of the entry to an end of the hash bucket; and
after the key and the value are written to the end of the hash bucket, updating the hash table with an indicator of the entry to enable reading of the entry by the multiple read processes.

### Claim 5 (depends on 4)

The method of claim 4, wherein using the set of processes and the lock-free hash table to index the graph database further comprises:
upon determining that the remaining capacity of the hash bucket cannot accommodate an additional entry to the lock-free hash table:
allocating an additional hash bucket in the lock-free hash table;
including, in a field of the hash bucket, an reference to the additional hash bucket; and
appending the additional entry to an end of the additional hash bucket.

### Claim 6 (depends on 1)

The method of claim 1, wherein using the set of processes and the lock-free hash table to index the graph database comprises:
reading, by a read process in the multiple read processes, an entry from the lock-free hash table by:
using a hash of one or more keys associated with the entry to identify a hash bucket in the hash table; and
iterating through entries in the hash bucket until the entry matching the one or more keys is found.

### Claim 7 (depends on 6)

The method of claim 6, wherein using the set of processes and the lock-free hash table to index the graph database further comprises:
using a value stored in the entry to obtain a subset of the edges associated with the one or more keys; and
providing the subset of the edges in response to a query of the graph database.

### Claim 8 (depends on 7)

The method of claim 7, wherein the value of the entry comprises at least one of:
the subset of the edges; and
a reference to the subset of the edges.

### Claim 9 (depends on 6)

The method of claim 6, wherein the one or more keys comprise at least one of:
a subject;
a predicate; and
an object.

### Claim 10

An apparatus, comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
execute a set of processes for accessing a lock-free hash table stored in the memory, wherein the set of processes comprises a write process and multiple read processes; and
use the set of processes and the lock-free hash table to index a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
use the set of processes to access a compressed edge store comprising a compact representation of the set of edges at a virtual time in the graph and a series of updates to the edges after the virtual time; and
during use of the set of processes and the lock-free hash table to index the graph database, reference the set of edges in the compact representation from a set of entries in the lock-free hash table.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein referencing the set of edges in the compact representation from the set of entries in the lock-free hash table comprises:
storing, in the set of entries, a set of offsets associated with the edges from the compact representation.

### Claim 13 (depends on 10)

The apparatus of claim 10, wherein using the set of processes and the lock-free hash table to index the graph database comprises:
adding, by the write process, an entry to the lock-free hash table by:
using a hash of one or more keys associated with the entry to identify a hash bucket in the hash table;
upon determining that the entry does not exceed a remaining capacity of the hash bucket, appending the one or more keys and a value of the entry to an end of the hash bucket; and
after the key and the value are written to the end of the hash bucket, updating the hash table with an indicator of the entry to enable reading of the entry by the multiple read processes.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein using the set of processes and the lock-free hash table index the graph database further comprises:
upon determining that the remaining capacity of the hash bucket cannot accommodate an additional entry to the lock-free hash table:
allocating an additional hash bucket in the lock-free hash table;
including, in a field of the hash bucket, an reference to the additional hash bucket; and
appending the additional entry to an end of the additional hash bucket.

### Claim 15 (depends on 10)

The apparatus of claim 10, wherein using the set of processes and the lock-free hash table to index the graph database comprises:
reading, by a read process in the multiple read processes, an entry from the lock-free hash table by:
using a hash of one or more keys associated with the entry to identify a hash bucket in the hash table; and
iterating through entries in the hash bucket until the entry matching the one or more keys is found.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein using the set of processes and the lock-free hash table to index the graph database further comprises:
using a value stored in the entry to obtain a subset of the edges associated with the one or more keys; and
providing the subset of the edges in response to a query of the graph database.

### Claim 17

A system, comprising:
a management module comprising a non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to execute a set of processes for accessing a lock-free hash table stored in memory on a computer system, wherein the set of processes comprises a write process and multiple read processes; and
a processing module comprising a non-transitory computer-readable medium comprising instructions that, when executed by the one or more processors, cause the system to use the set of processes and the lock-free hash table to index a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates.

### Claim 18 (depends on 17)

The system of claim 17, wherein the non-transitory computer-readable medium of the processing module further comprises instructions that, when executed by the one or more processors, cause the system to:
use the set of processes to access a compressed edge store comprising a compact representation of the set of edges at a virtual time in the graph and a series of updates to the edges after the virtual time; and
during use of the set of processes and the lock-free hash table to index the graph database, reference the set of edges in the compact representation from a set of entries in the lock-free hash table.

### Claim 19 (depends on 17)

The system of claim 17, wherein using the set of processes and the lock-free hash table to index the graph database comprises:
adding, by the write process, an entry to the lock-free hash table by:
using a hash of one or more keys associated with the entry to identify a hash bucket in the hash table;
upon determining that the entry does not exceed a remaining capacity of the hash bucket, appending the one or more keys and a value of the entry to an end of the hash bucket; and
after the key and the value are written to the end of the hash bucket, updating the hash table with an indicator of the entry to enable reading of the entry by the multiple read processes.

### Claim 20 (depends on 19)

The system of claim 19, wherein using the set of processes and the lock-free hash table to index the graph database further comprises:
upon determining that the remaining capacity of the hash bucket cannot accommodate an additional entry to the lock-free hash table:
allocating an additional hash bucket in the lock-free hash table;
including, in a field of the hash bucket, an reference to the additional hash bucket; and
appending the additional entry to an end of the additional hash bucket.