基于稀疏多头自注意力的轨迹kNN查询方法

doi:10.13229/j.cnki.jdxbgxb.20220865

Abstract

Abstract:

The application of location information generates a large volume of spatio-temporal data with multidimensional attributes such as latitude， longitude and time. The index-based trajectory query method cannot obtain the spatio-temporal semantic features of the trajectory， and its trajectory representation ignores the spatio-temporal correlation of the trajectory and is inefficient for large-scale trajectory data query. To solve the above problems， a kind of trajectory encoder based on sparse multi-head attention is proposed， through the trajectory of the encoder can extract high-level semantic features， trajectories are represented as encoding vectors. On the basis of trajectory coding vector， a trajectory query method based on locally sensitive hash function is developed， which can query large-scale trajectory data quickly. The experiment results show that the proposed trajectory query method can effectively deal with kNNT query problems and it is superior to the current trajectory query method in terms of accuracy and efficiency.

Key words: computer application, spatio-temporal data, trajectory data mining, deep learning, trajectory representation learning, multi-head self-attention

CLC Number:

TP311

Li-ping ZHANG,Bin-yu LIU,Song LI,Zhong-xiao HAO. Trajectory k nearest neighbor query method based on sparse multi-head attention[J].Journal of Jilin University(Engineering and Technology Edition), 2024, 54(6): 1756-1766.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Table 1

Fig.4

Fig.5

Fig.6

Table 2

Fig.7

Table 3

Fig.8

Fig.9

References 28

1	Ugwoke P O, Bakpo F S, Udanor C N, et al. A framework for monitoring movements of pandemic disease patients based on GPS trajectory datasets[J]. Wireless Networks, 2022, 28(1): 1-28.
2	Belhassena A, Wang H. Trajectory big data processing based on frequent activity[J]. Tsinghua Science and Technology, 2019, 24(3): 317-332.
3	Sojahrood Z B, Taleai M. Behavior-based POI recommendation for small groups in location-based social networks[J]. Transactions in GIS, 2021,26(1):259-277.
4	李松, 胡晏铭, 郝晓红, 等. 基于维度分组降维的高维数据近似k近邻查询[J]. 计算机研究与发展, 2021, 58(3): 609-623.
	Li Song, Hu Yan-ming, Hao Xiao-hong, et al. Approximate k-nearest neighbor query of high dimensional data based on dimension grouping and reducing[J]. Journal of Computer Research and Development, 2021, 58(3): 609-623.
5	Qi S, Bouros P, Sacharidis D, et al. Efficient point-based trajectory Search[C]∥Advances in Spatial and Temporal Databases, Hong Kong, China, 2015: 179-196.
6	Tang L A, Zheng Y, Xie X, et al. Retrieving k-nearest neighboring trajectories by a set of point locations[C]∥Symposium on Large Spatial Databases, Minneapolis,USA, 2011: 223-241.
7	姜乔文, 刘瑜, 谭大宁, 等. 时空轨迹多维特征融合的行为规律挖掘算法[J]. 航空学报, 2022, 43(9): No.32394.
	Jiang Qiao-wen, Liu Yu, Tan Da-ning, et al. Regular behaviors mining algorithm based on spatiotemporal trajectory multidimensional features fusion[J]. Acta Aeronautica ET Astronautica Sinica,2022, 43(9): No.32394.
8	Roh Gook-pil, Roh Jong-won, Hwang Seung-won, et al. Supporting pattern-matching queries over trajectories on road networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(11): 1753-1758.
9	Eiter T, Mannila H. Computing discrete Fréchet distance[EB/OL]. [2022-07-01].
10	Yi Byoung-Kee, Jagadish H V, Christos Faloutsos. Efficient retrieval of similar time sequences under time warping[C]∥Proceedings of the Fourteenth International Conference on Data Engineering, Orlando,USA, 1998:201-208.
11	Vlachos Michail, Kollios George, Gunopulos Dimitrios. Discovering similar multidimensional trajectories[C]∥ICDE 2002, San Jose,USA, 2002: 673-684.
12	Chen Lei. Tamer Özsu M, Oria V. Robust and fast similarity search for moving object trajectories[C]∥SIGMOD 2005, Baltimore,USA, 2005: 491-502.
13	许建秋, 梁珺秀, 秦小麟. 基于时空标签轨迹的k近邻模式匹配查询[J]. 通信学报, 2018, 39(4): 112-122.
	Xu Jian-qiu, Liang Jun-xiu, Qin Xiao-lin. k nearest neighbor pattern match queries over spatio-temporal label trajectories[J]. Journal on Communications, 2018, 39(4): 112-122.
14	Xu J, Hartmut G R, Gao Y. Continuous k nearest neighbor queries over large multi-attribute trajectories: a systematic approach[J]. GeoInformatica, 2018, 22(4): 1-44.
15	余列冰, 向隆刚, 孙尚宇, 等. 面向分布式列式存储的轨迹大数据k近邻查询[J]. 武汉大学学报: 信息科学版, 2020, 46(5): 736-745.
	Yu Lie-bing, Xiang Long-gang, Sun Shang-yu, et al. kNN query processing for trajectory big data based on distributed column-oriented storage[J]. Geomatics and Information Science of Wuhan University, 2020, 46(5): 736-745.
16	Yu Z. Trajectory data mining: an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 1-41.
17	Guttman A. R-tree: a dynamic index structure for spatial searching[C]∥Proc ACMSIGMOD,San Francisco, USA, 1984: 90-100.
18	Kamel I, Faloutsos C.Hilbert R-tree: an improved R-tree using fractals[C]∥Proceedings of the 20th International Conference on Very Large Data Bases, Burlington, USA, 1994: 500-509.
19	Papadias D, Zhang D, Kollios G. Proceedings of the 10th international conference on Advances in spatial and temporal databases[C]∥International Conference on Advances in Spatial & Temporal Databases. Boston: Springer-Verlag, 2007.
20	Bowman S R, Vilnis L, Vinyals O, et al. Generating sentences from a continuous space[C]∥Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning,Berlin, Germany, 2016: 10-21.
21	Wang Sheng, Bao Zhi-feng, Shane C, et al. A survey on trajectory data management, analytics, and learning[J]. ACM Computing Surveys, 2021, 54(2): No.39.
22	Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space[EB/OL]. [2022-07-02].
23	Rong X. Word2vec parameter learning explained[J/OL]. [2022-07-02].
24	He K, Zhang X, Ren S, et al. Deep residual learning for image recognition[C]∥Conference on Computer Vision and Pattern Recognition, Las Vegas,USA, 2016: 770-778.
25	章登义, 李想. 一种基于密度网格索引的k-最近邻查询算法[J]. 电子学报, 2017, 45(2): 376-383.
	Zhang Deng-yi, Li Xiang. A k-nearest neighbor query algorithm for density grid-based index[J]. Acta Electronica Sinica, 2017, 45(2): 376-383.
26	向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报: 信息科学版, 2017, 42(1): 21-27.
	Xiang Long-gang, Wang De-hao, Gong Jian-ya. Organization and efficient range query of large trajectory data based on geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 21-27.
27	冯小康, 彭延国, 崔江涛, 等. 基于最优排序的局部敏感哈希索引[J].计算机学报, 2020, 43(5):930-947.
	Feng Xiao-kang, Peng Yan-guo, Cui Jiang-tao, et al. Locality sensitive hashing index based on optimal linear order[J]. Chinese Journal of Computers, 2020, 43(5): 930-947.
28	Ramadhan Hani, Kwon Joonho. Enhancing learned index for a higher recall trajectory k-Nearest neighbor search[C]∥2021 IEEE International Conference on Big Data, Orlando, USA, 2021: 6006-6007.

Related Articles 15

[1]	Yu-kai LU,Shuai-ke YUAN,Shu-sheng XIONG,Shao-peng ZHU,Ning ZHANG. High precision detection system for automotive paint defects [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(5): 1205-1213.
[2]	Li-ming LIANG,Long-song ZHOU,Jiang YIN,Xiao-qi SHENG. Fusion multi-scale Transformer skin lesion segmentation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(4): 1086-1098.
[3]	Yun-zuo ZHANG,Wei GUO,Wen-bo LI. Omnidirectional accurate detection algorithm for dense small objects in remote sensing images [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(4): 1105-1113.
[4]	Guo-jun YANG,Ya-hui QI,Xiu-ming SHI. Review of bridge crack detection based on digital image technology [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(2): 313-332.
[5]	Xiong-fei LI,Zi-xuan SONG,Rui ZHU,Xiao-li ZHANG. Remote sensing change detection model based on multi⁃scale fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(2): 516-523.
[6]	Yue-lin CHEN,Zhu-cheng GAO,Xiao-dong CAI. Long text semantic matching model based on BERT and dense composite network [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(1): 232-239.
[7]	Guang HUO,Da-wei LIN,Yuan-ning LIU,Xiao-dong ZHU,Meng YUAN,Di GAI. Lightweight iris segmentation model based on multiscale feature and attention mechanism [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2591-2600.
[8]	Ying HE,Zhuo-ran WANG,Xu ZHOU,Yan-heng LIU. Point of interest recommendation algorithm integrating social geographical information based on weighted matrix factorization [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2632-2639.
[9]	Yun-zuo ZHANG,Xu DONG,Zhao-quan CAI. Multi view gait cycle detection by fitting geometric features of lower limbs [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2611-2619.
[10]	Ming-yao XIAO,Xiong-fei LI,Rui ZHU. Medical image fusion based on pixel correlation analysis in NSST domain [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2640-2648.
[11]	Ya-hui ZHAO,Fei-yu LI,Rong-yi CUI,Guo-zhe JIN,Zhen-guo ZHANG,De LI,Xiao-feng JIN. Korean⁃Chinese translation quality estimation based on cross⁃lingual pretraining model [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(8): 2371-2379.
[12]	Xiao-jun JIN,Yan-xia SUN,Jia-lin YU,Yong CHEN. Weed recognition in vegetable at seedling stage based on deep learning and image processing [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(8): 2421-2429.
[13]	Xiang-jiu CHE,Huan XU,Ming-yang PAN,Quan-le LIU. Two-stage learning algorithm for biomedical named entity recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(8): 2380-2387.
[14]	Qing-tian GENG,Zhi LIU,Qing-liang LI,Fan-hua YU,Xiao-ning LI. Prediction of soil moisture based on a deep learning model [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(8): 2430-2436.
[15]	Lian-ming WANG,Xin WU. Method for 3D motion parameter measurement based on pose estimation [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(7): 2099-2108.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

移动方式	移动总距离/m	移动总用时/h
徒步	10 123	5 460
自行车	6 495	2 410
公交车	20 281	1 507
汽车	32 866	2 384
火车	36 253	745
飞机	24 789	40
其他	9 493	404

方法	k值
方法	10	50	100	500	1 000	5 000
DGrid	46.65	46.91	47.34	50.78	52.23	52.31
Geohash	37.99	38.04	36.43	36.94	36.71	38.25
O2LSH	17.21	17.36	17.80	17.93	19.71	19.82
LR-Tree	43.99	41.83	42.96	43.22	44.52	45.63
ER-Tree	39.62	38.54	40.21	41.30	45.11	45.23
SMHkNN	16.94	16.86	16.87	16.97	17.44	17.03

方法	数据规模
方法	1 000	5 000	10 000	100 000
DGrid	5.63	24.65	46.71	276.85
Geohash	5.24	19.47	36.43	249.66
O2LSH	4.67	7.43	23.32	26.35
LR-Tree	4.58	15.46	37.83	259.11
ER-Tree	4.52	14.62	36.96	253.75
SMHkNN	4.24	8.43	16.87	24.68

Trajectory k nearest neighbor query method based on sparse multi-head attention

RICH HTML

PDF (PC)