Efficient processing of distance–time <i>k</i> th‐order skyline queries in bicriteria networks

You are here: Homepage > Search

Efficient processing of distance–time k th‐order skyline queries in bicriteria networks

Free access

Zheng, Jiping / Jiang, Shunqing / Chen, Jialiang / Yu, Wei

With the increasing complexity of traffic conditions in road networks, the nearest destination cannot be necessarily reached in the fastest time. The traditional nearest neighbor (NN) and k NN searches in spatial network databases with single cost criterion are often strongly restrictive. In this paper, the authors consider the problem of k th‐order skyline queries in bicriteria networks, where edges represent road segments. Their proposed k th‐order skyline queries consider distance, time preferences of each edge, thus having two kinds of skyline queries, named distance optimal k th‐order skyline query (DO‐k OSQ) and time optimal k th‐OSQ (TO‐k OSQ). They design algorithms for the two kinds of skyline queries in bicriteria networks based on incremental network expansion method and further develop a maximum distance/time restriction strategy to improve the efficiency of the algorithms. Experimental results show that all of their methods are far below 1000 input–output input/output (IO) accesses and 1 s of central processing unit (CPU) time. For real road networks, their k OSQ+ queries need only 51.6% IO accesses and 59.6% CPU time of those for k OSQ queries, whereas for the larger road network the percentages are 51.8% and 51.2%, respectively. Thus, the results indicate the efficiency and effectiveness of their proposed methods.