移动对象的反向最近邻查询方法研究

在移动对象允许相互提供某些服务的地方,反向最近邻居(RNN)能有效地运用到许多应用中。提出了一个在指定时间间隔内计算一个查询点的RNN查询的有效方法,在这里假设查询和数据点都在空间内连续移动。做为解决子问题的方法,同时提出了解决连续移动点NN查询的算法。     

基于格网划分的道路最近邻查询算法

针对现有道路最近邻查询算法均以数据点作为道路端点进行查询,并未考虑数据点在道路上的情况,使得在大数据量时查询效率不够理想的问题,利用格网划分算法进行解决。利用分治法的思想,将查询区域进行格网划分,缩小有效的查询区域,快速定位查询点所在道路,进而找到最近邻数据点。研究结果表明:当数据量足够大时,格网划分算法与增量网络扩张(INE)算法相比,查询时间明显降低,效率明显提升,格网划分查询的时间复杂度为O(1);当数据量较少时,格网划分算法与INE算法相比,查询时间减少并不明显,表明格网划分算法更适用于大数据量最近邻查询。     

移动环境中的位置依赖连续轮廓查询

针对移动环境中查询点快速移动时连续、高效输出给定搜索区域数据轮廓的问题,提出一种位置依赖连续轮廓查询算法(LDCS).该算法结合数据流技术,首先使用R树快速更新查询数据,然后利用两次连续计算时搜索区域的重叠性构造被动数据流,并对新增和失效数据分别进行处理,从而连续输出轮廓.由于充分利用了已有结果,LDCS的计算量较传统算法有大幅下降.实验结果表明,LDCS特别适合计算频度要求较高的场合,与基于网格索引的算法相比,时间效率随着数据集规模的增大显著提升.     

公路网移动终端的KNN查询技术

公路网中移动兴趣点(POIs)的查询处理是一个难点,目前的研究多基于欧氏距离对静态POIs进行处理,不能很好地适应移动环境下终端弱连接和频繁移动的需要.文中在公路网移动计算场景下,设计了一种存储分区数据对象的结构来表示公路网图形模型,提出适用于移动终端的连续KNN查询(CQ-KNN)算法.该算法改进了Wang等提出的MKNN算法,将逐层渐近探测和检索边列表结合起来进行近邻查询,避免了MKNN算法在限定层数不够却不得不执行范围查询时所带来的开销;同时使用缓存策略来支持移动终端提交的连续查询请求,并给出基于广播位置失效报告的缓存一致性维护策略.仿真结果表明,CQ-KNN算法较MKNN算法有更快的CPU处理速度和更短的网络响应延时,并且能支持移动终端的离线KNN近似查询.     

基于残差融合的时序数据离群点检测算法

物联网的快速发展产生了海量的高维时序数据,然而时间序列易受到外界变化的环境因素影响而产生离群点。针对现有的离群点挖掘算法不能兼顾时序数据的趋势性、季节性、循环性、不规则性的特点,从而导致检测效果不理想的问题,提出一种基于残差融合的时序数据离群挖掘(residual integration outlier,RIO)算法。首先利用线性自回归移动平均模型(autoregressive integrated moving average model,ARIMA)拟合数据,得到在相同时间粒度下的残差序列,并将该序列作为非线性模型长短期记忆网络(long short-term memory,LSTM)模型的输入,输出残差序列预测值,而后将经由ARIMA模型与LSTM模型处理的序列在相同时间粒度下融合,得到一条经由混合模型两次处理的残差序列。最后,利用基于直方图的离群点模型(histogram-based outlier score,HBOS)检测出该二次残差序列的离群点。实验表明,RIO算法的准确度得到了较为明显的提高,具备良好的实用价值。     

路网移动对象空间关键字连续Top-k查询

为了克服现有空间关键字查询方法大多只适用于欧氏空间查询处理的局限性,提出了一种渐增监控查询处理方法(CMA),以高效处理路网中移动对象空间关键字连续top-k查询问题(CMkSK).该方法用一棵组合扩展树CEtree来界定查询的监控范围,通过识别、处理监控范围内对查询结果有影响的查询点和移动对象的位置更新对相应的CEtree进行修正,以保证查询结果的持续有效性.所提出的方法考虑了现实生活中对象的可移动性,可以处理查询点和数据对象在路网中自由移动的情形.最后,通过模拟实验证明了所提出算法较参照算法的性能提高约1.1倍.     

一种社交网络环境下并行短文本查询算法

随着移动社交网络的迅速发展,如何从海量带有时间属性和地理位置属性的短文本信息中快速查询到有效信息具有重要意义.社交网络环境下传统短文本查询算法忽略时间维度,并且在海量数据下无法满足用户快速响应的需求.针对以上问题,提出一种社交网络环境下并行短文本查询算法.提出的算法设计了基于MapReduce模型下的查询框架,该框架使用了基于滑动窗口下的多版本时空索引(MVSTR-tree),保证了查询过程中融合了时间和空间属性,实现了对海量数据高效查询的目标.最后,通过真实数据集的实验证明该算法能有效缩短查询时间.     

分布式网络中 CKNN 查询的 BORA 优化汇聚

针对时空数据库中,移动对象轨迹的连续K近邻查询(continuous K nearest neighbor query,CKNN)的查询效率较低的问题,以及在分布式的移动对象数据库(moving objects databases,MOD)环境下,提升对应查询结果的数据汇聚效率问题进行了研究.在CKNN查询中,设计优化了查询海滩线的更新算法,通过在轨迹数据结构中增加更新标志位,减少了轨迹线段参与的判定运算;同时在假设的类网格覆盖的分布式空间环境下,利用基于Bresenham覆盖的路由汇聚(Bresenham-based overlay for routing and aggregation,BORA)方法,进行查询结果的汇聚;并针对不同近邻参数、轨迹数目、移动对象速度、汇聚方式等对查询时间的影响进行了仿真实验;仿真结果表明,不同参数数值的增加延长了处理时间,基于BORA的汇聚方式比一般的汇聚方式节省了更多的处理时间,提高了系统查询及处理的效率.     

时空数据库中反向最近邻查询的方法研究

随着无线通讯及连续移动对象寻轨技术的高速发展，迫切需要提出解决大量移动对象查询的有效方法。本文提出了一个解决连续移动点反向最近邻查询的算法，同时也提出了解决连续移动点的最近邻查询算法。     

面向推荐系统的多目标决策优化算法

针对推荐系统利用多目标决策技术进行位置信息的查询与推荐时,由于查询者位置的移动和空间障碍物的位置变化导致传统多目标决策技术的查询效率较低的问题,提出了一种基于范围的障碍空间连续Skyline查询算法。首先,根据静态Skyline点的特征对由空间数据对象信息组成的初始数据集进行约减;然后,根据障碍空间中查询者的位置移动的特点构建距离相交模型,利用距离相交模型和数据对象的属性提出了剪枝策略,再根据剪枝策略过滤掉当查询者的位置移动时对查询结果无影响的数据对象,从而精减了冗余数据,得到过滤后的候选数据集;最后,根据数据对象的非空间属性和相互间的支配关系特征得出影响候选数据集的事件,利用影响候选数据集的事件再对候选数据集进行精炼计算,从而减少了冗余计算,查询出当前时刻的结果集。理论研究与实验结果表明：所提算法在查询者位置移动和空间障碍物位置变化时,能提升多目标决策技术的查询效率;相对传统对比算法,在数据集规模、障碍物数量、查询范围增大时,所提查询算法的平均效率提升约13%;针对多维度数据信息的查询,所提查询算法的平均效率提高了约11%。     

一种新的运动点目标检测方法

常规运动目标检测中所用图像都是基于二维空间坐标的序列图,文中根据运动点目标与静态背景的特性,采用一种新的图像表示方法,以时间和空间为坐标,描述的时空图像能较直观地反映运动目标与静态背景的差异,易于实现目标与背景分离。通过实例处理表明,时空方法能更有效地从复杂背景中检测出低信噪比的运动点目标,抗噪声干扰能力强。     

基于线结构光点云三维重建的弯管形工件测量方法

弯管形工件在化工、冶金生产中应用广泛,对其截面参数要求精确度极高,但该类工件由于内外形状不规则,人工测量效率低、细节捕捉度差、出错率高,难以满足工业在线实时检测的要求,因此提出使用线结构光扫描获取弯管外形三维点云数据的方法对弯管截面进行实时测量.使用已标定好的线结构光三维测量平台扫描约以4.3 cm/s移动的弯管模型并获取其点云数据,对点云数据进行最近点迭代法配准、高斯滤波去噪、改进的角度偏差法简化,然后采用Delaunay三角网生长算法对点云进行三维重构,并对重构模型的宽度、半径、内径进行拟合测量.实验测量过程耗时约20 s,测误差小于0.05 mm,结果表明该方法具有较高的精确度与准确性,可大幅度提升工件检测效率,有良好的工业应用前景.     

基于改进随机抽样一致的点云分割算法

随着三维点云数据模型在三维建模、测绘、智能城市以及机器视觉等领域的应用,点云数据处理也成为一个研究热点。点云分割就是将三维空间中点云通过一系列算法,将散乱的点云数据划分成更为连贯的子集的过程,可以为后续的数据分析提供数据基础。针对随机抽样一致算法(random sample consensus, RANSAC)对杂乱、无规则点云数据分割效果不佳的问题,提出一种改进的RANSAC点云分割算法。该算法通过构建Kd(K-dimensional)树,利用半径空间密度重新定义初始点的选取方式,进行多次迭代来剔除无特征点,在实现点云分割的同时可以有效去除噪声点;此外,该算法重新设定判断准则,优化面片合并,可以实现点云的精确分割。实验通过对散乱点云数据进行分割,结果表明该改进RANSAC算法的点云特征提取数据量较大,面片分割的准确性较高,是一种有效的点云分割算法。     

动态卷积的3D点云目标检测算法

针对不规则且稀疏的点的提取特征问题,提出一种以动态卷积作为特征提取的3D点云目标检测算法.首先,以一种新型的动态卷积的方式自适应学习点的位置特征,分类出前景点与背景点,同时对提取出的前景点逐一做回归框;然后,用非极大值抑制选出分数值最好的回归框.其次,进行粒度的细化,得到修正规范的3D回归框,完成3D物体的目标检测.最后,在KITTI数据集上验证算法的有效性.结果表明：文中所提算法在汽车类、行人类、自行车类数据集上的3D点云目标检测精度更高.     

从序列图像中获取点目标三维运动参数

本文研究了摄像机有机动,而点目标在短时间内作匀速直线运动的情形.研究表明,只要点目标——摄像机相对运动方程满足可观测性条件,那么就可从三幅序列图像中确定点目标的三维运动参数,进而估计出它的空间坐标.文中还对算法的抗干扰能力进行了分析,结果表明,摄像姿态以及点目标——摄像机相对运动方程的曲率是影响算法抗干扰能力的两大因素。最后给出了计算机模拟结果.     

基于分区的带球射门算法研究

为了提高足球机器人的射门成功率,提出了一种基于分区的带球射门方法。该方法以球为中心对场地进行分区,机器人按区域决定运动路径进行追球以达到合适的射门点,在进行角度调整后执行带球算法。实验结果表明,与原有几种射门算法相比,提出的算法通过合理路径规划减少了射门的追球时间。在引入带球算法后,射门成功率有了明显提升,并扩大了执行进攻策略的范围。整体提升了进攻与防守的效率。     

最优顶点覆盖的贪心边近似算法

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证（能得到最优覆盖点数）时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.     

采用空气阻力修正的火箭残骸落点算法

针对火箭分离后残骸落点计算问题,分析了火箭残骸在下落过程中的动力学特性,重点就空气阻力对残骸落点产生的影响进行研究,提出了带空气阻力修正的火箭残骸落点算法。与传统落点计算方法不同之处在于,该算法充分考虑落点地区的大气分层空气密度的影响,并根据下落过程空气动力学方程,估计空气阻力因子,采用积分法计算残骸在空中的运动轨迹并得到最终的落点数据。最后计算分析了4次卫星发射任务（对应4种火箭型号）一级残骸的落点,对算法的有效性进行了验证。     

基于灰度峰谷点的快速识别定位算法

在通常的基于灰度值的快速定位算法基础上，提出了基于灰度峰谷点的快速识别定位算法，能够迅速准确定出运动目标的位置坐标，并对二者的优缺点进行了比较。     

变点检测和控制图在数据业务监控中的应用

为实现对数据业务支撑系统的有效监控,通过剖析数据业务特点,提出了用控制图和变点监测发现数据业务中存在的异常。变点监测在处理三种类型的时间序列时存在不足,本文通过增加控制参数——变化率,对变点检测算法进行了改进,改进后的方法适应性更高,并且误报率大大降低。最后比较了控制图和变点检测方法的优缺点及各自的应用场景。