随着定位技术的发展,大量的时空数据不断积累。例如,人们拿着智能手机在城市里活动提供了大量个性化的活动数据,各种车载GPS设备记录着它们走过的所有轨迹。这些时空数据的涌现,使得很多过去难以分析的事情都变得可行起来,这包括人们个性化轨迹的分析、热点旅游路线和旅游项目的挖掘与发现、交通流量的预测等。已经有不少的工作尝试着去分析这些时空数据。一般来说,主要包含两个步骤：第一步是对散乱的GPS点做地图匹配,从而得到车辆/人的轨迹；第二步是对这些轨迹数据进行各种分析。但这些工作都有着各种各样的缺陷。对于地图匹配的工作,不少文章都对高频率采样(High-Sample)的GPS数据提出各种解决方案,但这些算法处理城市中大量存在的低频率采样(Low-Sample)GPS数据时效果却不好。至于轨迹的内容挖掘,一些文章尝试预测车辆未来的轨迹,但是它们假定车辆总是以恒定的速度在行驶,不会加速,也不会因为红绿灯而停止,显然与事实不符。还有些工作集中在挖掘历史的热点道路与地区,但考虑到城市热点道路与区域会经常随着时间在改动,这些分析并不能实时更新以预测未来的热点道路与区域。为此我们先通过预测出路网上的车辆轨迹,再根据这些未来的可能的轨迹,得到未来的热点道路,以此预测未来可能发生交通堵塞的路段或区域。我们先是提出了一个轨迹聚集的概念,来表示城市的路网上某时刻某条路车辆的密度。据我们所知,这是第一个尝试根据当前正在移动的轨迹,结合真实的历史轨迹数据库来预测城市路网车流聚集的工作。本文先尝试用Interative Voting Map Matching来将散乱的低频率的GPS点映射到路网上。然后提出了一个基于Levenshtein距离的轨迹相似度衡量指标,通过搜索历史上那些相似的轨迹来得到某车辆未来的可能位置。得到所有车辆未来的可能分布后,我们再统计出来未来路网的轨迹聚集情况。同时为了提高算法的效率,以达到在线预测的目的,我们提出了基于后缀树的轨迹搜索策略。最后,通过实验验证了我们算法的有效性。