Shyam Shankar

US Patent:

20170255708, Sep 7, 2017

Filed:

Mar 1, 2016

Appl. No.:

15/058028

Inventors:

- Mountain View CA, US
Jiahong Zhu - San Jose CA, US
Yinyi Wang - Saratoga CA, US
Roman A. Averbukh - Sunnyvale CA, US
Scott M. Meyer - Berkeley CA, US
Shyam Shankar - Sunnyvale CA, US
Qingpeng Niu - San Jose CA, US
Karan R. Parikh - San Francisco CA, US

Assignee:

LinkedIn Corporation - Mountain View CA

International Classification:

G06F 17/30

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.

US Patent:

20170255709, Sep 7, 2017

Filed:

Mar 1, 2016

Appl. No.:

15/058032

Inventors:

- Mountain View CA, US
Jiahong Zhu - San Jose CA, US
Yinyi Wang - Saratoga CA, US
Roman A. Averbukh - Sunnyvale CA, US
Scott M. Meyer - Berkeley CA, US
Shyam Shankar - Sunnyvale CA, US
Qingpeng Niu - San Jose CA, US
Karan R. Parikh - San Francisco CA, US

Assignee:

LinkedIn Corporation - Mountain View CA

International Classification:

G06F 17/30

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.