Dynamic Shortest Path Monitoring in Spatial Networks

With the increasing availability of real-time traffic information, dynamic spatial networks are pervasive nowadays and path planning in dynamic spatial networks becomes an important issue. In this light, we propose and investigate a novel problem of dynamically monitoring shortest paths in spatial networks (DSPM query). When a traveler aims to a destination, his/her shortest path to the destination may change due to two reasons: 1) the travel costs of some edges have been updated and 2) the traveler deviates from the pre-planned path. Our target is to accelerate the shortest path computing in dynamic spatial networks, and we believe that this study may be useful in many mobile applications, such as route planning and recommendation, car navigation and tracking, and location-based services in general. This problem is challenging due to two reasons: 1) how to maintain and reuse the existing computation results to accelerate the following computations, and 2) how to prune the search space effectively. To overcome these challenges, filter-and-refinement paradigm is adopted. We maintain an expansion tree and define a pair of upper and lower bounds to prune the search space. A series of optimization techniques are developed to accelerate the shortest path computing. The performance of the developed methods is studied in extensive experiments based on real spatial data.     

BASE: an assistant tool to precisely simulate energy consumption and reliability of energy‐efficient storage systems

The concept of green storage in cluster computing has recently attracted enormous interest among researchers. Consequently, several energy‐efficient solutions, such as multi‐speed disks and disk spin down methods, have been proposed to conserve power in storage systems and improve disk access. Some researchers have assessed their proposed solutions via simulations, while others have used real‐world experiments. Both methods have advantages and disadvantages. Simulations can more swiftly assess the benefits of energy‐efficient solutions, but various measurement errors can arise from procedural shortcomings. For instance, many power simulation tools fail to consider how heat increases the power overhead of disk operations. Some researchers claim that their modeling methods reduce the measurement error to 5% in the single disk model. However, the demand for large‐scale storage systems is growing rapidly. Traditional power measurement using a single disk model is unsuited to such systems because of their complex storage architecture and the unpredictability of numerous disks. Consequently, a number of studies have conducted real machine experiments to assess the performance of their solutions in terms of power conservation, but such experiments are time consuming. To address this problem, this study proposes an efficient simulation tool called Benchmark Analysis Software for Energy‐efficient Solution (BASE), which can accurately estimate disks' power consumption in large‐scale storage systems. We evaluate the performance of BASE on real‐world traces of Academia Sinica (Taiwan) and Florida International University. BASE incorporates an analytical method for assessing the reliability of energy‐efficient solutions. The analytical results demonstrate that the measurement error of BASE is 2.5% lower than that achieved in real‐world experiments involving energy‐estimation experiments. Moreover, the results of simulations to assess solution reliability are identical to those obtained through real‐world experiments. Copyright © 2015 Copyright © 2015 John Wiley & Sons, Ltd.     

Image structure rebuilding technique using fractal dimension on the best match patch searching

Since most images were built with regular textures and structures, the exemplar-based inpainting technique has become a brand-new solution for renovating degraded images by searching a match patch. This characteristic has also been named as the local self-similarity. Nevertheless, traditional exemplar-based methods try to find the best match patch in the whole image with only one direction; thus, often leading to a non-ideal repairing result. In this article, we propose a novel patch matching technique to rebuild the structure and texture of image, in which the surrounding information of the patch is fully concerned. Aside from determining a more precise filling priority by the sparsity of the image structure, we have applied the difference of fractal dimension to enhance the similarity between the source patch and the target patch. Experimental results have demonstrated the superiority of the proposed technique over related works in the renovating accuracy.     

HD-GDD: high dimensional graph dominance drawing approach for reachability query

Efficiently answering reachability queries, which checks whether one vertex can reach another in a directed graph, has been studied extensively during recent years. However, the size of the graph that people are facing and generating nowadays is growing so rapidly that simple algorithms, such as BFS and DFS, are no longer feasible. Although Refined Online Search algorithms can scale to large graphs, they all suffer from the false positive problem. In this paper, we analyze the cause of false positive and propose an efficient High Dimensional coordinate generating method based on Graph Dominance Drawing (HD-GDD) to answer reachability queries in linear or even constant time. We conduct experiments on different graph structures and different graph sizes to fully evaluate the performance and behavior of our proposal. Empirical results demonstrate that our method outperforms state-of-the-art algorithms and can handle extensive graphs.     

On the Uniqueness of User Equilibrium Flow with Speed Limit

This technical note focuses on the link flow uniqueness of user equilibrium (UE) with speed limits. Under a mild assumption on the monotonicity of link travel time function, the UE link flow solutions are well recognized to be unique. However, the incorporation of speed limits in the network has undermined the strict monotonicity of link travel time functions, thus the UE flows on the links with speed limits may not be unique. This note addresses the uniqueness problem with two major contributions. First, a polyhedron defined on links is provided, and it is proven that the UE link flow is unique if and only if the polyhedron only contains one value. Second, two concise methods are proposed to mathematically check whether the polyhedron is a singleton, which can be easily solved and convenient for practical use.