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

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

预定数据链规模的单纯型连续近邻链查询

研究预定数据链规模的单纯型连续近邻链(SCNNC)查询问题,基于Hilbert曲线,提出SCNNC_H_SS算法,将已处理过的数据点从数据集中进行剔除,可减少大量冗余计算。为对SCNNC进行动态维护和更新,提出SCNNC_H_CS算法。理论分析和实验结果表明,在数据集和待查近邻链的规模较大时,相比基于传统树索引结构的方法,该算法具有更高的查询效率。

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

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

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

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

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

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

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

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

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

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