Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network

doi:10.11772/j.issn.1001-9081.2023101503

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (11): 3403-3410.DOI: 10.11772/j.issn.1001-9081.2023101503

• Data science and technology • Previous Articles Next Articles

Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network

Guoxiang CHEN, Ziqiang YU(), Haoyu ZHAO

School of Computer and Control Engineering，Yantai University，Yantai Shandong 264005，China

Received:2023-11-03 Revised:2024-01-14 Accepted:2024-01-24 Online:2024-11-13 Published:2024-11-10
Contact: Ziqiang YU
About author:CHEN Guoxiang， born in 1998， M. S. candidate. His research interests include spatio-temporal data processing.
ZHAO Haoyu， born in 1999， M. S. candidate. Her research interests include spatio-temporal data processing.
Supported by:
National Natural Science Foundation of China(62172351)

面向动态路网的移动对象分布式k近邻查询算法

陈国祥, 于自强(), 赵浩宇

烟台大学计算机与控制工程学院，山东烟台 264005

通讯作者: 于自强
作者简介:陈国祥（1998—），男，山东青岛人，硕士研究生，主要研究方向：时空数据处理
赵浩宇（1999—），男，山东临沂人，硕士研究生，主要研究方向：时空数据处理。
基金资助:
国家自然科学基金资助项目(62172351)

Abstract

Abstract:

The k-Nearest Neighbor （kNN） query in dynamic road network is an important problem in many Location-Based Services （LBS）. To address this problem， a distributed moving object kNN query algorithm named DkNN （Distributed k-Nearest Neighbor） was proposed for dynamic road networks. Firstly， the entire road network was divided into multiple subgraphs deployed in different nodes in the cluster. Then， the accurate kNN results were obtained by searching the subgraphs involved in the query range in parallel. Finally， the searching process of the query was optimized， and the query range pruning strategy as well as the query termination strategy was introduced. A full comparison and validation with three baseline algorithms on four road network datasets was performed. Experimental results show that the DkNN algorithm reduces the query time by 56.8% and the road network update time by 3 orders of magnitude compared to TEN^*-Index （Tree dEcomposition based kNN^* Index） algorithm. The DkNN algorithm can quickly respond to kNN query requests in dynamic road network and has a low update cost when dealing with road network updates.

Key words: dynamic road network, k Nearest Neighbor (kNN) query, distributed environment, Location-Based Services (LBS), spatio-temporal data processing

摘要：

动态路网k近邻（kNN）查询是许多基于位置的服务（LBS）中的一个重要问题。针对该问题，提出一种面向动态路网的移动对象分布式kNN查询算法DkNN（Distributed kNN）。首先，将整个路网划分为部署于集群中不同节点中的多个子图；其次，通过并行地搜索查询范围所涉及的子图得到精确的kNN结果；最后，优化查询的搜索过程，引入查询范围剪枝策略和查询终止策略。在4个道路网络数据集上与3种基线算法进行了充分对比和验证。实验结果显示，与TEN^*-Index （Tree dEcomposition based kNN^* Index）算法相比，DkNN算法的查询时间减少了56.8%，路网更新时间降低了3个数量级。DkNN算法可以快速响应动态路网中的kNN查询请求，且在处理路网更新时具有较低的更新成本。

关键词: 动态道路网络, k近邻查询, 分布式环境, 基于位置的服务, 时空数据处理

CLC Number:

TP392

Guoxiang CHEN, Ziqiang YU, Haoyu ZHAO. Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network[J]. Journal of Computer Applications, 2024, 44(11): 3403-3410.

陈国祥, 于自强, 赵浩宇. 面向动态路网的移动对象分布式k近邻查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3403-3410.

Figures/Tables 10

Fig. 1 Example of graph partitioning with 4 subgraphs

Tab. 1 Symbols and their meanings

属性	含义
$q i d$	查询id，声明消息所属查询
$v b$	子图查询起始顶点
$d i s t$	查询点到 $v b$ 的局部最短距离
$f r o m$	消息来源子图
$a c k$	消息确认标志

Tab. 1 Symbols and their meanings

属性	含义
$q i d$	查询id，声明消息所属查询
$v b$	子图查询起始顶点
$d i s t$	查询点到 $v b$ 的局部最短距离
$f r o m$	消息来源子图
$a c k$	消息确认标志

Tab. 2 Summary of parameters used in experiments

参数	解释	数值范围
k	近邻数	10， 20， 30， 40， 50
$μ$	移动对象数	1×10⁴， 2×10⁴， 3×10⁴， 4×10⁴， 5×10⁴0
m	子图数	10， 50， 100， 300， 500
$τ$	线程数	10， 12， 14， 16， 18， 20
α	路网更新比例	0.1， 0.2， 0.3， 0.4， 0.5

Tab. 2 Summary of parameters used in experiments

参数	解释	数值范围
k	近邻数	10， 20， 30， 40， 50
$μ$	移动对象数	1×10⁴， 2×10⁴， 3×10⁴， 4×10⁴， 5×10⁴0
m	子图数	10， 50， 100， 300， 500
$τ$	线程数	10， 12， 14， 16， 18， 20
α	路网更新比例	0.1， 0.2， 0.3， 0.4， 0.5

Fig. 2 Initialization time and space consumption of DkNN algorithm

Fig. 3 Influence of different parameter settings on query efficiency

Fig. 4 Influence of α on road network update time

Fig. 5 Cost comparison of preprocessing time and preprocessing space

Fig. 6 Query efficiency comparison

Tab. 3 Query time of each algorithm under default parameters

算法	查询时间	算法	查询时间
TEN^*-Index	375	SIMkNN	485
Dijkstra	555	DkNN	162

Tab. 4 Update time of each algorithm

路网更新比例 $α$	更新时间/ms
路网更新比例 $α$	TEN^*-Index	Dijkstra	SIMkNN	DkNN
0.1	20 134	90	115	11
0.2	20 752	178	218	14
0.3	21 335	319	333	19
0.4	22 135	385	432	23
0.5	23 075	438	559	28

Tab. 4 Update time of each algorithm

路网更新比例 $α$	更新时间/ms
路网更新比例 $α$	TEN^*-Index	Dijkstra	SIMkNN	DkNN
0.1	20 134	90	115	11
0.2	20 752	178	218	14
0.3	21 335	319	333	19
0.4	22 135	385	432	23
0.5	23 075	438	559	28

References 21

1	DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik， 1959， 1（1）：269-271.
2	PAPADIAS D， ZHANG J， MAMOULIS N， et al. Query processing in spatial network databases［C］// Proceedings of the 29th International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers Inc.， 2003： 802-813.
3	WANG H， ZIMMERMANN R. Location-based query processing on moving objects in road networks［C］// Proceedings of the 2007 International Conference on Very Large Data Bases. New York： ACM， 2007： 321-332.
4	MOURATIDIS K， YIU M L， PAPADIAS D， et al. Continuous nearest neighbor monitoring in road networks［C］// Proceedings of the 32nd International Conference on Very Large Data Bases. New York： ACM， 2006：43-54.
5	HUANG X， JENSEN C S， ŠALTENIS S. The Islands approach to nearest neighbor querying in spatial networks［C］// Proceedings of the 2005 International Symposium on Spatial and Temporal Databases， LNCS 3633. Berlin： Springer， 2005： 73-90.
6	HUANG X， JENSEN C S， LU H， et al. S-GRID： a versatile approach to efficient query processing in spatial networks［C］// Proceedings of the 2007 International Symposium on Spatial and Temporal Databases， LNCS 4605. Berlin： Springer， 2007： 93-111.
7	OUYANG D， WEN D， QIN L， et al. Progressive top-k nearest neighbors search in large road networks［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 1781-1795.
8	LUO S， KAO B， LI G， et al. TOAIN： a throughput optimizing adaptive index for answering dynamic kNN queries on road networks［J］. Proceedings of the Very Large Data Bases Endowment， 2018， 11（5）： 594-606.
9	SHEN B， ZHAO Y， LI G， et al. V-Tree： efficient kNN search on moving objects with road-network constraints［C］// Proceedings of the IEEE 33rd International Conference on Data Engineering. Piscataway： IEEE， 2017： 609-620.
10	LEE K C K， LEE W C， ZHENG B， et al. ROAD： a new spatial object search framework for road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（3）： 547-560.
11	ZHONG R， LI G， TAN K L， et al. G-Tree： an efficient index for kNN search on road networks［C］// Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York： ACM， 2013： 39-48.
12	LI Z， CHEN L， WANG Y. G^*-Tree： an efficient spatial index on road networks［C］// Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 268-279.
13	SANKARANARAYANAN J， ALBORZI H， SAMET H. Efficient query processing on spatial networks［C］// Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems. New York： ACM， 2005： 200-209.
14	LUO S， KAO B， WU X， et al. MPR — a partitioning-replication framework for multi-processing kNN search on road networks［C］// Proceedings of the IEEE 35tth International Conference on Data Engineering. Piscataway： IEEE， 2019： 1310-1321.
15	CAO B， HOU C， LI S， et al. SIMkNN： a scalable method for in‑memory kNN search over moving objects in road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（10）： 1957-1970.
16	HE D， WANG S， ZHOU X， et al. An efficient framework for correctness-aware kNN queries on road networks［C］// Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 1298-1309.
17	DEMIRYUREK U， BANAEI-KASHANI F， SHAHABI C. Efficient continuous nearest neighbor query in spatial networks using Euclidean restriction［C］// Proceedings of the 2009 International Symposium on Spatial and Temporal Databases. Cham： Springer， 2009： 25-43.
18	LI C， GU Y， QI J， et al. A GPU accelerated update efficient index for KNN queries in road networks［C］// Proceedings of the IEEE 34th International Conference on Data Engineering. Piscataway： IEEE， 2018： 881-892.
19	KARYPIS G， KUMAR V. A fast and high quality multilevel scheme for partitioning irregular graphs［J］. SIAM Journal on Scientific Computing， 1998， 20（1）： 359-392.
20	HEWITT C， BISHOP P， STEIGER R. A universal modular actor formalism for artificial intelligence［C］// Proceedings of the 3rd International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers Inc.， 1973： 235-245.
21	YIU M L， MAMOULIS N， PAPADIAS D. Aggregate nearest neighbor queries in road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2005， 17（6）： 820-833.

[1]	WEN La RUI Jianwu HE Tingting GUO Liang. Accelerating hierarchical distributed latent Dirichlet allocation algorithm by parallel GPU [J]. Journal of Computer Applications, 2013, 33(12): 3313-3316.
[2]	Li-Juan CAO . Research of Web-OLAP system based on distributed data cache technology [J]. Journal of Computer Applications, 2008, 28(2): 515-518.

Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network

面向动态路网的移动对象分布式k近邻查询算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 21

Related Articles 2

Recommended Articles

Metrics