Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Shortest path key node query method based on Spark distributed system

A distributed system and the shortest path technology, applied in the field of information processing, can solve the problems of long time consumption and achieve the effect of reducing the occupied space

Inactive Publication Date: 2015-10-28
SHANGHAI JIAO TONG UNIV
View PDF7 Cites 6 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, this technology needs to aggregate and store data hierarchically. For a given point pair, there are only two central points. When querying, all nodes need to be traversed, which takes a long time

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
  • Shortest path key node query method based on Spark distributed system
  • Shortest path key node query method based on Spark distributed system
  • Shortest path key node query method based on Spark distributed system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0033]The Spark platform versions involved in this embodiment are Hadoop2.4.1 and Spark1.3.0; the compilation tool version of the Spark platform is sbt0.13.4, and the programming language versions are Java1.7.0 and scala2.10.5. The Spark platform includes a cluster of 9 workers, each with 6 cores and 18GB of memory; 9 workers have a total of 54 cores and 164GB of memory.

[0034] The figure G that present embodiment embodiment adopts is from 9 th Full map or submap of DIMACS road network NWs8324, BAYs15164, Floridas52781 or NWs111729.

[0035] Such as figure 1 As shown, this embodiment includes the following steps:

[0036] Step 1. Sorting all the nodes v in the graph G according to their criticality to form a total order o(v).

[0037] Said road network is a network system structure composed of traffic arterial roads, secondary arterial roads and large and small branch roads in a certain density and form.

[0038] The road network is expressed as a directed graph with no...

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 discloses a shortest path key node query method based on a Spark distributed system. Through carrying out pretreatment on a total node sequence formed by ranking all nodes in a graph according to the key degree on a Spark platform, a hierarchical label corresponding to each node is obtained, shortest path key node query between any node pair can be realized, and key nodes with the specified number on the shortest path are returned. Thus, a large amount of access work is completed during the pretreatment stage based on the Spark platform, the occupied space in the case of search can be narrowed, and certain extension is realized.

Description

technical field [0001] The invention relates to a technology in the field of information processing, in particular to a shortest path key point query method based on a Spark distributed system. Background technique [0002] At present, there are many shortest path algorithms, that is, the shortest path from node s to node t is recorded as SP<s,t>, and the corresponding shortest distance is dist<s,t>. Disjktra is a classic algorithm for the single-source shortest path problem in graph theory, but its efficiency cannot meet the mainstream needs. In recent years, many related high-efficiency algorithms have emerged, such as A*, a heuristic point-to-point shortest path direct search algorithm; such as the ALT algorithm that combines the idea of ​​landmarks and applies triangle side length inequality constraints; such as Abraham et al. Hub labeling algorithm (hub labeling, HL); and contraction hierarchy algorithm (Contraction Hierarchies, CH), a preprocessing shortes...

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 Applications(China)
IPC IPC(8): G06F17/30
CPCG06F16/2453G06F16/2471
Inventor 姚斌马菁过敏意唐飞龙周憬宇吴晨涛薛广涛
Owner SHANGHAI JIAO TONG UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com