计算机与人工智能学院郑宇和李天瑞教授团队成果被国际顶级会议IEEE ICDE 2022录用

来源:计算机与人工智能学院 发布日期: Sat Apr 02 00:00:00 CST 2022 浏览次数:1034

      近期,计算机与人工智能学院郑宇和李天瑞教授团队完成的学术论文“TraSS: Efficient Trajectory Similarity Search Based on Key-Value Data Stores”被国际顶级会议——第38届IEEE国际数据工程学术会议(IEEE International Conference on Data Engineering,简称ICDE)录用。这篇论文是以西南交通大学为第一署名单位。国际数据工程学术会议(IEEE ICDE)是计算机学科公认的数据库、数据挖掘和内容检索领域的国际顶级会议,被中国计算机学会(CCF)列为A类会议。这是我校首次以第一单位在IEEE ICDE发表高水平论文,标志着我校在数据库和内容检索领域的研究成果得到了国际同行的认可。
      相似性搜索已成为许多轨迹数据分析任务的重要组成部分。随着物联网技术的快速发展,使得企业收集轨迹数据的途径变多、速度变快,导致许多轨迹分析任务必须从海量轨迹中寻找相似的轨迹。由于轨迹数据结构复杂,具有不规则的空间形状和连续的时间序列属性,存储和查询海量轨迹数据具有挑战性。计算机与人工智能学院博士生何华均为第一作者,郑宇和李天瑞教授为通讯作者,重庆大学李瑞远副教授和京东智能城市研究院鲍捷、阮思捷和何天赋共同完成的论文“TraSS: Efficient Trajectory Similarity Search Based on Key-Value Data Stores”提出了一种在key-value数据库中快速查询相似轨迹的高效框架。通常,海量轨迹数据可以通过key-value数据库进行管理。然而,现有的key-value数据库只能使用粗粒度的空间索引来存储轨迹数据,并且没有提供高效的查询处理算法来搜索相似的轨迹。TraSS设计了一种新颖的空间索引 XZ*,它利用具有不规则形状和大小的细粒度索引空间来精细地表示轨迹的空间位置和形状。此外,TraSS构建了一个从 XZ* 的多维索引空间到一维连续整数域的编码函数,可方便设计高效的轨迹存储策略和快速的轨迹查询处理算法。进一步地,为了提高相似性搜索的效率,TraSS采用两个步骤来修剪不相似的轨迹:(1)全局修剪。它利用 XZ* 索引来修剪没有相似于查询轨迹的索引空间。TraSS的全局剪枝只会挑选出与查询轨迹具有相似大小和形状的索引空间。与之前最先进的索引相比,TraSS的全局剪枝在查询处理过程中减少了高达 66.4% 的 I/O 开销; (2)局部过滤。它以降低相似度计算复杂度的方式来快速过滤不相似的轨迹。TraSS使用 Douglas-Peucker 算法从轨迹中提取代表性特征来加速局部过滤,极大地降低了查询处理过程中产生的计算量。TraSS在流行的key-value数据库(HBase)上实现了一个开源的工具包TraSS(https://github.com/huajunge/k-sim)。大量实验和实际案例表明TraSS极大地提高了海量轨迹相似查询效率。
 

图1 TraSS基础架构示意图


 

      郑宇和李天瑞教授课题组在智慧城市、大数据等领域取得过多项科研成果,曾获得教育部自然科学二等奖,重庆市自然科学一等奖等。近年来,课题组注重在理论研究的前提下开展产学研融合,该研究是在智慧城市领域取得的阶段性科研成果,得到了学校和学院的大力支持,该成果也成功支持了京东智能城市在北京、雄安、成都、南通和宿迁等城市的智能轨迹数据管理业务。
      该研究受到了国家重点研发计划(No: 2019YFB2103201)的支持。