数据集中单纯型连续近邻链查询方法

为解决数据集中的单纯型连续近邻链查询问题,提出一种基于Voronoi图的查询方法。给出单纯型连续近邻链查询的定义,利用Voronoi图的性质对大量数据点进行精减,设计可准确查询出数据集中单纯型连续近邻链的查询算法。实验结果表明,随着待查连续近邻链所含数据点规模的增大,该方法的效率比传统基于R树方法更高。     

障碍物环境下的动态单纯型连续近邻链查询

单纯型连续近邻链查询在空间数据查询、空间数据挖掘和网络搜索等领域具有重要意义。针对障碍物环境下动态数据集中的单纯型连续近邻链查询问题,着重考虑新增点和删除点对初始单纯型连续近邻链的影响,基于判定圆域对初始单纯型连续近邻链进行二次计算和判断,提出在数据集动态增大和动态减小环境下的OB_DYNSCNNC_ADD和OB_DYNSCNNC_DET查询算法,以实现对数据集的有效筛选和过滤。理论研究和实验分析表明,2种算法均能实现障碍物环境下动态数据集中的单纯型连续近邻链查询,并具有较高的查询效率。     

动态受限区域内的单纯型连续近邻链查询方法

受限区域内的单纯型连续近邻链查询在空间数据挖掘、数据的相似分析和推理、空间数据库等方面具有重要的作用。为了弥补已有方法的不足,详细研究了动态受限区域内的单纯型连续近邻链查询方法。基于计算几何中的Voronoi图给出了VOR_IN_CRSCNNC算法、VOR_EX_CRSCNNC算法和VOR_DE_CRSCNNC算法。进一步进行了实验比较和分析。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一筛选和判断的冗余计算,在处理空间数据量较大、初始受限区域数据量较多、受限区域形状较为复杂的单纯型连续近邻链查询方面具有较大的优势。     

障碍物增减情况下的单纯型连续近邻链查询

单纯型连续近邻链查询在空间数据挖掘、空间数据库、数据的相似分析和推理等方面具有重要的作用。为了弥补已有方法的不足,对动态障碍物环境下的单纯型连续近邻链查询（ObSCNNC查询）问题进行了详细研究。利用Voronoi图和判定圆给出了ObSCNNC_Search算法,进一步提出了障碍物动态增加情况下的查询算法（ObSCNNC_ADD算法）和障碍物动态减少情况下的查询算法（ObSCNNC_DET算法）。对所提方法进行了实验比较与分析。理论研究与实验分析表明,所提方法较适合处理障碍物环境下的单纯型连续近邻链问题。     

受限区域内的单纯型连续近邻链查询方法

由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题,针对受限区域和障碍物的复杂性,详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法,分别提出了VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法。算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算,每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点,预先过滤掉大量数据,减少每次计算涉及的数据量。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一判断的冗余计算,受受限区域形状的影响较小,较大程度提高了查询效率。     

受限区域内的单纯型连续近邻链查询方法

由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题,针对受限区域和障碍物的复杂性,详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法,分别提出了VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法。算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算,每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点,预先过滤掉大量数据,减少每次计算涉及的数据量。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一判断的冗余计算,受受限区域形状的影响较小,较大程度提高了查询效率。     

RTC树的构建与不确定近邻关系查询方法

空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

外包空间数据库中反向k近邻查询验证

在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(ReversekNearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.     

基于特征选择与鲁棒图学习的多视图聚类

现有的多视图聚类方法大多直接在原始数据样本上构建各视图的相似图,而原始数据中的冗余特征和噪声会导致聚类精度下降。针对该问题,基于特征选择和鲁棒图学习提出多视图聚类算法FRMC。在自适应选择不同视图特征时降低数据维度,减少冗余特征,同时利用自表示学习获取数据的表示系数,滤除噪声影响并得到数据样本的全局结构,从而去除样本中的噪声和离群点。在此基础上,通过自适应近邻学习构造样本鲁棒图,利用鲁棒图矩阵的加权和构建最终的亲和图矩阵,提出一种基于增广拉格朗日乘子的交替迭代算法对目标函数进行优化。在6个不同类型的标准数据集上进行实验,与SC、RGC、AWP等算法的对比结果表明,FRMC算法能够有效提升聚类精度且具有较好的收敛性与鲁棒性。     

GSwMKnn:基于类别基尼系数子空间的加权互K近邻算法

在高维数据空间中,存在大量冗余或无用的属性,这使得在子空间中寻找目标类更为有效．为此文章提出基于类别基尼系数子空间的加权互k近邻算法,利用类别基尼系数求出其对应的软子空间并将待分类样本和训练样本投影到各个类别子空间中,再在各软子空间中使用类别基尼系数加权距离互k近邻算法计算出待分类样本在各个子空间的投票权重并叠加,最终得出待分类样本的类标签．在公共数据集上的实验结果验证了该方法的有效性．     

位序互补的空间关联规则挖掘算法

为有效地提高基于空间事务的挖掘算法效率,提出一种基于位序的互补空间挖掘算法,其适合在海量数据中挖掘任何长度的频繁项;该算法用定序项目集的方法来减少现有算法存在的冗余判断操作和计算,同时也用非频繁项目集的补集来快速生成候选项,删除了现有双向挖掘算法中的空闲操作,可以有效地降低算法的运行时间。实验结果表明此法在空间数据挖掘中比现有算法更快速而有效。     

空间聚类与方向关系的融合技术研究

在大数据量的环境下,传统空间数据的空间关系仅描述两个空间物体,从而出现数据存储冗余,检索速度慢等问题。提出改进的聚类算法对空间物体聚类,再在聚类结果的基础上表示空间物体的方向关系。提出了基于密度的K-均值算法和空间聚类与方向关系融合的新方法。所提方法增强了空间数据库对空间数据对象的空间方向关系的智能处理能力,节省了存储空间,提高了数据的查询速度。     

An evaluation and query algorithm for the influence of spatial location based on RkNN

This paper is devoted to the investigation of the evaluation and query algorithm problem for the influence of spatial location based on RkNN (reverse k nearest neighbor). On the one hand, an object can make contribution to multiple locations. However, for the existing measures for evaluating the influence of spatial location, an object only makes contribution to one location, and its influence is usually measured by the number of spatial objects in the region. In this case, a new measure for evaluating the influence of spatial location based on the RkNN is proposed. Since the weight of the contribution is determined by the distance between the object and the location, the influence weight definition is given, which meets the actual applications. On the other hand, a query algorithm for the influence of spatial location is introduced based on the proposed measure. Firstly, an algorithm named INCH (INtersection’s Convex Hull) is applied to get candidate regions, where all objects are candidates. Then, kNN and Range-k are used to refine results. Then, according to the proposed measure, the weights of objects in RkNN results are computed, and the influence of the location is accumulated. The experimental results on the real data show that the optimized algorithms outperform the basic algorithm on efficiency. In addition, in order to provide the best customer service in the location problem andmake the best use of all infrastructures, a location algorithm with the query is presented based on RkNN. The influence of each facility is calculated in the location program and the equilibrium coefficient is used to evaluate the reasonability of the location in the paper. The smaller the equilibrium coefficient is, the more reasonability the program is. The actual application shows that the location based on influence makes the location algorithm more reasonable and available.     

基于时序聚类的北斗位置冗余数据压缩算法

在北斗用户机的位置数据采集过程中,容易出现数据冗余现象。为此,分析导致数据冗余的原因,提出一种基于时序聚类的冗余数据压缩算法。该算法采用基于密度的聚类方法将数据集进行分簇,把属于同一类运动特征的位置数据归为一类,根据簇直径判断该簇是否为冗余数据,并对冗余数据进行压缩。实验结果表明,该算法可以正确标识冗余数据,实现数据压缩。