李 松 胡晏铭 郝晓红 张丽平 郝忠孝

(哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080)

(lisongbeifen@163.com)

随着计算机技术以及传感器技术的不断发展，基于位置的服务得到了广泛的应用，其中最近邻查询作为基于位置服务中重要的支持性技术之一,在许多领域都有广泛的应用.目前国内外学者针对最近邻查询问题进行了广泛研究，为了更好地解决现实问题，学者们提出了一系列的变形，例如概率最近邻查询[1]、反向最近邻查询[2]、连续最近邻查询[3]、组最近邻查询[4]、强邻近对查询[5]、k近邻(knearest neighbor，kNN)查询[6-7]、反向k近邻查询[8]等，其中k近邻查询问题一直吸引学者们的目光.

kNN查询问题作为最近邻查询问题的扩展形式，在现实生活中具有广泛的应用.例如送餐员在接单时会选择距离他最近的k个订单；外出旅行时游客通过手机地图查找最近的k个酒店；新闻网站通过分析与某用户最相似的k个用户的浏览历史为该客户进行新闻推荐等.kNN查询技术除了被应用在现实生活中，也被广泛应用到了科研等领域，然而与多数现实生活中处理的低维数据相反，科研领域要处理的数据多为高维数据.例如天文学中，在宇宙环境中查找与地球最相似的k个星球，不仅要考虑大小、温度，还需要考虑自转速度、大气组成成分等众多维度数据；在计算机的模式识别领域对图像进行基于kNN分类时，需要处理的图像数据的维度可高达成千上万维.由于数据维度的增长，低维空间中的kNN查询……