李 松，张丽平，刘 艳，郝晓红，杨和禹

(哈尔滨理工大学a.计算机科学与技术学院;b.计算中心，哈尔滨 150080)

1 概述

数据集中的近邻查询问题在空间数据库、海量数据查询与分析、大数据处理、数据挖掘、图像处理和交通控制等领域具有重要的研究意义。国内外学者对近邻查询问题进行了广泛研究，在简单最近邻、反向最近邻、组最近邻、线段最近邻和最近对查询等方面取得了一些重要研究成果［1］。

近年来，由于数据量的显著增长和实际应用的需要，数据集中的近邻查询及其变种问题成为研究的热点。国内外的研究进一步拓展到移动查询点的最近邻查询［2］、道路网中的连续最近邻查询［3-4］、连续集合最近邻查询［5］、不确定数据集中的受限最近邻查询［6］、可视最近邻查询［7］、可视反向最近邻查询［8］、高维数据近似最近邻查询［9］、不确定数据集的概率频繁最近邻查询［10］、基于Voronoi 图的反向最近邻查询［11］等方面。所取得的成果解决了最近邻查询领域的一系列重要问题。

作为最近邻查询领域的一个变种问题，单纯型连续近邻链(Simple Continues Near Neighbor Chain，SCNNC)查询在空间数据挖掘、数据相似性分析和智能推理等领域具有较大的作用。已有的研究成果［2-11］无法有效地查询单纯型连续近邻链，为处理单纯型连续近邻链问题，文献［12］基于计算几何中的Voronoi 图对数据集中单纯型连续近邻链问题进行了研究，提出了一种查询数据集中单纯型连续近邻链的方法。文献［13］基于空间索引结构R 树给出了动态数据集中的单纯型连续近邻链查询的算法:SCNNC_R_ST 算法，SCNNC_R_SD 算法和SCNNC_R_XZ 算法。……