基于时空标签轨迹的k近邻模式匹配查询

doi:10.11959/j.issn.1000-436x.2018063

摘要/Abstract

摘要：

时空标签轨迹在传统的时空轨迹数据基础之上融入了具有语义含义的标签信息，丰富了移动对象数据。针对该数据提出k近邻模式匹配查询，即在给定时间区间内匹配相应的模式且距离查询轨迹最近的k条轨迹。设计并实现标签R树（LR-Tree），即增加标签表并在R树每项中添加标签位图，及基于LR-Tree的k近邻模式匹配查询算法。通过真实数据和合成数据将LR-Tree与3DR-Tree、SETI及TB-Tree进行对比，实验表明LR-Tree具有更好的剪枝能力，从而验证了所提算法及索引的有效性。

关键词: 时空标签轨迹, k近邻算法, 模式匹配, 索引

Abstract:

Spatio-temporal label trajectories extended traditional spatio-temporal trajectories with semantic labels.k nearest neighbor pattern match was proposed to return the k nearest trajectories that fulfilled the temporal pattern condition.The Label R-Tree (LR-Tree for short) was proposed,which appending a label table and adding label bitmap in each entry,and k nearest neighbor pattern match query algorithm based on LR-Tree was designed.Using both real and synthetic datasets,the LR-Tree was extensively evaluated in comparison with 3DR-Tree,SETI and TB-Tree.The experimental results demonstrate that LR-Tree showing better pruning ability,and verify the effectiveness of proposed algorithm and index.

Key words: spatio-temporal label trajectories, k nearest neighbor algorithm, pattern match, index

中图分类号:

TP311

许建秋,梁珺秀,秦小麟. 基于时空标签轨迹的k近邻模式匹配查询[J]. 通信学报, 2018, 39(4): 112-122.

Jianqiu XU,Junxiu LIANG,Xiaolin QIN. k nearest neighbor pattern match queries over spatio-temporal label trajectories[J]. Journal on Communications, 2018, 39(4): 112-122.

图/表 12

图1

图2

图3

图4

表1

图5

图6

表2

图7

图

表3

图9

参考文献 24

[1]	XUAN K , ZHAO G , TANIAR D ,et al. Continuous range search query processing in mobile navigation[C]// The IEEE International Conference on Parallel and Distributed Systems. 2008: 361-368.
[2]	GAO Y J , LI C , CHEN G C ,et al. Efficient k-nearest- neighbor search algorithms for historical moving object trajectories[J]. Journal of Computer Science and Technology, 2007,22(2): 232-244.
[3]	BENETIS R , JENSEN C S , KAR?IAUSKAS G ,et al. Nearest neighbor and reverse nearest neighbor queries for moving objects[C]// The IEEE International Symposium on Database Engineering ＆ Applications. 2002: 44-53.
[4]	TIAKAS E , PAPADOPOULOS A N , NANOPOULOS A ,et al. Searching for similar trajectories in spatial networks[J]. Journal of Systems ＆ Software, 2009,82(5): 772-788.
[5]	ALVARES L O , BOGORNY V , KUIJPERS B ,et al. A model for enriching trajectories with semantic geographical information[C]// The ACM International Symposium on Advances in Geographic Information Systems. 2007:22.
[6]	ZHENG K , SHANG S , YUAN N J ,et al. Towards efficient search for activity trajectories[C]// The IEEE International Conference on Data Engineering. 2013: 230-241.
[7]	GüTING R H , VALDéS F , DAMIANI M L . Symbolic trajectories[J]. ACM Transactions on Spatial Algorithms ＆ Systems, 2015,1(2): 1-51.
[8]	WU D , YIU M L , JENSEN C S ,et al. Efficient continuously moving top-k spatial keyword query processing[C]// The IEEE International Conference on Data Engineering. 2011: 541-552.
[9]	ZHENG B , YUAN N J , ZHENG K ,et al. Approximate keyword search in semantic trajectory database[C]// The IEEE International Conference on Data Engineering. 2015: 975-986.
[10]	HAN Y , WANG L , ZHANG Y ,et al. Spatial keyword range search on trajectories[M]// Database Systems for Advanced Applications.Springer International Publishing. 2015: 223-240.
[11]	FELIPE I D , HRISTIDIS V , RISHE N . Keyword search on spatial databases[C]// The IEEE International Conference on Data Engineering. 2008: 656-665.
[12]	DAMIANI M L , ISSA H , GüTING R H ,et al. Hybrid queries over symbolic and spatial trajectories:a usage scenario[C]// The IEEE International Conference on Mobile Data Management. 2014: 341-344.
[13]	SPACCAPIETRA S , PARENT C , DAMIANI M L ,et al. A conceptual view on trajectories[J]. Data ＆ Knowledge Engineering, 2008,65(1): 126-146.
[14]	ZHANG C , HAN J , SHOU L ,et al. Splitter:mining fine-grained sequential patterns in semantic trajectories[J]. Proceedings of the Very Large Data Bases Endowment, 2014,7(9): 769-780.
[15]	PARENT C , SPACCAPIETRA S , RENSO C ,et al. Semantic trajectories modeling and analysis[J]. ACM Computing Surveys, 2013,45(4): 1-32.
[16]	PALMA A T , BOGORNY V , KUIJPERS B ,et al. A clustering-based approach for discovering interesting places in trajectories[C]// The ACM Symposium on Applied Computing. 2008: 863-868.
[17]	VALDéS F , DAMIANI M L , GüTING R H . Symbolic trajectories in SECONDO:Pattern Matching and Rewriting[J]. Lecture Notes in Computer Science, 2013,7826(2): 450-453.
[18]	GUTTMAN A , . R-trees:a dynamic index structure for spatial searching[C]// The ACM SIGMOD International Conference on Management of Data. 1984: 47-57.
[19]	PRASAD V , ADAM C , EVERSPAUGH C ,et al. Indexing large trajectory data sets with SETI[C]// Conference on Innovative Data Systems Research. 2003.
[20]	PFOSER D , JENSEN C S , THEODORIDIS Y . Novel approaches in query processing for moving object trajectories[C]// International Conference on Very Large Data Bases. 2000: 395-406.
[21]	CONG G , JENSEN C S , WU D . Efficient retrieval of the top-k most relevant spatial web objects[J]. Proceedings of the Very Large Data Bases Endowment, 2009,2(1): 337-348.
[22]	BERCHTOLD S , B?HM C , KRIEGEL H P . Improving the query performance of high-dimensional index structures by bulk load operations[J]. Lecture Notes in Computer Science, 1998,1377(2): 216-230.
[23]	GUTING R H , ALMEIDA V , ANSORGE D ,et al. SECONDO:an extensible DBMS platform for research prototyping and teaching[C]// International Conference on Data Engineering. 2005: 1115-1116.
[24]	ZHENG Y , XIE X , MA W Y . GeoLife:a collaborative social networking service among user,location and trajectory[J]. Bulletin of the Technical Committee on Data Engineering, 2010,33(2): 32-39.

名称	轨迹数量	轨迹单元数
GeoLife	4 300	4 124 326
Train	562	51 544
Train(10)	56 200	5 154 400
Train(15)	126 450	11 597 400
Train(20)	224 800	20 617 600
Train(30)	505 800	46 389 600
Train(50)	1 405 000	128 860 000

参数名	参数值
标签	飞机,自行车,火车,步行,出租车,汽车,地铁,公交
标签数量	1,3,5,7,9
时间区间长度	1 h,2 h,3 h,1d,1m
返回结果数	1,100,300,600,1 000
数据集(轨迹)/条	56 000,126 000,224 000,505 000,1 405 000

标签名称	标签数量	标签百分比
飞机	18	0.19%
出租车	813	9.10%
火车	147	1.65%
步行	574	6.43%
自行车	477	5.34%
汽车	1594	17.86%
地铁	1564	17.52%
公交	3740	41.90%