اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMulti-Constraint Shortest Path using Forest Hop Labeling
145
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The textit{Multi-Constraint Shortest Path (MCSP)} problem aims to find the shortest path between two nodes in a network subject to a given constraint set. It is typically processed as a textit{skyline path} problem. However, the number of intermediate skyline paths becomes larger as the network size increases and the constraint number grows, which brings about the dramatical growth of computational cost and further makes the existing index-based methods hardly capable of obtaining the complete exact results. In this paper, we propose a novel high-dimensional skyline path concatenation method to avoid the expensive skyline path search, which then supports the efficient construction of hop labeling index for textit{MCSP} queries. Specifically, a set of insightful observations and techniques are proposed to improve the efficiency of concatenating two skyline path set, a textit{n-Cube} technique is designed to prune the concatenation space among multiple hops, and a textit{constraint pruning} method is used to avoid the unnecessary computation. Furthermore, to scale up to larger networks, we propose a novel textit{forest hop labeling} which enables the parallel label construction from different network partitions. Our approach is the first method that can achieve both accuracy and efficiency for textit{MCSP} query answering. Extensive experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art solutions.
قيم البحث
اقرأ أيضاً
In two-stage robust optimization the solution to a problem is built in two stages: In the first stage a partial, not necessarily feasible, solution is exhibited. Then the adversary chooses the worst scenario from a predefined set of scenarios. In the
second stage, the first-stage solution is extended to become feasible for the chosen scenario. The costs at the second stage are larger than at the first one, and the objective is to minimize the total cost paid in the two stages. We give a 2-approximation algorithm for the robust mincut problem and a ({gamma}+2)-approximation for the robust shortest path problem, where {gamma} is the approximation ratio for the Steiner tree. This improves the factors (1+sqrt2) and 2({gamma}+2) from [Golovin, Goyal and Ravi. Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems. STACS 2006]. In addition, our solution for robust shortest path is simpler and more efficient than the earlier ones; this is achieved by a more direct algorithm and analysis, not using some of the standard demand-robust optimization techniques.
The determination of time-dependent collision-free shortest paths has received a fair amount of attention. Here, we study the problem of computing a time-dependent shortest path among growing discs which has been previously studied for the instance w
here the departure times are fixed. We address a more general setting: For two given points $s$ and $d$, we wish to determine the function $mathcal{A}(t)$ which is the minimum arrival time at $d$ for any departure time $t$ at $s$. We present a $(1+epsilon)$-approximation algorithm for computing $mathcal{A}(t)$. As part of preprocessing, we execute $O({1 over epsilon} log({mathcal{V}_{r} over mathcal{V}_{c}}))$ shortest path computations for fixed departure times, where $mathcal{V}_{r}$ is the maximum speed of the robot and $mathcal{V}_{c}$ is the minimum growth rate of the discs. For any query departure time $t geq 0$ from $s$, we can approximate the minimum arrival time at the destination in $O(log ({1 over epsilon}) + loglog({mathcal{V}_{r} over mathcal{V}_{c}}))$ time, within a factor of $1+epsilon$ of optimal. Since we treat the shortest path computations as black-box functions, for different settings of growing discs, we can plug-in different shortest path algorithms. Thus, the exact time complexity of our algorithm is determined by the running time of the shortest path computations.
In this paper we address the problem of computing a sparse subgraph of a weighted directed graph such that the exact distances from a designated source vertex to all other vertices are preserved under bounded weight increment. Finding a small sized s
ubgraph that preserves distances between any pair of vertices is a well studied problem. Since in the real world any network is prone to failures, it is natural to study the fault tolerant version of the above problem. Unfortunately, it turns out that there may not always exist such a sparse subgraph even under single edge failure [Demetrescu emph{et al.} 08]. However in real applications it is not always the case that a link (edge) in a network becomes completely faulty. Instead, it can happen that some links become more congested which can easily be captured by increasing weight on the corresponding edges. Thus it makes sense to try to construct a sparse distance preserving subgraph under the above weight increment model. To the best of our knowledge this problem has not been studied so far. In this paper we show that given any weighted directed graph with $n$ vertices and a source vertex, one can construct a subgraph that contains at most $e cdot (k-1)!2^kn$ many edges such that it preserves distances between the source and all other vertices as long as the total weight increment is bounded by $k$ and we are allowed to have only integer valued (can be negative) weight on each edge and also weight of an edge can only be increased by some positive integer. Next we show a lower bound of $ccdot 2^kn$, for some constant $c ge 5/4$, on the size of the subgraph. We also argue that restriction of integer valued weight and integer valued weight increment are actually essential by showing that if we remove any one of these two restrictions we may need to store $Omega(n^2)$ edges to preserve distances.
Given two locations $s$ and $t$ in a road network, a distance query returns the minimum network distance from $s$ to $t$, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find import
ant applications in practice, and a plethora of solutions have been proposed in past few decades. The existing solutions, however, are optimized for either practical or asymptotic performance, but not both. In particular, the techniques with enhanced practical efficiency are mostly heuristic-based, and they offer unattractive worst-case guarantees in terms of space and time. On the other hand, the methods that are worst-case efficient often entail prohibitive preprocessing or space overheads, which render them inapplicable for the large road networks (with millions of nodes) commonly used in modern map applications. This paper presents {em Arterial Hierarchy (AH)}, an index structure that narrows the gap between theory and practice in answering shortest path and distance queries on road networks. On the theoretical side, we show that, under a realistic assumption, AH answers any distance query in $tilde{O}(log r)$ time, where $r = d_{max}/d_{min}$, and $d_{max}$ (resp. $d_{min}$) is the largest (resp. smallest) $L_infty$ distance between any two nodes in the road network. In addition, any shortest path query can be answered in $tilde{O}(k + log r)$ time, where $k$ is the number of nodes on the shortest path. On the practical side, we experimentally evaluate AH on a large set of real road networks with up to twenty million nodes, and we demonstrate that (i) AH outperforms the state of the art in terms of query time, and (ii) its space and pre-computation overheads are moderate.
Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving todays massive networks. There
fore, it is required to find approximation methods to enable scalable graph processing with a significant speedup. In this paper, we utilize vector embeddings learnt by deep learning techniques to approximate the shortest paths distances in large graphs. We show that a feedforward neural network fed with embeddings can approximate distances with relatively low distortion error. The suggested method is evaluated on the Facebook, BlogCatalog, Youtube and Flickr social networks.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
