TY - JOUR
T1 - Reverse Nearest Neighbor Search in Semantic Trajectories for Location-Based Services
AU - Pan, Xiao
AU - Nie, Shili
AU - Hu, Haibo
AU - Yu, Philip S.
AU - Guo, Jingfeng
N1 - This research was partially supported by the Grant from the
Natural Science Foundation of China (No. 61303017, 61572413, and U1636205), the Research Grants Council, Hong Kong SAR, China (Grant No: 15238116, 15222118 and C1008-16G), the Natural Science Foundation of Hebei Province (F2018210109), the Hebei Education Department (No. ZD2018040), the Foundation of Introduction of Oversea Scholar(C201822), the Fourth Outstanding Youth Foundation of Shijiazhuang Tiedao University, and by NSF under Grants III-1526499, III-1763325, III-1909323, and CNS-1930941.
Publisher Copyright:
© 2008-2012 IEEE.
PY - 2022/3
Y1 - 2022/3
N2 - In resource planning scenarios, reverse kk nearest neighbor search plays an important role. However, the existing reverse kk nearest neighbor search on trajectories only supports spatial features of trajectories. In this article, we introduce reverse kk nearest neighbors query on semantic trajectories (RkkNNST). Given a query point from a set of geo-textual objects (e.g., POIs), the query finds those trajectories that take this query point as one of their kk nearest geo-textual correlative objects. To efficiently answer RkkNNST queries, we propose a novel index IMC-tree, which organizes the global and local geo-textual information on semantic trajectories. A branch-and-bound search algorithm DOTA is then designed to traverse IMC-tree with various pruning rules. To speed up the computation of correlative distance, we also design an inverted-file-based algorithm to compute without enumerating all combinations of geo-textual objects. Experiments on a real dataset validate the effectiveness and efficiency of our proposed algorithms.
AB - In resource planning scenarios, reverse kk nearest neighbor search plays an important role. However, the existing reverse kk nearest neighbor search on trajectories only supports spatial features of trajectories. In this article, we introduce reverse kk nearest neighbors query on semantic trajectories (RkkNNST). Given a query point from a set of geo-textual objects (e.g., POIs), the query finds those trajectories that take this query point as one of their kk nearest geo-textual correlative objects. To efficiently answer RkkNNST queries, we propose a novel index IMC-tree, which organizes the global and local geo-textual information on semantic trajectories. A branch-and-bound search algorithm DOTA is then designed to traverse IMC-tree with various pruning rules. To speed up the computation of correlative distance, we also design an inverted-file-based algorithm to compute without enumerating all combinations of geo-textual objects. Experiments on a real dataset validate the effectiveness and efficiency of our proposed algorithms.
KW - geo-textual objects
KW - Location-based services
KW - reverse nearest neighbor queries
KW - semantic-enriched trajectories
UR - http://www.scopus.com/inward/record.url?scp=85128475985&partnerID=8YFLogxK
U2 - 10.1109/TSC.2020.2968309
DO - 10.1109/TSC.2020.2968309
M3 - Journal article
AN - SCOPUS:85128475985
SN - 1939-1374
VL - 15
SP - 986
EP - 999
JO - IEEE Transactions on Services Computing
JF - IEEE Transactions on Services Computing
IS - 2
M1 - 8966480
ER -