Title:
LARGE-SCALE DYNAMIC GRAPH DIVISION METHOD BASED ON SLIDING WINDOW
Document Type and Number:
WIPO Patent Application WO/2021/000435
Kind Code:
A1
Abstract:
A large-scale dynamic graph division method based on a sliding window, which method belongs to the technical field of computers. According to the method, when vertexes are added, the vertexes with higher degrees are preferentially selected from the sliding window for division, so that the vertexes with lower degrees can be gathered to the vertexes with higher degrees, and as many vertexes as possible can also be divided into appropriate partitions at each instance of division, thereby realizing load balancing and reducing the number of cut edges, and thus greatly reducing the communication cost during a graph calculation process; and when edges are added, the vertexes with the most adjacent edges are preferentially selected from the sliding window for division, so that the frequent migration of the vertexes can be effectively avoided, and as many adjacent vertexes as possible can also be divided into appropriate partitions at each instance of division, thereby greatly reducing the number of instances of migrations of the vertexes, improving the division efficiency, and realizing load balancing and minimizing the number of cut edges.
Inventors:
CUI HUANQING (CN)
RONG XUANYU (CN)
JIA RUISHENG (CN)
WEI YONGSHAN (CN)
ZHANG FENG (CN)
XU QIANG (CN)
RONG XUANYU (CN)
JIA RUISHENG (CN)
WEI YONGSHAN (CN)
ZHANG FENG (CN)
XU QIANG (CN)
Application Number:
PCT/CN2019/108136
Publication Date:
January 07, 2021
Filing Date:
September 26, 2019
Export Citation:
Assignee:
UNIV SHANDONG SCIENCE & TECH (CN)
International Classes:
G06F16/901
Foreign References:
| CN103699606A | 2014-04-02 | |||
| CN106780697A | 2017-05-31 | |||
| CN104361578A | 2015-02-18 | |||
| CN109325976A | 2019-02-12 | |||
| US7742906B2 | 2010-06-22 |
Attorney, Agent or Firm:
QINGDAO ZHIDILINGCHUANG PATENT AGENCY CO., LTD (CN)
Download PDF: