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

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

Abstract

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

CLC Number:

TP311

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.

Figures/Tables 12

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

名称	轨迹数量	轨迹单元数
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%

k nearest neighbor pattern match queries over spatio-temporal label trajectories

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Yi GUO, Yiqing WANG, Yuanyuan FAN, Gang LIU. OFDM transmission scheme with subcarrier supply index modulation [J]. Journal on Communications, 2023, 44(2): 104-111.
[2]	Qihan ZHANG, Xiaoxue GONG, Rui LI, Xin LI, Shanguo HUANG, Lei GUO. All-optical pattern matching system of 42 Gbit/s 4-bit BPSK signals and its demonstration for optoelectronic firewall [J]. Journal on Communications, 2022, 43(7): 31-40.
[3]	Hua YANG, Yu WANG, Siyuan XU, Guoping JIANG. Time hopping short reference carrier index differential chaos shift keying communication scheme [J]. Journal on Communications, 2022, 43(3): 113-123.
[4]	Xiaodong FU, Xinxin QI, Li LIU, Wei PENG, Jiaman DING, Fei DAI. Detecting and preventing collusion attack in DPoS based on power index [J]. Journal on Communications, 2022, 43(12): 123-133.
[5]	Dong CUI, Qiaoyan WEN, Hua ZHANG, Huawei WANG. QML: a hybrid spatial index structure [J]. Journal on Communications, 2021, 42(12): 1-16.
[6]	Hongyan WANG,Tuo WANG,Mian PAN,Zumin WANG. Gamma norm minimization based image denoising algorithm [J]. Journal on Communications, 2020, 41(10): 222-234.
[7]	Shunqin XIE,Ke ZHOU,Dahai CHEN,Xianglu LI,Sheng ZHONG,Jian ZHANG. Reduced phase-state detection based on virtual modulation indexes for Multi-h CPM [J]. Journal on Communications, 2019, 40(9): 45-50.
[8]	Shanguo HUANG,Xin LI,Ying TANG,Junfeng GUO. Overview of the key technology of photonic firewall at high speed [J]. Journal on Communications, 2019, 40(9): 157-167.
[9]	Qiang ZHANG,Guojun WANG,Shaobo ZHANG. Method of privacy protection based on multiple edge servers in personalized search [J]. Journal on Communications, 2019, 40(2): 40-50.
[10]	Gaochao LI,Ben LI,Yuhai LU,Mengya LIU,Yanbing LIU. Graph compression algorithm based on a two-level index structure [J]. Journal on Communications, 2018, 39(6): 109-115.
[11]	Zhi-qiang WU,Ken-li LI,Hui ZHENG. Efficient and scalable architecture for searchable symmetric encryption [J]. Journal on Communications, 2017, 38(8): 79-93.
[12]	Shui-fei ZENG,Xiao-yan ZHANG,Xiao-feng DU,Tian-bo LU. Improved incremental algorithm of Naive Bayes [J]. Journal on Communications, 2016, 37(10): 81-91.
[13]	Hai-lun LIN,Yan LI,Wei-ping WANG,Yin-liang YUE,Zheng LIN. Efficient segment pattern based method for malicious URL detection [J]. Journal on Communications, 2015, 36(Z1): 141-148.
[14]	Kai BI,Xiao-dan WANG,Ya-qiong XING. Cluster ensemble selection based on validity index in evidence space [J]. Journal on Communications, 2015, 36(8): 135-145.
[15]	Jia-jie XU,Kai ZHENG,Ming-min CHI,Yang-yong ZHU,Xiao-hui YU,Xiao-fang ZHOU. Trajectory big data:data,applications and techniques [J]. Journal on Communications, 2015, 36(12): 97-105.