抗轨迹差异识别攻击的相似轨迹实时生成方法

用户使用基于位置服务进行连续查询产生的移动轨迹可能会遭受轨迹差异识别攻击,进而造成用户个人隐私的泄露问题,本文依据轨迹r-匿名的思想,提出了一种相似轨迹实时生成方法用来保护用户的个人位置隐私。该方法通过匿名服务器对用户提交进行需要匿名的真实位置计算,实时生成、筛选建立虚假位置集合,利用虚假位置形成的位置轨迹与真实轨迹之间的相似性模糊了真实轨迹,降低了生成的虚假轨迹被攻击者识别的概率,实现了连续位置查询中的实时轨迹匿名。通过性能分析和模拟对比实验验证,进一步说明了本文所提出算法的隐私保护效力和算法执行效率。

基于最长公共子序列的非同步相似轨迹判断

针对非同步相似轨迹判断问题,提出了一种基于最长公共子序列理论的相似轨迹判断新算法。首先,求出查询轨迹线段与候选轨迹线段之间的距离;其次,利用最长公共子序列算法,计算两轨迹的最长公共子轨迹长度;最后,根据相似度门限,判断轨迹是否相似。数值实例验证了所提算法能够提高非同步轨迹的相似度。

一种车辆移动对象相似轨迹查询算法

车辆移动对象的相似轨迹查询问题是当前移动对象数据管理研究中的一个热点,可以应用在车辆缉查防控、出行规律分析及城市道路规划等诸多领域。当前,随着车辆移动对象监测手段的不断丰富,车辆移动对象数据逐渐表现出流式不间断产生、数据量急剧增大的特征。现有的移动对象相似轨迹查询方法在面对具有上述特征的车辆移动对象数据时在查询正确性和查询效率方面暴露出诸多问题。论文针对这种大规模车辆移动对象数据流下的相似轨迹查询问题,提出一种基于双阈值支持度的车辆移动对象相似轨迹查询算法,该算法通过对车辆移动对象数据的预处理来减少查询中涉及的移动对象数据量,以提高移动对象相似轨迹查询的效率,同时保证查询正确性。实验表明,该文提出的算法,在保障正确查询相似轨迹的前提下,效率比传统相似轨迹查询算法提高很多。

搜索路网空间中时空相似轨迹

为了分析移动对象行为特征,需要一种度量轨迹间相似性的方法,虽然在欧氏空间检索移动对象相似轨迹的研究较多,但在路网空间这种研究还不多见。在实际应用方面,大多数移动对象位于路网空间而不是欧氏空间。本文研究了路网空间相似轨迹的特性,并提出了一种在路网空间搜索相似轨迹的度量方法。实验结果表明该方法不仅是搜索相似轨迹的实用技术。

一种面向多场景的轨迹相似度计算框架

轨迹相似度计算作为轨迹数据分析中的一个研究热点,主要用来衡量两个移动对象轨迹相似程度。已有的轨迹相似度计算工作主要根据不同类型的轨迹数据和应用场景提出了大量轨迹相似性度量方法,但随着轨迹数据采集手段的逐渐丰富和应用需求的发展,在轨迹相似性计算方面却缺少一个统一的框架以支持多样化轨迹数据下的相似轨迹分析。为此,本文在综合分析已有相似轨迹度量方法共性特征基础上,提出了一个兼容多种轨迹相似度度量方法的集成计算框架(Multiple Scenarios Similarity Trajectory Framework,MSSTJ),并通过一种统一的轨迹数据分区索引方法来优化不同相似轨迹度量方法的计算效率,从而使得用户可以通过参数化配置的简单方式来实现不同场景下多样化的轨迹相似度高效计算的需求。通过基于两类不同类型轨迹数据集的相关实验表明,MSSTJ可以帮助用户快速实现不同的轨迹相似度计算算法,并且实现的算法具有较好的性能表现。

基于Hausdorff距离的轨迹相似性度量的航迹复原方法

面对有源和无源探测时存在的大量杂波等干扰,导致探测的重点目标航迹存在缺失的问题,采用基于Hausdorff距离的轨迹相似性度量方法,计算重点目标与探测数据中所有批次在距离-时间、方位-时间2个维度的双重Hausdorff距离。以加权Hausdorff距离为相似性度量排序,从探测数据中辨识出与重点目标航迹相似度最高的目标,实现在探测数据中准确辨识重点目标以及复原目标缺失航迹。实测数据验证表明,该方法简单高效,具有工程应用价值。

基于距离变换的轨迹群组相似性度量

从海量轨迹中挖掘移动对象的时空运动规律一直广受关注。轨迹数据的聚类、异常检测、多尺度概化等,都是以轨迹数据的相似性度量为基础的。相较于单一轨迹的相似性,轨迹群组的相似性受到尺度、轨迹数据的多维特征等多种因素的影响,缺乏广泛共识的度量方法。面向轨迹群组相似性度量的需求,本文提出了基于距离变换的轨迹骨架线提取方法,以实现轨迹群组的骨架线提取;并利用最长公共子序列算法开展轨迹群组骨架线的相似性度量;最后,基于GeoLife数据集对本文方法进行了验证。结果表明,基于距离变换的方法能够较好地顾及轨迹数据的多种形态特征。这可为轨迹群组相似性度量提供新思路。

一种融合图结构的时空轨迹相似性查询算法

针对海量时空轨迹数据相似性查询速度慢的问题,提出一种融合图结构的时空轨迹相似性查询算法。从空间维和时间维将轨迹建模为图结构中的一条路径,设计了一种同步匹配空间和时间距离的轨迹相似性度量函数。在此基础上,设计了一种结合时间过滤的基于边的倒排索引结构支持轨迹时空相似性查询,同时利用距离上界的剪枝策略提高查询性能。计算返回的相似轨迹集合中每条轨迹的距离并进行排序,得到相似度最高的前k个轨迹。最后将所提算法与NTrajI算法、SHQ算法、SHQT算法在合成数据集和真实数据集上进行实验对比。结果表明:该算法在索引建立、查询效率和查询质量方面均优于其他对比方法,因此是可行而有效的。

基于大地距离计算相似度的海上目标轨迹预测

目前基于相似度的移动目标轨迹预测算法一般根据数据的时空特性进行分类,无法体现算法自身的特点,为此提出一种基于算法特征的分类方法。轨迹相似度算法通常需要先计算两点之间的距离,再开展后续计算,而常用的欧氏距离(ED)只适用于目标在小区域范围内移动的问题。针对现有基于相似度的轨迹预测算法无法适用于移动范围比较大的海上目标轨迹预测的问题,提出使用大地距离代替ED进行相似度计算。首先,对轨迹数据进行预处理和分段;其次采用离散弗雷歇距离(FD)作为相似性度量;最后,利用模拟数据和实际数据进行测试。实验结果表明,当海上目标移动范围较大时,采用ED算法可能会得到不正确的预测结果,而所提算法可输出正确的目标轨迹预测结果。

基于二级时空分桶的伴随轨迹查询

随着移动传感器设备的普及,人们能够采集到的位置数据越来越多,轨迹数据的规模也越来越庞大.从大规模时空数据中查找与指定轨迹最相似的前k条轨迹一直是时空大数据挖掘的重要挑战之一.现有的相似轨迹查询方法大都包括三个阶段:(1)对海量的离线轨迹数据建立索引;(2)基于索引结构从已知轨迹集中查询与指定轨迹相似的候选轨迹;(3)计算指定轨迹与候选轨迹之间的精确相似度并返回相似度最大的前k条轨迹.但大多数现有方法对轨迹进行聚类索引时不能有效利用时间和空间信息,导致时间相似度不高的轨迹也会被划分到相同的索引项上,最终影响查询的准确性和效率.此外,现有的时空轨迹相似度计算方法存在大量的无效运算,使得相似轨迹的查询效率整体较低.针对当前伴随轨迹查询方法对时间与空间信息利用不充分的问题,本文提出一种新的二级时空分桶索引结构,首先将每条轨迹数据按照时间滑动窗口划分为若干带有时间槽信息的子轨迹,在时间上对轨迹进行一级索引聚类;在此基础上对在相同时间槽内的子轨迹进行二级空间索引聚类,利用哈希算法将具有连续相同位置点的子轨迹映射到同一时空分桶中.与已有索引方法相比,该方法对不同轨迹在索引时具有更好的区分度,查询时的筛选条件更为严格,有效降低了候选轨迹集的规模.针对现有轨迹相似度计算方法效率低下的问题,提出一种基于时差约束的轨迹相似度计算方法.利用轨迹之间的时差排除大量不必要的位置比较运算,将轨迹相似度的计算复杂度控制在线性级别,大大提高了计算效率,同时为过滤伴随轨迹查询过程中的无效计算,对基于时差约束的轨迹相似度计算方法进行变体得到一种上下界过滤方法,最大限度地避免了无效计算.最后,在4个真实的大规模轨迹数据集上对所提方法进行实验验证,实验结果表明所提方法的轨迹查找效率是已知最好方法的9~20倍,证明了算法的有效性.

基于轨迹相似性的用户LBS双重隐私保护方案

根据LBS的特点,为了有效提高隐私保护算法的执行效率,提出了一种基于轨迹相似性的用户LBS双重隐私保护方案。首先当用户发起LBS请求时,分别在用户起始位置和目标位置处的特定区域内生成k-1个随机位置,再随机生成连接起始位置和目标位置的k-1条假轨迹,计算出所有假轨迹和原始轨迹的相似程度,然后选出其中与原始轨迹相似度最低的假轨迹替代用户发起LBS请求;其次,对LBS位置数据集进行预处理,使用字典查询构建位置事务数据库,使用trie树结构存储所得到的位置数据和频率;最后,在trie树上进行频繁位置选取,并使用差分隐私下的拉普拉斯机制扰动位置频率。结果表明,与已有方法相比,对用户的位置隐私进行了双重保护,降低了隐私泄露风险的同时提高了隐私保护算法运算的效率。所提方案在理论分析和实验结果中,可以在安全,隐私和适用性方面取得改进。

基于海量车牌识别数据的相似轨迹查询方法

车牌识别数据是一种具有数据量大、时空相关、位置可测等特征的车辆监测数据,基于此类数据的相似轨迹查询面临着诸多问题。该文给出一种基于"点伴随关系"的车辆相似轨迹定义,提出了一种多级任务并行的相似轨迹查询方法,并给出了基于MapReduce迭代计算模型的方法实现,可支持在海量车牌识别数据集中利用分布计算环境高效地完成相似轨迹查询。基于近千万条真实车牌识别数据的实验表明,相对于传统方法,该方法在保证相似轨迹查询结果准确的前提下具有更好的查询性能。

海量地铁乘客轨迹相似性连接方法:以深圳地铁为例

当前主要的轨迹相似性连接方法都以GPS轨迹为研究对象。针对GPS轨迹的优化方法无法直接用于解决地铁乘客轨迹相似性连接的问题,充分利用地铁乘客轨迹的时空特征,借助轨迹的重复性和对称性,将轨迹从点序列转化为OD序列。以OD序列为基础的轨迹,长度是原轨迹的一半,对应的索引空间变小,后续的计算量也随之减少。着重研究了基于PPJoin+的轨迹连接算法在Spark平台上的设计与实现。在一个13结点Spark集群和一个包含500万个乘客轨迹集合(5.6亿条刷卡记录)的超大规模数据集上验证了该算法的有效性。实验结果显示,基于OD序列的PPJoin+算法的执行时间为14.0 min,比默认的点序列轨迹连接算法的节约了62.5%,比Dima连接算法的节约了78.2%,并表现出了良好的可扩展性。

基于相似轨迹替代查询的位置隐私保护方案研究

针对基于位置服务中移动终端用户位置隐私泄露问题,提出了一个基于相似轨迹替代查询的位置隐私保护方案.该方案在基于位置服务请求的用户及候选者身份匿名化的基础上,采用相似轨迹函数挑选出一定时间间隔内和用户轨迹相似度最高的候选者;然后由该时刻所挑选出的候选者替代用户发起位置服务请求,从而实现用户身份、查询和轨迹的隐私性保护.通过安全性分析,该方案满足匿名性、不可伪造性、以及抵抗连续查询服务追踪攻击等安全特性.仿真实验结果表明,本方案有效提高了最优候选者轨迹相似度以及最优候选者挑选效率.

轨迹相似性度量方法研究新进展

轨迹数据广泛应用于智能交通、自然保护、疫情防控等领域。轨迹相似性度量是轨迹查询分析中最复杂和耗时的操作之一,是轨迹数据管理领域的研究基础。文章首先将轨迹相似性度量方法按对时间信息是否敏感划分为时间敏感型和非时间敏感型,同时介绍了基于语义和深度学习的新型轨迹相似性度量方法;然后对每类度量方法进行了综合对比分析,并给出了各自的优缺点;最后对本领域未来的研究趋势进行了展望。

基于轨迹数据的目标聚类算法研究与应用

文中探讨了轨迹数据的特征分析和目标聚类中存在的挑战,研究了轨迹数据的特征及其在目标聚类中的重要性,提出了以密度和轨迹相似性为基础的聚类算法。在实验设计和数据集选择方面,选取了具有代表性的数据集进行验证,并在算法实现、性能评估等方面进行了深入研究。通过应用案例,分析了该算法在轨迹数据处理中的实际应用效果,为相关领域的研究和应用提供了新的理念和方法。

基于时间约束的Hausdorff距离的时空轨迹相似度量

从海量的轨迹数据中发现用户的相似轨迹是实现基于位置的个性化服务推荐的关键技术之一。位置和时间是轨迹数据的两个重要属性,而已有的基于Hausdorff距离的轨迹相似度量只着重关注于位置属性。针对在计算轨迹间相似性时忽略了轨迹的时间属性这一问题,提出一种基于时间约束的Hausdorff距离的时空轨迹相似度量,利用滑动窗口挖掘两条较长轨迹中所有相似的子轨迹,进而判断较长轨迹间的相似性。实验结果表明,该时空轨迹相似度量具有更好的效果。

群组相似轨迹的特征点映射数据压缩方法

针对车载定位设备的普及产生大量车辆轨迹数据的管理问题,该文提出了一种群组相似轨迹的数据压缩算法。该算法提取每条轨迹的特征点,再将这些特征点进行融合以形成初始参考轨迹。通过定义和求解最优压缩比目标函数,初始参考轨迹被进一步过滤为优化参考轨迹。获得待压缩轨迹的关键特征点与优化参考轨迹的公共特征点之间的映射关系,利用特征点映射关系对每个轨迹进行压缩,将所提出的群组相似轨迹压缩算法与两种代表性算法进行了比较。实验结果证明,本文算法在压缩比方面优于这两种代表性算法,并且在压缩时间上也具有竞争性。该算法的特点在于利用特征点之间的相互映射关系,能够实现对群相似轨迹数据进行统一压缩。

使用轨迹指纹和地点相似性的地点推荐

针对传统的时空轨迹相似性度量算法中存在的计算复杂度高且不适于增量计算的问题,提出了基于相似哈希计算用户时空轨迹相似度的方法,同时使用逆轨迹频率(ITF)度量位置流行度对轨迹相似性的影响,将用户的历史轨迹编码为二进制轨迹指纹,并根据海明距离判断轨迹指纹之间的相似性,使得相似性计算可以在线性时间内完成;此外,改进了地点相似性算法,并将轨迹相似度和地点相似度相结合提出了基于地点和轨迹相似性的地点推荐算法。实验结果表明,本文的推荐方法在准确率、召回率和覆盖率方面能够取得较好的推荐效果,验证了所提方法的有效性。

基于位置的社交网络用户轨迹相似性算法

为了提高在位置社交网络中匹配轨迹相似用户的准确性,提出了一种基于自适应密度聚类的用户轨迹相似性双重加权模型。首先,根据签到点的分布,提出基于聚类区域半径的自适应密度聚类算法,对签到点进行聚类,得到符合一定区域半径的自适应分层聚类区域。然后,针对用户相似性的计算,提出用户轨迹相似性双重加权模型:基于不同层次上权重不同及同一层次上不同签到区域权重不同2个原则。基于分层聚类区域,计算用户访问各分层的轨迹相似性;由于不同签到区域对相似度的表征能力不同,通过不同权重来计算具体层次上的相似性。进而,进行层次上的加权,获得用户总体的相似性。仿真表明,该方法能有效地分析出用户轨迹相似性,具备较高的准确性。