Skip to main content
Top

2018 | OriginalPaper | Chapter

Towards Efficient Path Skyline Computation in Bicriteria Networks

Authors : Dian Ouyang, Long Yuan, Fan Zhang, Lu Qin, Xuemin Lin

Published in: Database Systems for Advanced Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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}\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Brumbaugh-Smith, J., Shier, D.: An empirical investigation of some bicriterion shortest path algorithms. Eur. J. Oper. Res. 43(2), 216–224 (1989)MathSciNetCrossRef Brumbaugh-Smith, J., Shier, D.: An empirical investigation of some bicriterion shortest path algorithms. Eur. J. Oper. Res. 43(2), 216–224 (1989)MathSciNetCrossRef
2.
go back to reference Clímaco, J.C., Pascoal, M.: Multicriteria path and tree problems: discussion on exact algorithms and applications. Int. Trans. Oper. Res. 19(1–2), 63–98 (2012)MathSciNetCrossRef Clímaco, J.C., Pascoal, M.: Multicriteria path and tree problems: discussion on exact algorithms and applications. Int. Trans. Oper. Res. 19(1–2), 63–98 (2012)MathSciNetCrossRef
3.
go back to reference Climaco, J.C.N., Martins, E.Q.V.: A bicriterion shortest path algorithm. Eur. J. Oper. Res. 11(4), 399–404 (1982)MathSciNetCrossRef Climaco, J.C.N., Martins, E.Q.V.: A bicriterion shortest path algorithm. Eur. J. Oper. Res. 11(4), 399–404 (1982)MathSciNetCrossRef
4.
go back to reference Delling, D., Wagner, D.: Pareto paths with SHARC. In: Proceedings of the SEA, pp. 125–136 (2009)CrossRef Delling, D., Wagner, D.: Pareto paths with SHARC. In: Proceedings of the SEA, pp. 125–136 (2009)CrossRef
5.
go back to reference Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectr. 22(4), 425–460 (2000)MathSciNetCrossRef Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectr. 22(4), 425–460 (2000)MathSciNetCrossRef
6.
go back to reference Gabrel, V., Vanderpooten, D.: Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. Eur. J. Oper. Res. 139(3), 533–542 (2002)CrossRef Gabrel, V., Vanderpooten, D.: Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. Eur. J. Oper. Res. 139(3), 533–542 (2002)CrossRef
7.
go back to reference Garroppo, R.G., Giordano, S., Tavanti, L.: A survey on multi-constrained optimal path computation: exact and approximate algorithms. Comput. Netw. 54(17), 3081–3107 (2010)CrossRef Garroppo, R.G., Giordano, S., Tavanti, L.: A survey on multi-constrained optimal path computation: exact and approximate algorithms. Comput. Netw. 54(17), 3081–3107 (2010)CrossRef
9.
go back to reference Jang, S., Yoo, J.: Processing continuous skyline queries in road networks. In: Computer Science and Its Applications, pp. 353–356 (2008) Jang, S., Yoo, J.: Processing continuous skyline queries in road networks. In: Computer Science and Its Applications, pp. 353–356 (2008)
10.
go back to reference Kriegel, H.-P., Renz, M., Schubert, M.: Route skyline queries: a multi-preference path planning approach. In: Proceedings of the ICDE, pp. 261–272 (2010) Kriegel, H.-P., Renz, M., Schubert, M.: Route skyline queries: a multi-preference path planning approach. In: Proceedings of the ICDE, pp. 261–272 (2010)
12.
go back to reference Mote, J., Murthy, I., Olson, D.L.: A parametric approach to solving bicriterion shortest path problems. Eur. J. Oper. Res. 53(1), 81–92 (1991)CrossRef Mote, J., Murthy, I., Olson, D.L.: A parametric approach to solving bicriterion shortest path problems. Eur. J. Oper. Res. 53(1), 81–92 (1991)CrossRef
13.
go back to reference Mouratidis, K., Lin, Y., Yiu, M.L.: Preference queries in large multi-cost transportation networks. In: Proceedings of the ICDE, pp. 533–544 (2010) Mouratidis, K., Lin, Y., Yiu, M.L.: Preference queries in large multi-cost transportation networks. In: Proceedings of the ICDE, pp. 533–544 (2010)
14.
go back to reference Müller-Hannemann, M., Weihe, K.: On the cardinality of the Pareto set in bicriteria shortest path problems. Ann. Oper. Res. 147(1), 269–286 (2006)MathSciNetCrossRef Müller-Hannemann, M., Weihe, K.: On the cardinality of the Pareto set in bicriteria shortest path problems. Ann. Oper. Res. 147(1), 269–286 (2006)MathSciNetCrossRef
15.
go back to reference Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest path problems. Comput. Oper. Res. 36(4), 1299–1331 (2009)MathSciNetCrossRef Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest path problems. Comput. Oper. Res. 36(4), 1299–1331 (2009)MathSciNetCrossRef
16.
go back to reference Sacharidis, D., Bouros, P., Chondrogiannis, T.: Finding the most preferred path. In: Proceedings of the SIGSPATIAL (2017) Sacharidis, D., Bouros, P., Chondrogiannis, T.: Finding the most preferred path. In: Proceedings of the SIGSPATIAL (2017)
18.
go back to reference Shekelyan, M., Jossé, G., Schubert, M.: Linear path skylines in multicriteria networks. In: Proceedings of the ICDE, pp. 459–470 (2015) Shekelyan, M., Jossé, G., Schubert, M.: Linear path skylines in multicriteria networks. In: Proceedings of the ICDE, pp. 459–470 (2015)
19.
go back to reference Skriver, A.J.: A classification of bicriterion shortest path (BSP) algorithms. Asia-Pac. J. Oper. Res. 17(2), 199 (2000)MathSciNetMATH Skriver, A.J.: A classification of bicriterion shortest path (BSP) algorithms. Asia-Pac. J. Oper. Res. 17(2), 199 (2000)MathSciNetMATH
20.
go back to reference Skriver, A.J., Andersen, K.A.: A label correcting approach for solving bicriterion shortest-path problems. Comput. Oper. Res. 27(6), 507–524 (2000)MathSciNetCrossRef Skriver, A.J., Andersen, K.A.: A label correcting approach for solving bicriterion shortest-path problems. Comput. Oper. Res. 27(6), 507–524 (2000)MathSciNetCrossRef
21.
go back to reference Storandt, S.: Route planning for bicycles-exact constrained shortest paths made practical via contraction hierarchy. In: ICAPS, vol. 4, p. 46 (2012) Storandt, S.: Route planning for bicycles-exact constrained shortest paths made practical via contraction hierarchy. In: ICAPS, vol. 4, p. 46 (2012)
22.
go back to reference Tarapata, Z.: Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms. Int. J. Appl. Math. Comput. Sci. 17(2), 269–287 (2007)MathSciNetCrossRef Tarapata, Z.: Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms. Int. J. Appl. Math. Comput. Sci. 17(2), 269–287 (2007)MathSciNetCrossRef
23.
go back to reference Ulungu, E., Teghem, J., Fortemps, P., Tuyttens, D.: MOSA method: a tool for solving multiobjective combinatorial optimization problems. J. Multicriteria Decis. Anal. 8(4), 221 (1999)CrossRef Ulungu, E., Teghem, J., Fortemps, P., Tuyttens, D.: MOSA method: a tool for solving multiobjective combinatorial optimization problems. J. Multicriteria Decis. Anal. 8(4), 221 (1999)CrossRef
24.
go back to reference Yang, B., Guo, C., Jensen, C.S., Kaul, M., Shang, S.: Multi-cost optimal route planning under time-varying uncertainty. In: Proceedings of the ICDE (2014) Yang, B., Guo, C., Jensen, C.S., Kaul, M., Shang, S.: Multi-cost optimal route planning under time-varying uncertainty. In: Proceedings of the ICDE (2014)
Metadata
Title
Towards Efficient Path Skyline Computation in Bicriteria Networks
Authors
Dian Ouyang
Long Yuan
Fan Zhang
Lu Qin
Xuemin Lin
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-91452-7_16

Premium Partner