Open AccessResearch on K Nearest Neighbor Skyline Query in Time Dependent Road Network
Author(s) -
Lixiang Song,
Fei Ke
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1848/1/012140
Subject(s) - skyline , computer science , data mining , k nearest neighbors algorithm , landmark , pruning , set (abstract data type) , shortest path problem , path (computing) , algorithm , artificial intelligence , theoretical computer science , graph , agronomy , biology , programming language
In recent years, with the increase for query preference, skyline query in road networks has gradually become a research hot topic. In order to help users get the desired query result, we propose a new algorithm. Firstly, we select landmark heuristically and establish corresponding shortest path tree (SPT). Then we construct a skyline matrix index called time dependent matrix index (TDMI), which help us associate the updated result set with dynamic k nearest neighbor (KNN) and simplify the non-space dominance relationship better. Finally, with SPT, TDMI, KNN and dynamic pruning conditions, an algorithm, the TDMI-KS algorithm, is proposed to rapidly answer the query result. Extensive experiments using Oldenburg road network datasets demonstrate the effectiveness and the efficiency of our proposed TDMI-KS algorithms.