# US 2017/0255709 A1 · Atomic updating of graph database index structures

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

- Number: US 2017/0255709 A1
- Document ID: US20170255709A1
- Status: Published application
- Kind: A1
- Application number: 15/058,032
- 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/US20170255709A1

## CPC

- G06F 16/9014: {hash tables}
- G06F 16/2255: {Hash tables}
- G06F 16/2272: {Management thereof}
- G06F 16/28: Databases characterised by their database models, e.g. relational or object models
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The disclosed embodiments provide a system for updating an index structure of a graph database storing a graph. During operation, the system includes, in the index structure, a first compressed edge store containing a first compact representation of edges in the graph at a first virtual time and a first series of updates to the edges after the first virtual time. At a second virtual time, the system creates a second compact representation of the edges from the first compact representation and the first series of updates. The system then appends, to the second compact representation, a second series of updates to the edges after the second virtual time to produce a second compressed edge store. Finally, the system updates the index structure by atomically replacing, in the index structure, a reference to the first compressed edge store with a reference to the second compressed edge store.

## Claims

### Claim 1

A method, comprising:
providing, by a computer system, an index structure for use in processing queries of 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;
including, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the edges after the first virtual time;
creating, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates;
appending, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store; and
updating the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
including, in the index structure, a first lock-free hash table comprising a first set of hash buckets and a first set of entries in the first set of hash buckets; and
referencing, by the first set of entries, the set of edges in the first compact representation.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
creating a second lock-free hash table comprising a second set of hash buckets and a second set of entries in the second set of hash buckets;
referencing, by the second set of entries, the set of edges in the second compact representation; and
updating the index structure with the second lock-free hash table by atomically replacing, in the index structure, a third reference to the first lock-free hash table with a fourth reference to the second lock-free hash table.

### Claim 4 (depends on 3)

The method of claim 3, wherein creating the second lock-free hash table comprises:
selecting a size of the second lock-free hash table based on an attribute associated with the first lock-free hash table.

### Claim 5 (depends on 4)

The method of claim 4, wherein the attribute is at least one of:
a remaining capacity of the first lock-free hash table; and
a number of overflow buckets in the first lock-free hash table.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
after the first reference is replaced with the second reference in the index structure, maintaining the first compressed edge store until processing of the queries using the first compressed edge store is complete.

### Claim 7 (depends on 1)

The method of claim 1, wherein the first compact representation comprises:
a first sorting of the edges by a first attribute; and
for each value of the first attribute in the first sorting, a second sorting of the edges by a second attribute.

### Claim 8 (depends on 7)

The method of claim 7, wherein the first compact representation further comprises:
for each value of the second attribute in the second sorting, a set of values for one or more additional attributes of the edges.

### Claim 9 (depends on 8)

The method of claim 8, wherein the one or more additional attributes comprise a virtual time in the graph.

### Claim 10 (depends on 7)

The method of claim 7, wherein the first attribute and the second attribute comprise at least one of:
a subject;
a predicate; and
an object.

### Claim 11 (depends on 1)

The method of claim 1, wherein the second series of updates is appended to the second compact representation from a log-based representation of the graph database.

### Claim 12

An apparatus, comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
provide an index structure for use in processing queries of 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;
include, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the edges after the first virtual time;
create, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates;
append, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store; and
update the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
include, in the index structure, a first lock-free hash table comprising a first set of hash buckets and a first set of entries in the first set of hash buckets; and
reference, by the first set of entries, the set of edges in the first compact representation.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
create a second lock-free hash table comprising a second set of hash buckets and a second set of entries in the second set of hash buckets;
reference, by the second set of entries, the set of edges in the second compact representation; and
update the index structure with the second lock-free hash table by atomically replacing, in the index structure, a third reference to the first lock-free hash table with a fourth reference to the second lock-free hash table.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein creating the second lock-free hash table comprises:
selecting a size of the second lock-free hash table based on an attribute associated with the first lock-free hash table.

### Claim 16 (depends on 12)

The apparatus of claim 12, wherein the first compact representation comprises:
a first sorting of the edges by a first attribute; and
for each value of the first attribute in the first sorting, a second sorting of the edges by a second attribute.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the first compact representation further comprises:
for each value of the second attribute in the second sorting, a set of values for one or more additional attributes of the edges.

### Claim 18

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:
provide an index structure for use in processing queries of 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; and
include, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the edges after the first virtual time; and
an update module comprising a non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to:
create, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates;
append, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store; and
update the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store.

### Claim 19 (depends on 18)

The system of claim 18, wherein the non-transitory computer-readable medium of the management module further comprises instructions that, when executed by the one or more processors, cause the system to:
include, in the index structure, a first lock-free hash table comprising a first set of hash buckets and a first set of entries in the first set of hash buckets; and
reference, by the first set of entries, the set of edges in the first compact representation.

### Claim 20 (depends on 19)

The system of claim 19, wherein the non-transitory computer-readable medium of the update module further comprises instructions that, when executed by the one or more processors, cause the system to:
create a second lock-free hash table comprising a second set of hash buckets and a second set of entries in the second set of hash buckets;
reference, by the second set of entries, the set of edges in the second compact representation; and
update the index structure with the second lock-free hash table by atomically replacing, in the index structure, a third reference to the first lock-free hash table with a fourth reference to the second lock-free hash table.