ISSN: 1673-825X    Imprint: Chongqing University of Posts and Telecommunications Journal
Volume listings
  • Current volume
  •  
  • Search by keywords:
  • Search by 
  • Keywords
  • To
  • Journal archive
Related Links
Spark环境下基于网格索引的轨迹k近邻查询方法
Grid-based k-nearest neighbors query over moving trajectories under spark
DOI:10.3979/j.issn.1673-825X.2019.04.014
Received:December 26, 2017  Revised:February 22, 2019
中文关键词:移动对象  轨迹数据  网格索引  k近邻查询  Spark
英文关键词:moving objects  trajectory data  grid index  k nearest neighbor query  Spark
基金项目:国家自然科学基金(41571401);重庆市教育科学技术研究项目(KJ1400429)
Author NameAffiliationE-mail
XIA Ying School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China xiaying@cqupt.edu.cn 
WANG Ruidi School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China wrd.jn@qq.com 
ZHANG Xu School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China zhangx@cqupt.edu.cn 
NGUYEN Vanluong School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China 2054794756@qq.com 
Hits: 35
Download times: 13
中文摘要:
      移动对象轨迹的k近邻(k nearest neighbor trajectories,kNNT)查询是一种重要的空间信息服务,主要用于寻找与给定轨迹最近邻的k条轨迹,被广泛地应用于智能交通、信息推荐等领域。随着轨迹数据量的快速增长,由于单机计算资源的限制,传统集中式环境下的kNNT查询效率和可扩展性无法满足实际要求。为了解决这个问题,设计了轨迹数据的分布式网格索引结构,该索引在Spark环境下将轨迹切分并映射到网格中,并引入轨迹还原表以保留查询时候选子轨迹段间的连续性。基于此索引,提出了Spark环境下的轨迹k近邻查询方法kNNT-Grid。实验结果表明,kNNT-Grid方法在分布式环境下实现了良好的查询效率和可扩展性,能够应对海量轨迹数据的k近邻查询需求。
英文摘要:
      The k nearest neighbor trajectories (kNNT) query is an important spatial information service, which is mainly to find k nearest neighbor trajectory objects of the given query trajectory, and is widely used in the field of intelligent transportation, information recommendation and so on. However, with the rapid increase of trajectory data volume, traditional kNNT query algorithms for centralized environment are not effective and scalable enough, because the computation and memory of a standalone are limited. To address this problem, a distributed grid index for trajectory data is designed which splits and partitions the trajectory into grids under Spark, and trajectory rebuild table is introduced to keep track of the sub-trajectory segments during the query. Based on the proposed grid index, a parallel query approach kNNT-Grid is proposed. The experiment demonstrates that kNNT-Grid gains better efficiency and scalability in distributed computing environment, which can meet the demand of k-nearest neighbor query on large-scale trajectory data.
HTML    View PDF   View/Add Comment  Download reader