无索引空间数据库的基于最优点的集合最近邻查找算法

针对度量空间中的无索引空间数据库,提出一种基于最优点的集合最近邻查找算法及其改进算法.采用真实数据集与人工生成的数据集对算法进行测试,评估所提出算法的效率.实验结果表明,所提算法的效率优于组最近邻居查询算法,并且对于高维数据空间,所提出的算法有较高的稳定性.由于查询区域中数据点的数量比较少,改进的基于最优点的集合最近邻...     

约束的移动对象最近邻轨迹查询

提出了一种新的查询概念,即约束的移动对象最近邻轨迹(constrained nearest neighbor search on moving objects trajectories,简称CNNMOT)查询.针对两阶段算法分阶段处理最近邻查询和范围查询的缺陷,对传统空间最近邻算法进行了改进和扩展,使其能够合并到一步完成,并对传统的mindist定义进行了修改.实验结果表明:该改进算法能较好地克服两阶段算法的缺陷,并在数据量较大时仍保持较高的性能.     

范围最近邻查询方法研究

范围最近邻(RNN)查询检索到一个区域内每个点的最近邻(NN),它是点和连续最近邻查询的推广.本文将范围看作矩形,分析了二维空间中范围最近邻查询的性质,描述了算法处理过程,并对提出的算法进行了性能分析.     

基于GPGPU的并行LiDAR点云滤波算法

基于边缘点进行LiDAR点云滤波算法在复杂城区具有良好效果,然而在边缘点检测时非常耗时,因此提出基于GPGPU的并行边缘点检测算法来提高滤波的效率.该并行边缘点检测算法分为并行检索k最近邻点、并行拟合平面、并行计算投影点和并行计算夹角等4个步骤.在计算检索k最近邻算法中,提出了队首优先的插入排序算法,大量减少判断次数.实验结果表明,采用GPU并行计算有效提高滤波效率,当数据量达到128 M以上,加速比可以达到9左右.     

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

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

优化区域生长的高分辨率影像道路精确提取

鉴于区域生长存在需提供种子点及易过生长的缺陷,改进了区域生长算法对高分辨率遥感影像进行道路精确提取。首先利用格网对原始影像进行划分,将在道路灰度范围内的外边缘格网以同质性指标依次排序作为候选种子点;将满足道路连续性和一致性要求的路径格网起始点作为种子点;并通过道路指数加以验证得到最终种子点,以此避免盲目选择种子点的不足。其次在引入梯度值进行道路生长后,以二值化的彩色分量与生长结果进行信息融合方式来优化算法,达到缓解过生长的目的。实验结果表明算法是合理有效的,能够较为精确地提取出道路区。     

基于划分采样的初始聚类中心算法

针对大数据集的初始聚类中心选取问题,在基于密度的划分算法和适用于大规模数据集限定初值的采样算法基础上,提出了一种用于初始聚类中心的划分采样算法。对聚类子空间在每一维上进行均匀划分形成不同的数据区域,根据数据区域的数据点数的多少进行采样来提高采样的准确性。利用采样思想缩小了数据集的规模,保证了算法在时间上的优势。通过不同规模、不同形状的数据集对算法进行验证,实验结果表明,与其它初始聚类中心算法相比,该算法在准确率和时间上都具有一定的优势。     

道路网络中移动对象的连续反k最近邻查询算法

在道路网络中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,基于欧氏空间的反k最近邻查询算法不适用于道路网络。为了解决道路网络中移动对象连续的反k最近邻查询问题,给出了道路网络的一种索引结构及一种利用扩展树处理查询的方法,在此基础上,提出了道路网络中适用与单、双色连续反k最近邻查询算法（CRkNNMA算法）,证明了该算法的正确性。     

基于有点区域的K近邻搜索新算法

目的对不同的点云数据,根据有点区域占空间包围盒的比率的不同,对栅格划分最优边长进行估算。方法在分析已有栅格边长估算方法的基础上,提出基于有点区域的二次分割算法来估算最优边长。结果给出了算法的步骤,并将该算法应用于不同的点云数据进行邻域搜索。结论与单次划分的边长相比,新算法的边长估算更加合理、计算效率更高。     

一种应用于电子地图道路特征点提取的新方法

电子地图中的道路信息数据往往数据量比较大,在进行地图匹配时,不利于对电子地图的快速搜索,因此需要对道路数据进行压缩,提取道路特征点。为此在对现有的道路特征点提取方法进行分析的基础上,提出了一种基于无限圆逼近曲线的自适应道路特征点提取方法。该算法依据道路的曲率变化,按照自适应步长对道路数据进行压缩。仿真实验结果表明,该算法计算量小、逼真度高,有效地提高了电子地图道路数据压缩效率。     

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

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

一种改进的离群点检测方法

现有的离群点检测算法运用于规模较大的数据集时,其时间效率和检测效果通常不够理想.通过对离群点分布特征的分析,在计算每个数据点到其kth最近邻对象距离的同时,结合其k最近邻的分布情况,给出一种改进的离群点度量方法.基于上述思想构造的离群点检测算法DokOF能够处理混合属性数据.实验表明,该算法具有良好的适用性和有效性.     

基于时空相关的传感器网络汇聚查询算法

减少网络中的数据传输量是传感器网络节约能量、延长网络生命的重要方法.提出一种基于时空相关的传感器网络汇聚查询算法STCAQ.在STCAQ中,首先通过基于时间相关的预测算法对网络中节点采样数据进行汇聚;然后依据节点采样数据汇聚结果,通过基于空间相关判定算法查询空间相关区域信息.仿真结果表明,STCAQ在能量消耗、查询质量和网络数据量等方面优于ESA算法.     

形貌约束的多视角点云分阶配准方法

为提高大数据量多视角点云的配准效率,提出一种基于多分辨率模型的多视角点云分阶配准方法。首先根据平坦形貌约束条件对点云进行递归分割,提取所得割集的核心点作为特征点构造多分辨率模型,然后采用迭代最近点算法基于该模型上层数据求解多视角点云的初始变换矩阵,将其作用于模型后逐级求解下层数据的变换矩阵,最终将复合变换矩阵同步作用于原多视角点云,实现原多视角点云的精确配准。实验结果表明,该分阶配准方法可有效缓解点云单一简化结果导致的配准精度与效率之间的矛盾,在显著降低点云规模的前提下实现原始点云精确配准;当点云规模达106级别时,与加权尺度迭代最近点(WSICP)算法相比,该方法的计算效率提高约2.5倍。     

复杂激光点云数据中路面自动化提取技术

为了从数据量十分庞大的点云数据中提取出所需的道路要素,实现道路基础设施的数字化,该文提出了一种复杂激光点云环境中的路面提取方法.基于最近行车轨迹数据点进行道路剖面的划分,搜索出每个点的最近行车轨迹点,并根据它们的编号来进行剖面划分.采用两个连续点的距离、高程、点到行车轨迹的距离这三项指标,通过它们的阈值进行路面点的判断...     

云环境下基于衰减因子网格的Skyline查询

为了解决云环境下对于海量数据的Skyline查询,提出了在Map-Reduce框架下基于衰减因子网格Skyline查询(SQBDFG)算法,该算法通过衰减式的网格进行区域划分,利用网格间的统治关系进行快速过滤,达到减少传输开销的目的,并针对网格的衰减速度会影响实际查询性能进行进一步优化.首先提出网格的最大剪枝空间和最大剪枝效率两个概念,然后从理论上证明了采用衰减式网格在处理海量数据的Skyline查询时在这两方面具有明显的优势.最后通过Hadoop分布式集群上的大量实验,在Skyline查询时间和数据I/O开销两个方面进行对比,证明了提出的SQBDFG算法具有良好的有效性和实用性.     

移动环境下的最近邻居查询

提出了移动数据点在某一时刻最近邻居(Nearest Neighbor)的查询算法(M—NN)，着重考虑移动数据点的速度、方向、时间等参数。此算法将分为两种情况进行讨论：只查询移动数据点运动中某个时间点的情况和需要查询移动数据点在所有时间的情况。     

基于多层图划分的云环境软件部署管理算法

针对在云服务器上软件构件分配时需要最大限度地减少所需带宽的问题,提出一种基于多层图划分算法的混合算法,来解决云计算环境中的软件部署问题。该算法对重边匹配(HEM)算法进行改进,同时添加1个新的约束条件来进行粗化,且使用类似KL的算法进行细分,最后结合退火算法从而实现对图划分算法的重新设计和评估。与传统的图划分相比,本文提出的算法考虑到基础设施的异构性,因此不局限于平衡划分。实验仿真结果表明:相比传统的KL图划分算法,提出的混合算法在执行时间和求解质量之间取得很好的平衡,综合性能优于传统算法。     

一种基于抽样的谱聚类集成算法

谱聚类是利用样本数据集的相似性矩阵中特征向量的性质对样本数据集进行聚类.而随着数据规模的增加,谱聚类算法所耗时间会因为大规模的特征分解而明显增大.采用抽样方法可以有效降低算法所耗时间,但是简单随机抽样子集之间关联性太弱,通常无法准确反映数据集的分布特征.基于此,设计了一种新的抽样策略,利用该方法进行多次抽样,生成多个既具有关联性又具有差异性的数据子集.在每个数据子集上分别利用NJW算法(由Ng A Y、Jordom M I和Weiss Y提出)进行谱聚类,并根据最近邻原则将聚类结果映射到全体数据集,生成若干基聚类,最后,将聚类结果集成,得到最终的聚类划分.实验证明,该方法与传统NJW算法以及简单抽样集成算法相比,算法的效率及有效性有了一定的提高.     

一种分布式环境下的skyline查询算法

skyline计算在多标准决策、数据挖掘和数据库可视化等领域具有非常重要的作用.研究了分布式环境下的skyline查询问题.提出通过合并局部skyline集合得到全局skyline集合的思想,在计算全局skyline集合时,先对局部skyline集合进行区域划分和动态编码,然后根据各个区域之间的制约关系进行数据合并.通过实验分析可知,当全局skyline集合的规模较大时,经过区域划分的算法比起直接合并的算法执行效率更好.