A Speedup Technique For Dynamic Graphs Using Partitioning Strategy And Multithreaded Approach
| المصدر: | مجلة جامعة الملك سعود - علوم الحاسب والمعلومات |
|---|---|
| الناشر: | جامعة الملك سعود |
| المؤلف الرئيسي: | Kalpana, R. (Author) |
| مؤلفين آخرين: | Thambidurai, P. (Co-Author) |
| المجلد/العدد: | مج26, ع1 |
| محكمة: | نعم |
| الدولة: |
السعودية |
| التاريخ الميلادي: |
2014
|
| الصفحات: | 111 - 119 |
| DOI: |
10.33948/0584-026-001-011 |
| ISSN: |
1319-1578 |
| رقم MD: | 973038 |
| نوع المحتوى: | بحوث ومقالات |
| اللغة: | الإنجليزية |
| قواعد المعلومات: | science |
| مواضيع: | |
| كلمات المؤلف المفتاحية: |
Dijkstra’s Algorithm | Speedup Techniques | Dynamic Graphs | Parallel Programming
|
| رابط المحتوى: |
| المستخلص: |
There are many pre-processing-based speedup techniques for shortest path problems that are available in the literature. These techniques have an increased demand because of large datasets in such applications such as roadmaps, web search engines and mobile data sets. Pre-processing for the Time-Dependent Shortest Path Problem is still a demanding process that involves graph or network partitioning strategy. Efficient pre-processing of graphs or networks reduces the shortest path computation time while parallelizing the pre-processing phase improves the speedup of the system. In this paper, a speedup technique called Recursive Spectral Bisection (RSB) combined with the Elliptic Convolution of the shortest path method is proposed for dynamic Time-Dependent networks. The same method has been parallelized, and the results are tested on three types of graphs. It is observed that the Time-Dependent RSB combined with the Elliptic Convolution of the shortest path method has no update time, and the Query Performance Loss (QPL) is reduced in planar and road networks compared to random networks. In road networks, the proposed method achieves an average speed up in a QPL of 140. The use of the Parallel speedup technique results in an average speed up in a QPL of more than 1 in the planar and road networks. |
|---|---|
| ISSN: |
1319-1578 |
عناصر مشابهة
-
MSP: Multiple Sub Graph Query Processing Using Structure Based Graph Partitioning Strategy And Map Reduce
بواسطة: Fathimabi, Shaik منشور: (2019) -
Graph Neural Networks Based Approach for Airport Gate Assignment Problem
بواسطة: Ben Aissa, Nour El Houda Sayah منشور: (2021) -
Investigating Non-Visual Presentation of Graphs Using the Novint Falcon
بواسطة: Al Abbadi, Reham منشور: (2012) -
A STUDY AND IMPLEMENTATION OF SOME VISIBILITY GRAPH ALGORITHMS
بواسطة: Al Anzi, Zeyad M. منشور: (1994) -
Maximal Assortative Matching for Complex Network Graphs
بواسطة: Meghanathan, Natarajan منشور: (2016)
