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

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

基于旅行时间的Top-k轨迹查询

为了进一步完善现有的轨迹查询,本文提出一种基于旅行时间的Top-k轨迹查询,给定查询点,可以为用户返回k条轨迹.这k条轨迹的选择依赖于用户感兴趣的位置点和旅行时间,为用户返回k条旅行时间最短的轨迹.针对该查询,提出一种查询算法,利用网格索引来记录轨迹点的信息,算法使用Best-First方法对查询点附近的轨迹点进行检索,并通过判断其是否为有效点来检索完全有效轨迹.为了提高查询效率,提出三种终止规则,其减少了需要访问轨迹点的数量.最后,通过实验验证该算法的有效性.

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

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

基于固定网络的移动对象轨迹查询

在基于固定网络的移动对象轨迹查询方面,现有的索引模型只能管理移动对象当前和过去或将来轨迹的查询,它们都不能同时实现移动对象的现在,过去和将来轨迹查询。本文在IMORS的索引结构基础上进行改进并提出了一种新的索引结构,它能实现基于固定网络的移动对象的全时态索引。

基于分布式3D R-Tree索引的轨迹查询方法研究

城市中的公共汽车和出租车每天都产生大量的GPS轨迹数据.如何查询和管理这些大规模轨迹数据是一个极具挑战的问题。本研究以大数据计算引擎Spark的RDD组件为基础,设计并实现了分布式的3D R-Tree,通过全局索引和局部索引加速轨迹查询。文章以一个13节点的Spark集群和3万辆出租车一周产生的2.97亿条GPS记录为基础,使用3个经典查询(轨迹点查询,区域查询,子串查询)和2种分区方式(空间网格,时空网格)对该方法进行了评估。实验结果显示:在时空网格分区条件下3个查询时延最短,轨迹点查询、子串查询和区域查询的时延分别为:2.33 s、3.33 s和6.88 s。

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

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

基于行程拆分的快速查询显示轨迹的方法

单个设备既要掌握设备的整体位置概况,又要查看每个轨迹点细节,目前轨迹查询方案无法很好地同时兼顾全局和细节。基于此,提出一种基于行程拆分的快速查询显示轨迹的方法,支持长达数月时间跨度的行程查询,针对单个行程支持缩放式地查询轨迹细节。

移动对象轨迹Top-K查询研究综述

随着基于位置服务应用的不断普及,实现移动对象轨迹实时查询成为当前时空数据库领域的研究热点,其中,移动对象轨迹的Top-K查询是面向轨迹大数据的一种快速查询方法。文章对移动对象轨迹查询方法及应用的研究现状进行全面梳理,从不同角度对Top-K查询优化算法进行归纳分析,对Top-K查询研究中存在的问题和未来研究方向进行总结和展望。

一种基于语义轨迹的相似性连接查询算法

随着移动互联网的快速发展和智能移动设备的广泛普及,携带文本信息的轨迹数据量大量增加,随之而来的轨迹相似性查询研究也在如火如荼地开展。空间轨迹相似性研究是查询轨迹集合中相似轨迹的主要方法,即缩减轨迹数量。由于许多的轨迹都是携带大量文本信息的,而空间轨迹相似性研究考虑的是距离方面,缺少对于文本信息的考虑。针对这一问题,在空间相似性的基础上增加对于文本相似性的考虑,同时将整个空间网格化,通过采用计算空间文本相似性上下限进行范围查询,得到最终的结果,使得轨迹相似性查询更全面,也更具有说服力。

支持预测查询和部分历史查询的移动对象索引方法

针对TPR*-tree隐含移动对象部分最近历史信息但不能提供历史信息查询的问题,将移动对象创建或更新时间引入到索引树中,提出一种既支持预测查询又支持部分历史信息查询的索引树Basic HTPR*-tree,为全时态查询奠定了坚实的基础.同时,为了支持移动对象的频繁更新,在Basic HTPR*-tree索引树基础上引入内存概要结构和Hash辅助索引结构,提出支持自底向上更新策略的HTPR*-tree索引结构.实验结果表明,HTPR*-tree更新性能优于TPR*-tree和Basic HTPR*-tree(TD_HTPR*-tree),预测查询性能仅仅稍逊于TPR*-tree.

移动对象查询研究进展

移动对象查询技术是目前数据库技术研究的热点。移动对象的查询处理技术不仅要追求高效率和高精确度,而且要充分考虑到现实可行性和不同维度空间的可拓展性。本文基于前人对移动对象查询的分类方法,根据移动对象查询的发展动态,将移动对象查询分为轨迹查询和坐标查询两大类;回顾了已有的各种查询处理方法,分析了各种方法的优缺点,并且基于方法间的继承性和互补性,为后续的查询研究提出了建议。

支持多种查询的室内移动对象索引

随着室内定位技术的广泛应用,室内位置服务快速发展.移动对象索引技术作为支撑位置服务的核心技术,大多数都基于室外环境,难以直接应用于室内空间.现有的室内移动对象索引,仅关注对移动对象历史数据的查询,且支持的查询类型单一.为此,提出MQII(multiple queries indoor index)索引结构,对移动对象历史和当前位置信息进行索引,能够同时支持对象位置查询、轨迹查询以及时空范围查询.索引采用对象链表和桶链表结构,实现从对象和时空范围2个方面对移动对象数据的管理;提出针对该索引结构的有效更新、查询算法;实验结果表明,与现有室内移动对象索引相比,索引不仅能够支持历史查询和当前查询,还能够同时高效支持对象位置查询、轨迹查询和范围查询.该方法可应用于办公楼、医院等多种室内空间.

轨迹图谱:一种基于知识图谱结构的轨迹信息抽取方法

现有的这些方法对轨迹数据需根据不同的应用设计不同的数据结构、存储结构、查询算法等,缺少通用性。为了使得轨迹数据更具有通用性,提出了将轨迹转换为知识图谱结构的方法。该方法结合轨迹数据的特点及知识图谱的定义,分别抽取出轨迹数据的实体、关系、属性并构造了轨迹图谱。转换为轨迹图谱后的轨迹数据具有通用的图结构,可直接支持轨迹的基本查询、范围查询、最近邻查询、关键词查询、模式查询等,并可轻易地将其添加到各种现有的知识库中。最终通过在真实数据集上的实验,对比了各类轨迹查询在轨迹图谱方法及普通数据库方法中的表现,证明了轨迹图谱方法的高效性及通用性。

基于DR-tree的室内移动对象索引研究

对于移动对象历史轨迹索引,现有的方案绝大多数都基于室外空间,难以直接应用于室内空间中;同时,未将对象本身作为一个独立的维度加以索引,无法提供高效的对象轨迹查询方式。对此,提出了一个室内环境下的移动对象索引结构DR-tree来对移动数据的位置、时间、对象三个维度进行索引,并将位置维与对象维解耦,将三维索引转换为两个二维索引,同时给出查询优化方案。实验结果表明,与现有的室内环境下的索引方案RTR-tree相比,该结构不仅能够提供高效的时空查询,而且还能提供高效的对象轨迹查询。

基于道路网络的时空索引方法IMon-tree

针对Mon-tree索引的不足提出一种基于道路网络的时空索引方法 IMon-tree。索引分三层,顶部用四叉树网格来索引道路网络,底部二维R树用来索引物体的运动信息,中部单链表将上述两层连接起来,完成从道路到运动信息的映射。为了支持轨迹查询,用哈希表将物体的运动信息组织起来。对比实验表明IMon-tree轨迹查询比TMN-tree性能更好,时空查询算法平均响应时间是Mon-tree的65%,是TMN-tree的81%。该方法可应用于各种空间数据库以及地理信息系统。

非羁押性强制措施的数字化监管问题研究

随着当前犯罪结构的改变和司法改革的推进,非羁押数字化监管模式应运而生,能够取代传统监管,提高非羁押的诉讼风险防控能力,解决传统模式下监管缺失的难题。非羁押作为一项诉讼权利,是否适用数字化监管由办案机关决定,适用过程中的监管主体应是社区矫正部门。APP的第一层级是注册登录页面,第二层级是每日打卡、轨迹查询、线上审批和违规统计四个模块,以视频抽查和打卡抽查防止人机分离。被监管者发生轻微违法时系统发出警告,严重违法时由办案机关决定转为逮捕。数字化监管一般适用于可能判处五年有期徒刑以下的嫌疑人,以是否开启实时定位为区分设置两级监管,避免过度侵犯隐私,准确识别系统漏洞,明确责任分配。

基于不均匀空间划分和R树的时空索引

随着移动互联网以及物联网的发展,越来越多的移动设备都内置GPS服务,从而产生了大量的时空数据.这些数据体量大、分布不均匀且带有时间和空间经纬度等多维属性.传统的时空索引还有很多问题有待解决,例如难以处理大规模数据、无法同时处理时间和空间维度等.基于Geohash和R-Tree,提出一种2层时空索引GRIST(Geohash and R-Tree based index for spatio-temporal data),第1层是空间索引,它将空间划分为不同大小的网格并使用Geohash进行编码;第2层是时间索引,由R-Tree构成,不同R-Tree索引不同网格里的数据.GRIST索引支持面向时间和面向时空的查询.在大量随机数据和真实Uber数据上的实验表明:GRIST在索引的构建效率上较于GeoMesa和PostGIS系统可以提升10～45倍,在查询效率上可以提升2～4倍.

基于语义和访问权限的室内移动对象索引

随着无线通信和室内定位技术的发展,室内移动对象索引技术在基于位置的服务等方面越来越重要。室内场景结构复杂且形式多样,现有的室内移动对象索引技术的研究都是将室内实体抽象为单元,将移动对象抽象为查询点,不区分它们之间的语义,也不考虑对象和单元之间的访问权限。针对这一问题,研究了一种基于语义的室内移动对象索引方法,并提出了基于语义和访问权限的轨迹推荐查询算法。另外,将室内场景、移动对象的语义和访问权限信息进行了形式化定义,提出了一个新的室内语义模型。通过大量实验,从多个方面与现有室内移动对象索引方法进行对比分析,验证了所提索引的高效性和鲁棒性。

基于MSP430的特种车辆云监控系统

本文设计了一套基于MSP430的特种车辆云监控系统,由供电模块、MSP430主处理器模块、无线通信模块、监控模块、存储模块、上位机管理系统等组成,针对目前的监控规划系统主要只适用于普通车辆,对特种车辆的监控仍然处于缓慢发展状态的背景下,本软件以特种车辆为主要中心设计,通过与交管部门的协同合作以及由硬件监控模块收集车辆运行状态信息,由MSP430主处理器处理数据信息,各个硬件模块之间通过无线通信实现数据的传递,以软件平台展示出实时监控特种车辆的运行状态和后期查询车辆的运行轨迹,同时可以清晰呈现对特种车辆规划好的行驶路线,从而能够有效全面地监控特种车辆,查询管理特种车辆的规范作业,提高特种车辆的道路通行效率,减小路段事故发生率。

定位技术在煤炭公路运输车辆上的应用

对于公路煤炭运输车辆目前的现状进行了分析,介绍并推荐采用车辆定位技术,解决煤炭车辆管理上面临的棘手问题。以提高效率,节约资源,提升管控力。