采样过滤下的时空热点查询

作者：李艳云; 牛保宁^*; 康家兴

来源：太原理工大学学报, 2020, 51(04): 522-529.

DOI：10.16355/j.cnki.issn1007-9432tyut.2020.04.006

• 时空热点
• 分布式计算
• 规律采样
• 阈值过滤
• 热点候选集

目前较高效的时空热点查询算法是基于Spark分布式计算框架和Getis-Ord统计量的两阶段map-reduce算法。为了解决其在第一阶段map-reduce,遍历全部轨迹数据导致耗时严重及数据分布不均匀导致资源空闲的问题,本文提出一种对轨迹数据采样的方法S-RSampling(stratified-random sampling),通过分析轨迹数据的分布规律,确定采样规模,从而减轻数据分布不均的影响,大幅降低查询时间;为了解决在第二阶段map-reduce,计算大量无用立方单元格导致计算浪费的问题,本文提出一种阈值过滤方法TFiltering(threshold filtering),根据单元格属性值的分布,动态确定阈值T,将属性值top-T的立方单元格作为热点候选集,从而减少计算浪费。实验表明,本文所提出的优化方法在查询结果准确率不降低的情况下能大幅降低查询响应时间。

• 单位
  太原理工大学