Dynamic aggregate nearest neighbor query algorithm in weighted road network space

doi:10.11772/j.issn.1001-9081.2022091371

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (7): 2026-2033.DOI: 10.11772/j.issn.1001-9081.2022091371

• The 39th CCF National Database Conference (NDBC 2022) • Previous Articles

Dynamic aggregate nearest neighbor query algorithm in weighted road network space

Fangshu CHEN(), Wei ZHANG, Xiaoming HU, Yufei ZHANG, Xiankai MENG, Linxiang SHI

School of Computer and Information Engineering，Shanghai Polytechnic University，Shanghai 201209，China

Received:2022-08-25 Revised:2022-09-20 Accepted:2022-10-12 Online:2023-07-20 Published:2023-07-10
Contact: Fangshu CHEN
About author:CHEN Fangshu， born in 1989， Ph. D.， lecturer. Her research interests include data mining， spatio-temporal data analysis.
ZHANG Wei， born in 1999， M. S. candidate. His research interests include spatial index， graph neural network.
HU Xiaoming， born in 1978， Ph. D.， professor. Her research interests include cryptography， information security， network security.
ZHANG Yufei， born in 1999， M. S. candidate. His research interests include graph neural network， complex network.
MENG Xiankai， born in 1985， Ph. D.， lecturer. His research interests include artificial intelligence， knowledge graph.
SHI Linxiang， born in 1972， M. S.， associate professor. His research interests include computer-aided design， smart detection.
Supported by:
National Natural Science Foundation of China(62002216);Shanghai Sailing Program(20YF1414400);Youth Project of Shanghai Polytechnic University(EGD22QD03);Collaborative Innovation Platform Construction Project of Electronic Information Master of Shanghai Polytechnic University(A10GY21F015)

加权路网空间中动态聚集最近邻居查询算法

陈方疏(), 张为, 胡小明, 张宇飞, 孟宪凯, 石林祥

上海第二工业大学计算机与信息工程学院，上海 201209

通讯作者: 陈方疏
作者简介:陈方疏（1989—），女，湖北襄阳人，讲师，博士，CCF会员，主要研究方向：数据挖掘、时空数据分析；
张为（1999—），男，湖北黄冈人，硕士研究生，CCF学生会员，主要研究方向：空间索引、图神经网络；
胡小明（1978—），女，浙江慈溪人，教授，博士，CCF会员，主要研究方向：密码学、信息安全、网络安全；
张宇飞（1999—），男，湖南长沙人，硕士研究生，CCF学生会员，主要研究方向：图神经网络、复杂网络；
孟宪凯（1985—），男，黑龙江讷河人，讲师，博士，CCF会员，主要研究方向：人工智能、知识图谱；
石林祥（1972—），男，湖北黄冈人，副教授，硕士，CCF会员，主要研究方向：计算机辅助设计、智能检测。
基金资助:
国家自然科学基金资助项目(62002216);上海市青年科技英才扬帆计划项目(20YF1414400);上海第二工业大学青年基金资助项目(EGD22QD03);上海第二工业大学电子信息类专业硕士协同创新平台建设项目(A10GY21F015)

Abstract

Abstract:

As a classical problem in spatial databases， Aggregate Nearest Neighbor （ANN） query is of great importance in the optimization of network link structures， the location selection of logistics distribution points and the car-sharing services， and can effectively contribute to the development of fields such as logistics， mobile Internet industry and operations research. The existing research has some shortcomings： lack of efficient index structure for large-scale dynamic road network data， low query efficiency of the algorithms when the data point locations move in real time and network weights update dynamically. To address these problems， an ANN query algorithm in dynamic scenarios was proposed. Firstly， with adopting G-tree as the road network index， a pruning algorithm combining spatial index structures such as quadtrees and k-d trees with the Incremental Euclidean Restriction （IER） algorithm was proposed to solve ANN queries in statistic space. Then， aiming at the issue of frequent updates of data point locations in dynamic scenarios， the time window and safe zone update strategy were added to reduce the iteration times of the algorithm， experimental results showed that the efficiency could be improved by 8% to 85%. Finally， for ANN query problems with road network weight changed， based on historical query results， two correction based continuous query algorithms were proposed to obtain the current query results according to the increment of weight changes. In certain scenarios， these algorithms can reduce errors by approximately 50%. The theoretical research and experimental results show that the proposed algorithms can solve the ANN query problems in dynamic scenarios efficiently and more accurately.

Key words: Aggregate Nearest Neighbor (ANN) query, road network, weighted space, dynamic query, spatial index

摘要：

聚集最近邻居（ANN）查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义，能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足：缺少针对大规模动态路网数据的高效索引结构，在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足，提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引，提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制（IER）算法结合起来的剪枝方法，以完成静态空间下的ANN查询；随后针对动态场景下数据点位置频繁更新的问题，加入时间窗口及安全区域更新策略，以减少算法的重复计算次数，实验结果表明效率能提高8%~85%；最后针对路网权重变化的ANN查询问题，提出两个基于校正的连续查询方法，在历史查询结果的基础上，根据权重变化的增量来得到当前的查询结果，在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明，所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。

关键词: 聚集最近邻居查询, 路网, 加权空间, 动态查询, 空间索引

CLC Number:

TP311

Fangshu CHEN, Wei ZHANG, Xiaoming HU, Yufei ZHANG, Xiankai MENG, Linxiang SHI. Dynamic aggregate nearest neighbor query algorithm in weighted road network space[J]. Journal of Computer Applications, 2023, 43(7): 2026-2033.

陈方疏, 张为, 胡小明, 张宇飞, 孟宪凯, 石林祥. 加权路网空间中动态聚集最近邻居查询算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2026-2033.

Figures/Tables 14

References 21

1	PAPADIAS D， SHEN Q M， TAO Y F， et al. Group nearest neighbor queries ［C］// Proceedings of the 20th International Conference on Data Engineering. Piscataway： IEEE， 2004： 301-312.
2	CHEN F S， QI J Z， LIN H Z， et al. GOAL： a clustering-based method for the group optimal location problem［J］. Knowledge and Information Systems， 2019， 61 （2）： 873-903. 10.1007/s10115-018-1307-6
3	GAO Y J， QI S Y， CHEN L， et al. On efficient k-optimal-location-selection query processing in metric spaces［J］. Information Sciences， 2015， 298： 98-117. 10.1016/j.ins.2014.11.038
4	XU C F， GU Y， ZIMMERMANN R， et al. Group location selection queries over uncertain objects［J］. IEEE Transactions on Knowledge and Data Engineering， 2013， 25 （12）： 2796-2808. 10.1109/tkde.2012.160
5	PAPADIAS D， TAO Y F， MOURATIDIS K， et al. Aggregate nearest neighbor queries in spatial databases［J］. ACM Transactions on Database Systems， 2005， 30 （2）： 529-576. 10.1145/1071610.1071616
6	CHEN K J， SUN W W， TU C C， et al. Aggregate keyword routing in spatial database ［C］// Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2012： 430-433. 10.1145/2424321.2424382
7	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. 10.1109/tkde.2005.87
8	SUN W W， CHEN C N， ZHU L， et al. On efficient aggregate nearest neighbor query processing in road networks［J］. Journal of Computer Science and Technology， 2015， 30 （4）： 781-798. 10.1007/s11390-015-1560-z
9	朱良，孙未未，荆一楠，等. 基于Voronoi图的路网k聚集最近邻居节点查询方法［J］. 计算机研究与发展， 2011， 48 （S3）： 155-162.
	ZHU L， SUN W W， JING Y N， et al. Voronoi-based k-aggregate nearest neighbor query processing in road networks［J］. Journal of Computer Research and Development， 2011， 48 （S3）： 155-162.
10	LEE K C K， LEE W C， ZHENG B H， 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. 10.1109/tkde.2010.243
11	ZHONG R C， LI G L， TAN K L， et al. G-tree： an efficient and scalable index for spatial search on road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2015， 27 （8）： 2175-2189. 10.1109/tkde.2015.2399306
12	CHEN F S， ZHANG P F， LIN H Z， et al. Continuous path-based range keyword queries on road networks ［C］// Proceedings of the 2019 IEEE International Conference on Big Knowledge. Piscataway： IEEE， 2019： 42-49. 10.1109/icbk.2019.00014
13	CHUNG M， LOH W K. α-Probabilistic flexible aggregate nearest neighbor search in road networks using landmark multidimensional scaling［J］. The Journal of Supercomputing， 2021， 77 （2）： 2138-2153. 10.1007/s11227-020-03521-6
14	CHEN Z P， YAO B， WANG Z J， et al. Flexible aggregate nearest neighbor queries and its keyword-aware variant on road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33 （12）： 3701-3715. 10.1109/tkde.2020.2975998
15	ABEYWICKRAMA T， CHEEMA M A， STORANDT S. Hierarchical graph traversal for aggregate k nearest neighbors search in road networks ［C］// Proceedings of the 30th International Conference on Automated Planning and Scheduling. Palo Alto， CA： AAAI Press， 2020： 2-10. 10.1609/icaps.v30i1.6639
16	MOURATIDIS K， PAPADIAS D， HADJIELEFTHERIOU M. Conceptual partitioning： an efficient method for continuous nearest neighbor monitoring ［C］// Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2005： 634-645. 10.1145/1066157.1066230
17	ELMONGUI H G， MOKBEL M F， AREF W G. Continuous aggregate nearest neighbor queries［J］. GeoInformatica， 2013， 17 （1）： 63-95. 10.1007/s10707-011-0149-0
18	ZHANG P F， LIN H Z， GAO Y J， et al. Aggregate keyword nearest neighbor queries on road networks［J］. GeoInformatica， 2018， 22 （2）： 237-268. 10.1007/s10707-017-0315-0
19	LI J， THOMSEN J R， YIU M L， et al. Efficient notification of meeting points for moving groups via independent safe regions［J］. IEEE Transactions on Knowledge and Data Engineering， 2015， 27 （7）： 1767-1781. 10.1109/tkde.2014.2334304
20	QIN L， YU J X， DING B L， et al. Monitoring aggregate k-NN objects in road networks ［C］// Proceedings of the 2008 International Conference on Scientific and Statistical Database Management， LNCS 5069. Berlin： Springer， 2008： 168-186.
21	WU Y K， ZHUANG D Y， LEI M Y， et al. Spatial aggregation and temporal convolution networks for real-time kriging［EB/OL］. （2021-09-24）［2022-05-14］. .

变量符号	含义
G（V，E，W）	路网图G，其中点集合V、边集合E和路网权重集合W
P， Q	数据点集合P、查询点集合Q
［p_i_，q_j ］	p_i 到q_j 的最短路网距离
dist（p_i_，q_j ）	p_i 到q_j 的最短欧氏距离
counts（SET）	集合SET中的元素数量
path（p_i_，q_j ）	p_i 到q_j 的最短路径
len（p_i_，q_j_，G'）	path（p_i_，q_j ）中的落在子图G'中的边的数量
pass（e）	经过边e的最短路径频数
var（e，t₀，t₁）	t₀至t₁时刻边e的路网权重增量
I（e）	集合E中边e对应的重要性权重

变量符号	含义
G（V，E，W）	路网图G，其中点集合V、边集合E和路网权重集合W
P， Q	数据点集合P、查询点集合Q
［p_i_，q_j ］	p_i 到q_j 的最短路网距离
dist（p_i_，q_j ）	p_i 到q_j 的最短欧氏距离
counts（SET）	集合SET中的元素数量
path（p_i_，q_j ）	p_i 到q_j 的最短路径
len（p_i_，q_j_，G'）	path（p_i_，q_j ）中的落在子图G'中的边的数量
pass（e）	经过边e的最短路径频数
var（e，t₀，t₁）	t₀至t₁时刻边e的路网权重增量
I（e）	集合E中边e对应的重要性权重

数据集	边数	点数
California	21 693	21 048
Oldenburg	7 034	6 014
North America	179 178	175 812

数据集	边数	点数
California	21 693	21 048
Oldenburg	7 034	6 014
North America	179 178	175 812

数据集	建立时间/s	内存消耗/MB
California	56.8	80.5
Oldenburg	49.8	54.8
North America	210.8	310.8

Dynamic aggregate nearest neighbor query algorithm in weighted road network space

加权路网空间中动态聚集最近邻居查询算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 21

Related Articles 15

Recommended Articles

Metrics

[1]	FU Yu, WANG Hong. Virtual trajectory filling algorithm for location privacy protection [J]. Journal of Computer Applications, 2019, 39(8): 2318-2325.
[2]	HUO Zheng, ZHANG Kun, HE Ping, WU Yanbin. Crowdsourcing location data collection for local differential privacy [J]. Journal of Computer Applications, 2019, 39(3): 763-768.
[3]	FENG Jun, LI Dingsheng, LU Jiamin, ZHANG Lixia. Spatio-temporal index method for moving objects in road network based on HBase [J]. Journal of Computer Applications, 2018, 38(6): 1575-1583.
[4]	LI Jiajia, LIU Xiaojing, LIU Xiangyu, XIA Xiufeng, ZHU Rui. Improved time dependent fast travel time algorithm by dynamically selecting heuristic values [J]. Journal of Computer Applications, 2018, 38(1): 120-125.
[5]	HUO Zheng, CUI Honglei, HE Ping. k-CS algorithm: trajectory data privacy-preserving based on semantic location protection [J]. Journal of Computer Applications, 2018, 38(1): 182-187.
[6]	HUO Zheng, WANG Weihong, CAO Yuhui. PTDC:privacy-aware trajectory data collection technology under road network constraint [J]. Journal of Computer Applications, 2017, 37(9): 2567-2571.
[7]	XU Wei, LI Wengen, ZHANG Yichao, GUAN Jihong. Probabilistic bichromatic reverse-kNN query on road network [J]. Journal of Computer Applications, 2017, 37(2): 341-346.
[8]	ZHOU Sha, WANG Run, ZHEN Wenjie. Pedestrian route choice model considering subjective judgment delay [J]. Journal of Computer Applications, 2016, 36(4): 1146-1150.
[9]	MA Xiaoqin, PENG Xiufen, YANG Li. Spatial range query in wireless broadcast environment [J]. Journal of Computer Applications, 2015, 35(6): 1762-1765.
[10]	ZHU Haiquan, LI Wengen, ZHANG Yichao, GUAN Jihong. Group trip planning queries on road networks [J]. Journal of Computer Applications, 2015, 35(11): 3146-3150.
[11]	LIU Degao LI Xiaoyu. Continuous k nearest neighbor query algorithm based on road network [J]. Journal of Computer Applications, 2013, 33(07): 1964-1968.
[12]	LUO Ya’nan FU Yongqing. Path planning algorithm based on hierarchical road network [J]. Journal of Computer Applications, 2013, 33(06): 1763-1766.
[13]	WU Jia-gao SHAO Shi-wei HUA Zheng ZOU Zhi-qiang HU Bin. Study and implementation of optimization mechanism for hybrid P2P spatial indexing network [J]. Journal of Computer Applications, 2011, 31(09): 2301-2304.
[14]	. Design of spatial index structure based on RBD-tree [J]. Journal of Computer Applications, 2010, 30(4): 1103-1106.
[15]	WU QinYang. Improved R*-tree spatial index [J]. Journal of Computer Applications, 2010, 30(2): 419-422.