Title:
METHOD AND SYSTEM FOR PARALLELIZING SEQUENTIAL GRAPH COMPUTATION
Document Type and Number:
WIPO Patent Application WO/2018/205986
Kind Code:
A1
Abstract:
A method and system for parallelizing sequential graph computations are provided. The method comprises, partitioning a graph G into fragments; distributing the fragments and parallelized algorithms across n workers respectively; receiving a query Q at a coordinator and posting Q to all workers; executing partial evaluation by each worker against its local fragment; and generating messages; exchange messages between each worker; executing incremental evaluation by worker upon receiving a message against local fragment updated by the message; iterating the incremental evaluation until no further update message can be made to any fragment; computing a complete result via assemble partial results from workers by the coordinator; and returning the result as the answer to the query Q. The system is also disclosed via illustrating the architecture according to a figure.
Inventors:
FAN WENFEI (CN)
XU JINGBO (CN)
YU WENYUAN (CN)
XU JINGBO (CN)
YU WENYUAN (CN)
Application Number:
PCT/CN2018/086454
Publication Date:
November 15, 2018
Filing Date:
May 11, 2018
Export Citation:
Assignee:
SHANGHAI PUTU TECH PARTNERSHIP GENERAL PARTNERSHIP (CN)
International Classes:
G06F17/30
Foreign References:
| CN106033476A | 2016-10-19 | |||
| CN105447156A | 2016-03-30 | |||
| CN104158840A | 2014-11-19 | |||
| US20170097853A1 | 2017-04-06 |
Other References:
FAN, WENFEI ET AL.: "Distributed Graph Simulation: Impossibility and Possibility", PROCEEDINGS OF THE VLDB ENDOWMENT, vol. 7, no. 12, 5 September 2014 (2014-09-05), pages 1084 - 1090, XP055550374
Attorney, Agent or Firm:
BEIJING KUAIZHIHUI IP AGENCY CO., LTD (CN)
Download PDF: