路网环境中标签化移动轨迹的时空查询

There are massive trajectories for location tracking from various location-based services (LBS). Effective use of these data has been an active topic in past few years. But the raw geometric trajectories are not suite for generic query. This proposal addresses a model called labeled trajectory to capture a wide range of meanings derived from a geometric trajectory. Labeled trajectories can represent, for example, the names of roads traversed obtained by map matching, transportation modes, places, activities etc. At first a language for pattern matching is introduced. It handles labeled trajectories in full generality and also provides sophisticated specification of temporal conditions.With these abilities, it does matching and classification.Then we propose a Voronoi-based network index for trajectories. Each cell of this Voronoi diagram is centered by one intersection and contains the objects that are close to it. And next we study customized path finding problem. It is a new path finding query which finds the most frequent path (MFP) during user specified time periods, areas or roads in large-scale historical trajectory data. Efficient weighted subgraph construction and searching algorithms along with two novel indexes is proposed. Finally, we investigate keyword cover search of labeled trajectories. We define keyword rating of objects by the count of trajectories visit，the distance by the network distance，and also propose a scalable algorithm can do heuristic search.

移动轨迹数据的高效、科学处理，对提高基于位置服务的服务质量具有重要意义。原始的轨迹位置信息仅包含时间、坐标等要素，不适合于一般的查询和处理。本文提出了轨迹标签化的概念，将轨迹点坐标信息标注为路段、地点以及相关的道路层次、用户活动等上下文信息，使其带有高层的语义进而方便查询利用。项目首先对通用的标签化预处理模式匹配语言展开研究。该语言适用点、线及多边形区域等空间概念，提供时间维度的复杂定义，能够进行准确的轨迹标签化以及分类。然后提出了基于路网Voronoi图网格的轨迹索引方法，将区域划分成若干以道路交叉点为中心的Voronoi图网格，对在同一网格中的对象进行二级索引。在此基础上，对使用历史轨迹数据的个性化路径推荐问题展开分析，介绍了推荐过程中权重子图实时高效构建和搜索的方法。最后，针对标签化轨迹的关键字覆盖查询，提出了对象被访问次数的快速统计和采用历史轨迹进行启发式搜索的方法。

移动轨迹数据的高效、科学处理，对提高基于位置服务的服务质量具有重要意义。原始的轨迹位置信息仅包含时间、坐标等要素，不适合于一般的查询和处理。本项目使用轨迹标签化的概念，将轨迹点坐标信息标注为路段、地点以及相关的道路层次、用户活动等上下文信息，使其带有高层的语义进而方便查询利用。.项目分几个阶段展开了研究：在2016年对路网移动轨迹处理技术的进一步全面综述；这2017对路网环境中轨迹数据标签化预处理和索引技术展开了研究；2018年对研究要点中的个性化路径推荐，关键字覆盖查询两个方向展开了研究；2019年部分研究成果在工程中应用中进行了推广。.截止2019年12月，通过本项目培养了研究生9名，在国际上有影响的学术期刊、以及学术会议上发表论文23篇，申请发明专利1项。在杭州市公交公司电动汽车在线监控项目中应用了部分研究成果。.项目研究内容包括基于轨迹处理技术的路径规划和关键字覆盖查询、推荐，主要贡献如下：.a.提出了一种分层道路的频繁路径查询算法，通过轨迹重构权值图，以每条边被选择的次数即频繁度作为路径权值，进行路径的推荐基础上，再根据城市己有的道路级别规划，引入了路网分层的思想，降低了算法的复杂度。 .b.活动轨迹是指带有用户活动关键字的轨迹，本项目提出了一种活动轨迹和用户查询的匹配问题和轨迹段的匹配方法。该方法将整条活动轨迹划分为一段段的活动轨迹片段，然后找出能够匹配部分用户查询活动的那些轨迹片段，并将这些轨迹片段连接起来组成一条能够完整匹配用户查询活动提供给用户。.c.基于轨迹搜索的路径规划技术。给出一系列查询点，首先将这些查询点转换成它们附近的道路，找出相交于这些道路的轨迹片段，然后利用这些片段拼接出行车路径。.d.提出并定义了一种新的面向集合的反向空间关键字查算法，利用区域剪枝和半空间剪枝技术提高算法效率。.e.基于出租车轨迹的寻客区域挖掘与推荐,充分利用寻客区域与驾驶员经验之间的相关性等隐含因素来挖掘出一些更高质量的寻客区域和高可行的个性化寻客路线..项目还对不确定数据的组最近邻查询、交通异常检测、基于事物的POI推荐等问题展开了研究，在各项研究中，通过实验和分析的手段验证了所提解决方法的可行性，对生产实践有很好的借鉴意义。