Large-Scale, Dynamic Graph Storage and Processing System

Patent metadata

Field	Value
Publication number	US-2016110409-A1
Application number	US-201514831809-A
Country	US
Kind code	A1
Filing date	Aug 20, 2015
Priority date	Oct 15, 2014
Publication date	Apr 21, 2016
Grant date	—

Abstract

A method in a graph storage and processing system is provided. The method includes storing, in a scalable, distributed, fault-tolerant, in-memory graph storage device, base graph data representative of graphs, and storing, in a real-time, in memory graph storage device, update graph data representative of graph updates for the graphs with respect to a time threshold. The method further includes sampling the base graph data to generate sampled portions of the graphs and storing the sampled portions, by an in-memory graph sampler. The method additionally includes providing, by a query manager, a query interface between applications and the system. The method also includes forming, by the query manager, graph data representative of a complete graph from at least the base graph data and the update graph data, if any. The method includes processing, by a graph computer, the sampled portions using batch-type computations to generate approximate results for graph-based queries.

First claim

What is claimed is:

1 . A method in a graph storage and processing system, comprising:
storing, in a scalable, distributed, fault-tolerant, in-memory graph storage device, base graph data representative of graphs; storing, in a real-time, in memory graph storage device, update graph data representative of graph updates for the graphs with respect to a time threshold; sampling the base graph data to generate sampled portions of the graphs and storing the sampled portions of the graph, by an in-memory graph sampler; providing, by a query manager, a query interface between applications and the system; forming, by the query manager, graph data representative of a complete graph from at least the base graph data in the scalable, distributed, fault-tolerant, in-memory graph storage device and the update graph data, if any, in the real-time, in memory graph storage device; and processing, by a graph computer, the sampled portions of the graphs using batch-type computations to generate approximate results for graph-based queries.

2 . The method of claim 1 , further comprising:
configuring the scalable, distributed, fault-tolerant, in-memory graph storage device for optimized graph-based retrieval and query processing; and configuring the real-time, in memory graph storage device for optimized data assimilation into the system.

3 . The method of claim 1 , further comprising using different data storage structures for storing the graph storage and the graph updates.

4 . The method of claim 3 , wherein the different data storage structures implement different storage policies and provide different storage capabilities.

5 . The method of claim 1 , further comprising indexing, by the scalable, distributed, fault-tolerant, in-memory graph storage device, graph vertices, incoming edges of the graph vertices, and outgoing edges of the graph vertices, to support structural queries on the graphs.

6 . The method of claim 1 , further comprising storing, in the scalable, distributed, fault-tolerant, in-memory graph storage device, temporal-based graph data to support temporal-based graph queries.

7 . The method of claim 1 , further comprising merging at least some of the sampled portions of the graph with live feeds from the real-time, in memory graph storage device.

8 . The method of claim 1 , further comprising:
publishing, by a glue device, the graph updates for the applications; and retiring the graph updates, by the glue device, responsive to a consumption of the graph updates by the applications.

9 . The method of claim 8 , wherein the graph updates are published, by the glue device, as live feeds configured for consumption by online, incremental graph algorithms.

10 . The method of claim 8 , further comprising merging, by the glue device, the graph updates with the sampled portions of the graphs for consumption by online, approximate, non-incremental graph algorithms.

11 . The method of claim 8 , further comprising pushing, by the glue device, the graph updates from the real-time, in memory graph storage device to the scalable, distributed, fault-tolerant, in-memory graph storage device for assimilation into corresponding ones of the graphs.

12 . The method of claim 11 , wherein the graph updates are pushed to the scalable, distributed, fault-tolerant, in-memory graph storage device with respect to the time threshold.

13 . The method of claim 1 , wherein the update graph data representative of the graph updates is maintained separately from the base graph data representative of the graphs using the real-time, in memory graph storage device and the scalable, distributed, fault-tolerant, in-memory graph storage device.

14 . The method of claim 1 , further comprising providing live graph update feeds, and configuring the query manager to respond to a graph query by selectively using one or more of the real-time, in-memory graph storage device, the scalable, distributed, fault-tolerant, in-memory graph storage device, the live graph update feeds, and the in-memory graph sampler depending on query requirements for query result completeness, query search speed, and query result accuracy.

15 . The method of claim 1 , further comprising providing live graph update feeds, and configuring the query manager to respond to a graph query by selectively bypassing one or more of the real-time, in-memory graph storage device, the scalable, distributed, fault-tolerant, in-memory graph storage device, the live graph update feeds, and the in-memory graph sampler depending on query requirements for query result completeness, query search speed, and query result accuracy.

16 . The method of claim 1 , further comprising providing live graph update feeds, and configuring the query manager to respond to a graph query by selectively accessing or bypassing the real-time, in-memory graph storage device, the scalable, distributed, fault-tolerant, in-memory graph storage device, the live graph update feeds, and the in-memory graph sampler depending on a request type present in the graph query.

17 . The method of claim 1 , further comprising providing live graph update feeds, and configuring the query manager to respond to a graph query from any of an online application, an offline application, an incremental application, a non-incremental application, an exact application and an approximate application by selectively accessing one or more of the real-time, in-memory graph storage device, the scalable, distributed, fault-tolerant, in-memory graph storage device, the live graph update feeds, and the in-memory graph sampler.

18 . The method system of claim 1 , further comprising:
performing, by an online, incremental graph computer, online incremental graph computations responsive to a graph query; performing, by an online, non-incremental graph computer, online non-incremental graph computations responsive to the graph query; and performing, by the graph computer, offline, batch-style, iterative graph computations responsive to the graph query.

19 . The method of claim 1 , further comprising:
receiving, by a real-time processing sub-system, the graph updates from a streaming source; and processing, by the real-time processing sub-system, the graph updates for dissemination in the system.

20 . The method of claim 1 , further comprising providing, by the query manager, a plurality of graph representations for a same one of the graphs depending on at least one of, requirements of a graph query and characteristics of an application generating the graph query.

Assignees

• Nec Lab America Inc

Inventors

• Rao Kunal
• Coviello Giuseppe
• Chakradhar Srimat
• Bhattacherjee Souvik
• Cadambi Srihari

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2372

  Updates performed during offline database operations · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F16/2358

  Change logging, detection, and notification (replication G06F16/27) · CPC title