Finding skyline paths in road networks
作者： Yuan Tian , Ken C. K. Lee , Wang-Chien Lee
关键词: Geography 、 Path (graph theory) 、 Skyline 、 Data mining 、 Any-angle path planning 、 Set (abstract data type) 、 Scope (computer science) 、 Path search 、 Location-based service 、 Computation
摘要: This paper presents a research study on skyline path queries. Given source s and destination d road network multiple search criteria (e.g., short distance travel time), query returns set of non-dominated paths from to d. These are called paths. Efficient computation queries is very challenging due expensive traversals extensive comparisons in dominance tests. In this paper, we explore the characteristics paths, based which novel algorithm SkyPath proposed. To narrow down scope for result partial test full devised as two components SkyPath. Evaluation results show superiority over state-of-the-art approaches.
acm.org
elsevier.com
sci-hub.se 参考文章(17)
S. Borzsony, D. Kossmann, K. Stocker, The Skyline operator international conference on data engineering. pp. 421- 430 ,(2001) , 10.1109/ICDE.2001.914855
F. Guerriero, R. Musmanno, Label correcting methods to solve multicriteria shortest path problems Journal of Optimization Theory and Applications. ,vol. 111, pp. 589- 613 ,(2001) , 10.1023/A:1012602011914
Ilaria Bartolini, Paolo Ciaccia, Marco Patella, SaLSa Proceedings of the 15th ACM international conference on Information and knowledge management - CIKM '06. pp. 405- 414 ,(2006) , 10.1145/1183614.1183674
J.M. Coutinho-Rodrigues, J.C.N. Clı́maco, J.R. Current, An interactive bi-objective shortest path approach: searching for unsupported nondominated solutions Computers & Operations Research. ,vol. 26, pp. 789- 798 ,(1999) , 10.1016/S0305-0548(98)00094-X
Janusz Granat, Francesca Guerriero, The interactive analysis of the multicriteria shortest path problem by the reference point method European Journal of Operational Research. ,vol. 151, pp. 103- 118 ,(2003) , 10.1016/S0377-2217(02)00594-5
John R. Current, Charles S. Revelle, Jared L. Cohon, An interactive approach to identify the best compromise solution for two objective shortest path problems Computers & Operations Research. ,vol. 17, pp. 187- 198 ,(1990) , 10.1016/0305-0548(90)90042-6
Ernesto Queirós Vieira Martins, On a multicriteria shortest path problem European Journal of Operational Research. ,vol. 16, pp. 236- 245 ,(1984) , 10.1016/0377-2217(84)90077-8
J. Brumbaugh-Smith, D. Shier, An empirical investigation of some bicriterion shortest path algorithms European Journal of Operational Research. ,vol. 43, pp. 216- 224 ,(1989) , 10.1016/0377-2217(89)90215-4
João Carlos Namorado Climaco, Ernesto Queirós Vieira Martins, A bicriterion shortest path algorithm European Journal of Operational Research. ,vol. 11, pp. 399- 404 ,(1982) , 10.1016/0377-2217(82)90205-3
Paola Modesti, Anna Sciomachen, A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks European Journal of Operational Research. ,vol. 111, pp. 495- 508 ,(1998) , 10.1016/S0377-2217(97)00376-7