Open AccessEfficient processing of distance–time k th‐order skyline queries in bicriteria networks
Author(s) -
Zheng Jiping,
Jiang Shunqing,
Chen Jialiang,
Yu Wei
Publication year - 2019
Publication title -
iet intelligent transport systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.579
H-Index - 45
eISSN - 1751-9578
pISSN - 1751-956X
DOI - 10.1049/iet-its.2018.5036
Subject(s) - skyline , computer science , enhanced data rates for gsm evolution , order (exchange) , k nearest neighbors algorithm , execution time , time complexity , data mining , algorithm , distributed computing , artificial intelligence , finance , economics
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.