定位技术在移动终端上的广泛使用以及基于位置的服务和移动社交网络的发展和普及,产生了大量的轨迹数据,包括车辆轨迹数据和用户轨迹数据。越来越多的应用(如基于热度路线的导航、信息推送和广告推荐以及车辆共享等)对轨迹数据进行分析和挖掘,以实现更好的服务质量。在此过程中的研究重点和挑战包括:(1)轨迹相似度分析,如何定义合理的轨迹相似度函数,并实现大数据集上高效的相似度连接算法。(2)用户轨迹发现问题,如何从大量非标准化的用户社交媒体内容中识别出用户的轨迹,并保证较高的准确度。(3)轨迹匹配问题,采用某种相似度度量标准,如何高效地匹配具有相似出行需求的用户轨迹,实现资源利用的最大化。具体地,本文的主要研究内容和贡献包括:1.基于相似度连接的轨迹分析:论文研究车辆轨迹的相似度连接问题,目的是实现相似轨迹的高效查找。针对现有方法不能较好地度量轨迹相似程度的问题,论文提出一种有效的双向轨迹相似度函数。为轨迹设计基于网格和阈值感知的两种签名,将签名相似作为轨迹相似的充要条件。论文提出高效的基于签名的“过滤-验证”算法框架。在“过滤”阶段,使用基于上下文和基于代价的策略,通过代价较低的签名相似度判定,实现不相似轨迹的快速剪枝。在“验证”阶段,提出了基于签名、基于扩展顺序以及基于上下界的候选集验证策略,进一步提高效率。2.基于微博的轨迹发现:用户在社交媒体发布的内容中包含位置信息,对其进行时间、空间维度的组织和分析可以得出用户轨迹。传统的轨迹发现方法对非标准化用户内容的容错性能欠佳,轨迹识别识别精度较低。本文将位置参考数据组织为位置索引树,进行逐层递进的位置发现。利用模糊匹配方法解决微博内容不规范的问题,发现微博的top-k位置;将多条微博的top-k位置聚合形成用户top-k位置,得出用户轨迹,并反馈优化微博top-k位置的质量。此外,对微博内容和位置参考数据的动态更新也提出了增量式算法,支持数据更新。3.资源利用最大化的轨迹匹配:在研究了车辆轨迹相似度连接和用户轨迹发现的基础上,论文进一步探讨将用户行驶活动形成的轨迹按照某种相似度标准(共享路径百分比)进行匹配,实现资源利用最大化。在基于连接的模型中,将问题转化为二分图最大匹配问题,并设计了高效的保证质量的近似算法。在基于搜索的模型中,提出了基于扩展的策略和最优者最先的策略,实现top-k匹配的最快查找。