Eureka AIR delivers breakthrough ideas for toughest innovation challenges, trusted by R&D personnel around the world.

A Directed Graph Reachability Linked List Generation and Query Method in Parallel Environment

A reachability and directed graph technology, which is applied in the field of directed graph reachability linked list generation and query, can solve the problems of short calculation time, large index occupation space, and high index storage cost, so as to speed up the query speed, The effect of reducing the size of graph data and reducing the calculation load

Active Publication Date: 2016-05-25
NORTHEASTERN UNIV LIAONING
View PDF4 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

If the precomputation cost of these methods is high, the obtained results will cover more accessibility information and the index will be more detailed; the corresponding query process time cost will be relatively small, and the query calculation speed will be relatively fast, but this is also It will cause the problem that the index is too large and takes up too much space
However, if there are too many update operations on the graph, and the index design cannot incrementally maintain the reachability index of the graph, the precomputation cost of this solution exceeds expectations—the entire graph data needs to be recalculated every time an update is performed. The calculated index is usually linearly related to the edge of the graph because the information is relatively complete, and the calculation cost is high, and the index storage cost is also high; if a lightweight index is used for judgment, the index calculation process is relatively short, but the query process is due to the reason Some indexes do not cover the data on the entire graph, so a large amount of data in the original graph needs to be searched

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • A Directed Graph Reachability Linked List Generation and Query Method in Parallel Environment
  • A Directed Graph Reachability Linked List Generation and Query Method in Parallel Environment
  • A Directed Graph Reachability Linked List Generation and Query Method in Parallel Environment

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0085] Embodiments of the present invention will be further described in detail below in conjunction with the accompanying drawings.

[0086] In modern society, the application of graphs is becoming more and more extensive, and the amount of data that needs to be processed has increased significantly. In this case, relying solely on a single processor for computing can no longer meet the current needs of graph accessibility computing tasks. The current computing The task needs to be completed in a multi-processor parallel environment, so it is particularly important to design a graph reachability calculation method suitable for a parallel environment. The main process of the method adopted in the embodiment of the present invention is as follows: first, a simplified result is obtained by compressing the data on the graph, and then calculation is performed on the compressed result, and the accessibility is judged based on the intersection of the descendant node set and the ances...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention belongs to the field of data processing for large graphs and relates to a generation and search method for reachability chain list of a directed graph in the parallel environment. The method includes distributing the directed graph to every processor which stores nodes in the graph and sub-nodes corresponding to the nodes; compressing graph data split to the processors; calculating a backbone node reachability code of a backbone graph; building a chain index; building a skip list on the chain index; allowing data communication among the processors; allowing each processor to send skip list information to other processors; allowing each processor to upgrade own skip list information; and building a reachability index of a total graph. Through use of graph reachability compression technology in the parallel environment, the size of graph data is greatly reduced, system computing load is reduced, and a system can process the graph data on a larger scale. The method has the advantages that the speed of reading data from a disk is higher, search speed is indirectly increased, accuracy of search results is guaranteed, and network communication cost and search time are reduced greatly for a parallel computing system during searching.

Description

technical field [0001] The invention belongs to the field of large graph data processing, and in particular relates to a method for generating and querying a directed graph reachability linked list in a parallel environment. Background technique [0002] Graphs are an important data structure in the computer field. Nowadays, a large number of information processing uses graphs as data structures, and the demand for various operations on graphs continues to increase. As a basic operation on graphs, the graph accessibility query operation has important applications in semantic networks, biological networks, and social networks. At the same time, graph accessibility is also a basic algorithm for advanced applications of graph data. The definition of the accessibility of a graph is as follows. For a directed graph G, the node set on the graph is set to V, and the edge set is set to E. The reachability calculation of a directed graph is to judge the nodes of a directed graph Whe...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F17/30
Inventor 谷峪王彪于戈鲍玉斌
Owner NORTHEASTERN UNIV LIAONING
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Eureka Blog
Learn More
PatSnap group products