Linear path skylines in multicriteria networks

In many graph applications, computing cost-optimal paths between two locations is an important task for routing and distance computation. Depending on the network multiple cost criteria might be of interest. Examples are travel time, energy consumption and toll fees in road networks. Path skyline queries compute the set of pareto optimal paths between two given locations. However, the number of skyline paths increases exponentially with the distance between the locations and the number of cost criteria. Thus, the result set might be too big to be of any use. In this paper, we introduce multicriteria linear path skyline queries. A linear path skyline is the subset of the conventional path skyline where the paths are optimal under a linear combination of their cost values. We argue that cost vectors being optimal with respect to a weighted sum are intuitive to understand and therefore, more interesting in many cases. We show that linear path skylines are convex hulls of an augmented solution space and propose an algorithm which utilizes this observation to efficiently compute the complete linear path skyline. To further control the size of the result set, we introduce an approximate version of our algorithm guaranteeing a certain level of optimality for each possible weighting. In our experimental evaluation, we show that our approach computes linear path skylines significantly faster than previous approaches, including those computing the complete path skyline.