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

许建秋; 梁珺秀; 秦小麟

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于时空标签轨迹的k近邻模式匹配查询
- k nearest neighbor pattern match queries over spatio-temporal label trajectories
- 通信学报 2018年39卷第4期页码：112-122
- 作者机构：
  
  南京航空航天大学计算机科学与技术学院，江苏南京 211106
- 作者简介：
  
  [ "许建秋（1982-），男，江苏南京人，博士，南京航空航天大学副教授，主要研究方向为移动对象数据库。" ]
  [ "梁珺秀（1994-），女，江西抚州人，南京航空航天大学硕士生，主要研究方向为移动对象数据库。" ]
  [ "秦小麟（1953-），男，江苏南京人，博士，南京航空航天大学教授，主要研究方向为安全数据库、时空数据库、分布式环境数据管理与安全等。" ]
- 基金信息：
  
  中央高校基本科研业务费专项基金资助项目(NS2017073)
- DOI：10.11959/j.issn.1000-436x.2018063
  中图分类号： TP311
- 网络首发：2018-04，
  
  纸质出版：2018-04-25
- 稿件说明：
移动端阅览
许建秋, 梁珺秀, 秦小麟. 基于时空标签轨迹的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.
许建秋, 梁珺秀, 秦小麟. 基于时空标签轨迹的k近邻模式匹配查询[J]. 通信学报, 2018,39(4):112-122. DOI： 10.11959/j.issn.1000-436x.2018063.

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. DOI： 10.11959/j.issn.1000-436x.2018063.

摘要

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

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.

关键词

Keywords

references

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 .

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 .

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 .

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 .

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.

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 .

GÜTING R H , VALDÉS F , DAMIANI M L . Symbolic trajectories [J ] . ACM Transactions on Spatial Algorithms ＆ Systems , 2015 , 1 ( 2 ): 1 - 51 .

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 .

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 .

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 .

FELIPE I D , HRISTIDIS V , RISHE N . Keyword search on spatial databases [C ] // The IEEE International Conference on Data Engineering . 2008 : 656 - 665 .

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 .

SPACCAPIETRA S , PARENT C , DAMIANI M L , et al . A conceptual view on trajectories [J ] . Data ＆ Knowledge Engineering , 2008 , 65 ( 1 ): 126 - 146 .

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 .

PARENT C , SPACCAPIETRA S , RENSO C , et al . Semantic trajectories modeling and analysis [J ] . ACM Computing Surveys , 2013 , 45 ( 4 ): 1 - 32 .

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 .

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 .

GUTTMAN A , . R-trees:a dynamic index structure for spatial searching [C ] // The ACM SIGMOD International Conference on Management of Data . 1984 : 47 - 57 .

PRASAD V , ADAM C , EVERSPAUGH C , et al . Indexing large trajectory data sets with SETI [C ] // Conference on Innovative Data Systems Research . 2003 .

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 .

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 .

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 .

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 .

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 .

浏览量

2146

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据