Towards Efficient Path Skyline Computation in Bicriteria Networks

Path skyline query is a fundamental problem in bicriteria network analysis and is widely applied in a variety of applications. Given a source s and a destination t in a bicriteria network G, path skyline query aims to identify all the skyline paths from s to t in G. In the literature, \(\mathsf {PSQ}\) is a fundamental algorithm for path skyline query and is also used as a building block for the afterwards proposed algorithms. In \(\mathsf {PSQ}\), a key operation is to record the skyline paths from s to v for each node v that is possible on the skyline paths from s to t. However, to obtain the skyline paths for v, \(\mathsf {PSQ}\) has to maintain other paths that are not skyline paths for v, which makes \(\mathsf {PSQ}\) inefficient. Motivated by this, in this paper, we propose a new algorithm \(\mathsf {PSQ^+}\) for the path skyline query. By adopting an ordered path exploring strategy, our algorithm can totally avoid the fruitless path maintenance problem in \(\mathsf {PSQ}\). We evaluate our proposed algorithm on real networks and the experimental results demonstrate the efficiency of our proposed algorithm. Besides, the experimental results also demonstrate the algorithm that uses \(\mathsf {PSQ}\) as a building block for the path skyline query can achieve a significant performance improvement after we substitute \(\mathsf {PSQ^+}\) for \(\mathsf {PSQ}\).