Lehrstuhl  |  Institut  |  Fakultät  |  LMU

PAROS: Pareto Optimal Route Selection

Published at SigMod 2010.

Conference Date: June 7, 2010
Conference Location: Indianapolis, Indiana, USA
Conference Title: ACM SIGMOD/PODS

Update: Paros is now open source and hosted at Google Code


Screenshot of Paros

Modern maps provide a variety of information about roads and their surrounding landscape allowing navigation systems to go beyond simple shortest path computation. In this demo, we show how the concept of skyline queries can be successfully adapted to routing problems considering multiple road attributes. In particular, we demonstrate how to compute several pareto-optimal paths which contain optimal results for a variety of user preferences. The PAROS-system has two main purposes. The first is to calculate the route skyline for a starting point and a destination. Our demonstrator visualizes the result set for up to three road attributes. Therefore, we provide a dual view on the computed skyline paths. The first view displays the result paths on the road map itself. The second view describes the result paths in the property space, displaying the trade-off between the underlying criteria. Thus, a user can browse through the results in order to find the path which fits best to his personal preferences. The second component of our system suits analysis issues. In this component, we illustrate the functionality of the underlying route skyline algorithm. Thus, we provide benchmark information about processing time and the search space visited during route skyline computation.

Copyright Notes:

Franz Graf, Hans-Peter Kriegel, Matthias Renz, Matthias Schubert
"PAROS: Pareto Optimal Route Selection", In Proceedings of the ACM International Conference on Management of Data (SIGMOD), Indianapolis, IN, 2010.

© ACM, 2010. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2010 international conference on Management of data (2010)



 author = {Graf, Franz and Kriegel, Hans-Peter and Renz, Matthias and Schubert, Matthias},
 title = {PAROS: pareto optimal route selection},
 booktitle = {SIGMOD '10: Proceedings of the 2010 international conference on Management of data},
 year = {2010},
 isbn = {978-1-4503-0032-2},
 pages = {1199--1202},
 location = {Indianapolis, Indiana, USA},
 doi = {},
 publisher = {ACM},
 address = {New York, NY, USA}