M.: Paretoprep: Fast computation of path skylines queries

Computing cost optimal paths in network data is a very important task in many application areas like transporta-tion networks, computer networks or social graphs. In many cases, the cost of an edge can be described by various cost criteria. For example, in a road network possible cost cri-teria are distance, time, ascent, energy consumption or toll fees. In such a multicriteria network, a route or path sky-line query computes the set of all paths having pareto opti-mal costs, i.e. each result path is optimal for different user preferences. In this paper, we propose a new method for computing route skylines which significantly decreases pro-cessing time and memory consumption. Furthermore, our method does not rely on any precomputation or indexing method and thus, it is suitable for dynamically changing edge costs. Our experiments demonstrate that our method outperforms state of the art approaches and allows highly efficient path skyline computation without any preprocess-ing. 1