高维主存高维主存的的反向K 最近最近邻邻查询及连接 刘 艳1,2，郝忠孝1,3
(1. 哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080；2. 长春大学计算机科学技术学院，长春 130022；
刘小华自杀
3. 哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001)
摘 要：对高维主存的反向K 最近邻(KNN)查询进行研究，提出一种∆-RdKNN-tree 索引结构。通过在该索引结构上进行主存KNN 自连接，预处理数据集中点的KNN 距离信息。将这些距离扩展到索引的各层节点中，基于该索引设计高维主存的反向KNN 查询算法以及反向KNN 连接算法。分析结果表明，该算法在高维空间中是有效的。 关键词关键词：：高维；主存；反向K 最近邻查询；反向K 最近邻连接；预处理 High-dimensional Main-memory
Reverse K Nearest Neighbor Query and Join
LIU Yan 1,2, HAO Zhong-xiao 1,3
(1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China;
2. College of Computer Science and Technology, Changchun University, Changchun 130022, China;
3. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
【Abstract 】The Reverse K Nearest Neighbor(RKNN) problem is a generalization of the reverse nearest neighbor problem which receives increasing attention recently, but high-dimensional RKNN problem is little explored. This paper studies on the high-dimensional main-memory RKNN queries, proposes an indexing structure called ∆-RdKNN-tree, precomputes KNN distances of points in the dataset by main-memory KNN self-join based on this index and propagates these distances to higher level index nodes. Main-memory RKNN query algorithm based on this index is proposed and main-memory RKNN join algorithm is given for set-oriented RKNN queries. Analysis shows that the two algorithms are effective in high dimension space.
【Key words 】high-dimensional; main-memory; Reverse K Nearest Neighbor(RKNN) query; Reverse K Nearest Neighbor(RKNN) join; preprocess- ing
DOI: 10.3969/j.issn.1000-3428.2011.24.008
计 算 机 工 程 Computer Engineering 第37卷 第24期
V ol.37 No.24 2011年12月
December 2011
·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)24—0022—03 文献标识码文献标识码：：A
中图分类号中图分类号：：TP311.13
1 概述
反向K 最近邻(Reverse K Nearest Neighbor, RKNN)查询在决策支持系统、市场决策、资料库文件搜索、生物资讯及地理信息系统(GIS)等领域中起着非常重要的作用。目前对RKNN 查询的研究主要局限在RNN 查询和低维数据。高维RKNN 查询的研究不是很多，文献[1]只给出了求高维RKNN 查询近似解的方法，文献[2]给出在度量空间上的RKNN 查询算法，文献[3]中的TPL 算法在低维空间中且k 比较小时是有效的，但在高维空间中修剪搜索区域的计算代价非常昂贵。这些RKNN 查询算法都是针对磁
盘系统而设计的，随着主存容量越来越大，且价格逐渐低廉，使得将数据集和索引装入主存成为可能，已有算法不再是最好的选择。
目前已提出的有效处理RKNN 查询的方法可以分为 2类：预处理方法和空间修剪方法。当数据的维数高或k 值大的时候，空间修剪方法的计算代价是非常昂贵的，所以在KNN 连接可用且高效的情况下，本文采用预处理方法实现高维数据的主存RKNN 查询和RKNN 连接。
2 索引结构∆-RdKNN-tree
2.1 ∆-RdKNN-tree 的构建
为了有效地支持高维主存反向K 最近邻查询和连接，本文在主存索引结构∆-tree-R [4]的基础上为包含N 个点的数据集R 构建∆-RdKNN-tree 。该索引结构在∆-tree-R 的节点记录
中加入了K 最近邻距离信息以满足查询反向K 最近邻的需
要。∆-RdKNN-tree 的叶子节点主要包含形如(center , radius , num , pointer , code , codeLen , max _dknn )的记录，其中，center 、radius 和num 分别为叶子节点的中心、半径及其包含的数据点的数目；pointer 为指向数据点的指针；code 、codeLen 分别为叶子节点在∆-RdKNN-tree 中的编码及编码长度；max _dknn =max{dknns (p )}，dknn 表示点p 到它的第k 个最近邻之间的距离值，p 是该叶
子节点中包含的点。
内部节点包含表示该节点自身信息的形如(num , code , codeLen , max _dknn )的记录，以及表示该内部节点中包含的子聚类的信息，形如(center , radius , children )的一组记录，每个子聚类(即孩子节点)对应一个记录，其中，num 、code 、codeLen 和max _dknn 的含义与叶子节点中的各项类似；center 、radius 分别为子聚类的中心和半径；children 为指向子聚类(即下一层孩子节点)的指针。
构建索引∆-RdKNN-tree 时，∆-RdKNN-tree 各节点中max _dknn 的初始值为−1。本文提出的索引∆-RdKNN-tree 既支持KNN 查询及连接，也支持RKNN 查询及连接。
基金项目基金项目：：黑龙江省自然科学基金资助项目(F2006-01)
作者简介作者简介：：刘 艳(1981－)，女，讲师、博士研究生，主研方向：高维数据处理，空间数据库；郝忠孝，教授、博士生导师 收稿日期收稿日期：：2011-07-15 E-mail ：liuyan6374@yahoo
第37卷第24期23
刘艳，郝忠孝：高维主存反向k最近邻查询及连接
2.2 修剪原理
定理1(点与节点之间的修剪原理) 在转换后的低维
PCA[5]空间中，如果查询点与∆-RdKNN-tree中节点之间的距
离大于该节点的max_dknn值，则该节点中不包含查询点的
RKNN。
证明详见文献[6]中的定理1。
定理2(节点与节点之间的修剪原理) 在转换后的低维
PCA空间中，如果∆-RdKNN-tree中的节点A与∆-tree中的
节点B之间的距离大于节点A的max_dknn值，则节点A中
不包含节点B中各查询点的RKNN。
证明：设Q为聚类B中任意一点，其转换后为Q′。PCA
转换后，聚类A的中心到Q′的距离大于到聚类B的距离，由
文献[6]中的定理1，Q到聚类A中任意一点的距离大于转换
后Q′到聚类A的距离，所以，转换后的低维空间中2个聚类
之间的距离为这2个聚类中任意2点之间距离的下限，命题
得证。
3 反向K最近邻
最近邻查询及连接算法
查询及连接算法
∆-tree-KNN-Join[4]是一种有效的高维主存KNN连接算
法，该算法使用∆-tree[7]作为基础索引，采用编码解码、自底
向上、深度优先遍历和剪枝等技术，解决了KNN连接中确
定搜索半径困难的问题。本节通过在∆-RdKNN-tree上执行
∆-tree-KNN-Join的自连接算法，求出数据集R中各点的KNN
距离，再通过算法Add-Distance-KNN将这些KNN距离信息
扩展到∆-RdKNN-tree各层节点的max_dknn中。在∆-tree-
KNN-Join的自连接算法中，不需要对∆-RdKNN-tree中的叶
子节点进行解码，直接使用其编码到它们的各祖先节点，
小学科学网站然后按自底向上的顺序进行连接即可，具体算法参见文
献[4]。算法Add_Distance_KNN通过深度递归的方式遍历
∆-RdKNN-tree中的各节点，对于每个节点遍历其中包含的数
据点，取KNN距离的最大值作为该节点的max_dknn，限于
篇幅，具体算法省略。
3.1 基于∆-RdKNN-tree的反向K最近邻
最近邻查询
查询
算法RKNN_Query的符号说明：node为∆-RdKNN-tree
中的内部节点；queryPoint为与数据集R中的数据点同时经
过PCA转换的查询点；result表示queryPoint在数据集R中
的反向K最近邻的集合。
算法1 RKNN_Query(基于∆-RdKNN-tree的反向K最近
邻查询算法)
输入node，queryPoint
输出result
begin
(1)for node中的每个孩子节点child i do
if P_dist(child i, queryPoint, m child
i.lev
)<child i.max_dknn then;
if child i为内部节点then
RKNN_Query(child i, queryPoint);
else //为叶子节点
for child i中的每个数据点point do
if dist(point, queryPoint)<point.dknn then
//point.dknn表示点point到它的第k个最近邻之间的距离
result = result∪point;
(2)return result;
end
定理3算法1对∆-RdKNN-tree正确地进行了RKNN查
询。时间复杂度为O((f L−1−1)m child
i.lev α/(f−1)+f Lαd)。其中，f
是∆-RdKNN-tree中节点的扇出；m child
i.lev 为孩子节点child i
所在层的维数；α为步骤(1)中第1个if语句的选择度；d为
数据点的维数。
证明：
正确性：执行步骤(1)，遍历node中的每个孩子节点
child i，由定理1，如果child i到queryPoint之间的距离小于
child i中max_dknn的值，则根据节点类型分2种情况进行处
理：如果child i为内部节点，则递归调用算法RKNN_Query，
对以child i为根的子树进行RKNN查询，如果child i为叶子节
点，则遍历child i中的每个point，计算point与queryPoint
之间的距离，将小于KNN距离的点加入结果集。当递归调
用停止时，该算法使用修剪策略完成对∆-RdKNN-tree的
RKNN查询。
可终止性：算法RKNN_Query被调用的次数是有限的，
步骤(1)中for循环可自动终止，故该算法可终止。
时间复杂度分析：执行步骤(1)，∆-RdKNN-tree中节点执
十一刀
行P_dist()的时间复杂度为O((f L−1−1)m child
i.lev
α/(f−1))；∆-
RdKNN-tree中叶子节点执行dist()的时间复杂度为O(f Lαd)。
综上，该算法总的时间复杂度为O((f L−1−1)m child
i.lev
α/(f−1)+
f Lαd)。
证毕。
3.2 基于∆-RdKNN-tree的反向K最近邻
最近邻连接
连接
在使用RKNN的数据挖掘任务中往往需要为数据集中的
每个点执行RKNN查询(即面向集合的RKNN查询)，本节给
出基于∆-RdKNN-tree的RKNN连接算法。对于进行主存
局地战斗机RKNN连接的2个数据集R和S，首先将它们同时进行PCA
转换，然后分别为转换后的数据集R和S构建索引
∆-RdKNN-tree和∆-tree[7]。
算法RKNN_Join及其子算法Leaf_RKNN_Join的符号说
明：leafR、nodeR分别为∆-RdKNN-tree中的叶子节点和内部
节点，leafS、nodeS分别为∆-tree中的叶子节点和内部节点，
result表示数据集R中每个查询点的反向K最近邻的集合。
算法2 Leaf_RKNN_Join(leafR和leafS进行反向k最近
邻连接)
输入leafR，leafS
输出result
begin
(1)for leafS中的每个查询点queryPoint do
if (P_dist(leafR, queryPoint, min(m leafR.lev, m leafS.lev)) <
leafR.max_dknn) then
for leafR中的每个数据点point do
if dist(point, queryPoint) < point.dknn;
result = result∪point;
(2)return result;
end
定理4算法Leaf_RKNN_Join对leafR和leafS中的数据
点对正确地进行了RKNN连接。时间复杂度为O(f(m min+σ′fd))
数字图像相关
级。其中，m min为m leafR.lev和m leafS.lev中较小的维，在满足
∆-RdKNN-tree的情况下，m min取值为d，m leaf.lev为节点leaf
所在层的维数，σ′为步骤(1)中第1个if条件的索引选择度。
证明：
正确性：执行步骤(1)，根据定理1将leafS中距离leafR
大于leafR.max_dknn的queryPoint过滤掉，然后使用dist()
计算leafS中剩余查询点与leafR中每个数据点之间的真实距
离，将距离小于KNN距离的数据点对加入结果集。
可终止性：该算法中只有一个双重for循环，故可自动
24 计算机工程2011年12月20日终止。
时间复杂度分析：执行步骤(1)中内、外层for循环都为
O(f)级，P_dist()为O(m min)级，dist()为O(d)级，故算法的时
间复杂度为O(f(m min+σ′fd))。
证毕。
算法3 RKNN_Join(基于∆-RdKNN-tree的反向K最近邻
连接算法)
输入nodeR，nodeS
输出result
begin
(1) Queue = NewPriorityQueue(); result = ∅;
(2) for nodeR中的每个孩子节点child i do
for nodeS中的每个孩子节点child j do
if (P_dist(child i, child j, min(m child
i.lev , m child
j.lev
)) <
child i.max_dknn) then
if child i和child j都为内部节点then
RKNN_Join(child i, child j);
else if child i和child j都为叶子节点then
result = Leaf_RKNN_Join (child i, child j);
else if child i为叶子节点且child j为内部节点then
Enqueue (Queue, child j);
While Queue非空do
node = RemoveFirst(Queue);
for node中的每个孩子节点child k do
if (P_dist(child i, child k, min(m child
i.lev
,
m child
k.lev
)) < child i. max_dknn) then
if child k是内部节点then
Enqueue (Queue, child k);
else // child k是叶子节点
result = Leaf_RKNN_Join
(child i, child k);
else //child i为内部节点且child j为叶子节点
处理方法与第3种情况类似，故省略
(3) return result;
end
定理5算法RKNN_Join正确地对∆-RdKNN-tree和∆-tree进行RKNN连接，是可终止的，时间复杂度为O((f2−f2L−2)f2m levσ/(1−f2)+f2L−1σd(1+fσ′))，其中，σ为步骤(2)中第1个if条件的索引选择度；m lev表示∆-RdKNN-tree中第lev层使用的维数。
证明：
正确性：执行步骤(1)，初始化优先队列Queue和result。执行步骤(2)，由定理2，保留nodeR和nodeS中满足节点与节点之间修剪条件的孩子节点对，然后根据节点类型分4种情况进行处理。当对该算法的递归调用停止且Queue为空时，该算法对∆-RdKNN-tree和∆-tree中所有满足修剪条件的叶子节点对进行了RKNN连接，由定理4，该算法对∆-RdKNN-tree中和∆-tree中所有点对正确地进行了RKNN 连接处理。
可终止性：在步骤(2)中，双重for循环及单重for循环均可自动终止，算法RKNN_Join被递归调用的次数及Queue 的容量都是有限的，算法Leaf_RKNN_Join可终止，故该算法可终止。
时间复杂度分析：满∆-RdKNN-tree和满∆-tree的情况下，执行步骤(2)，∆-RdKNN-tree和∆-tree中的节点对执行P_dist()的时间复杂度共为O((1+(f 2−f 2L−2)σ/(1−f 2))f 2m lev)，叶子节点对执行算法Leaf_RKNN_Join的时间复杂度共为O(f2L−1σd(1+fσ′))，故算法的时间复杂度为O((1+(f2−f2L−2) σ/(1−f 2))f 2m lev+ f 2L-1σd(1+fσ′))。
证毕。
4 算法性能分析
目前还没有专门为高维主存RKNN查询和连接设计的算法，在为磁盘而设计的高维RKNN查询算法中，或是不能提供准确的解[1]，或是计算代价昂贵[3]。本文采用预处理的方法求解主存RKNN查询，在高维情况下，使用“一次计算的操作”KNN连接代替多个KNN查询是非常好的选择，文献[4]已证明KNN连接算法∆-tree-KNN-Join的高效性，所以本文使用它的自连接算法计算出数据集R中每个点的KNN 及KNN距离；文献[7]已对算法RangeQuery的优越性进行了证明，所以基于该算法的RKNN查询算法RKNN_Query具有较高的效率；文献[8]已对∆-tree-Join算法的高效性进行了证明，故本文基于该算法的RKNN_Join算法具有较优的性能。另外，本文提出的RKNN查询及连接算法也适用于灵活的k，当k变化时，只需在索引∆-RdKNN-tree上重新执行∆-tree-KNN-Join的自连接算法和算法Add_Distance_KNN以更新索引节点中的max_dknn值后，就可以对新的k进行RKNN查询及连接。
5 结束语
本文为基于主存的高维数据设计了索引∆-RdKNN-tree，根据该索引提出了主存RKNN查询算法RKNN_Query和RKNN连接算法RKNN_Join。算法性能分析表明，这2个算法是高效的和可扩展的。高维主存K最近对连接、KNN连接和RKNN连接的具体应用问题有待于进一步研究。
参考文献
[1] Singh A, Ferhatsomanoglu H, Tosun A S. High Dimensional
Reverse Nearest Neighbor Queries[C]//Proc. of the l2th International Conference on Information and Knowledge Management. New Orleans, Louisiana, USA: ACM Press, 2003: 91-98.
[2] Achtert E, Bohm C, Kroger P, et al. Efficient Reverse k-Nearest
Neighbor Search in Arbitrary Metric Spaces[C]//Proc. of the ACM International Conference on Management of Data. Chicago, Illinois, USA: ACM Press, 2006: 515-526.
[3] Tao Yufei, Papadias D, Lian Xiang, et al. Multidimensional
Reverse kNN Search[J]. International Journal on Very Large Data Bases, 2007, 16(3): 293-316.
[4] 刘艳, 郝忠孝. 一种基于主存∆-tree的高维数据KNN连接算
回馈制动法[J]. 计算机研究与发展, 2010, 47(7): 1234-1243.
[5] Jolliffe I T. Principal Component Analysis[M]. New York, USA:
Springer-Verlag, 1986.
[6] 刘艳, 郝忠孝. 基于∆-tree的递归深度优先KNN查询算法[J].
计算机工程, 2011, 37(22): 48-50.
[7] Cui Bin, Chin O B, Su Jianwen, et al. Contorting High Dimen-
sional Data for Efficient Main Memory KNN Processing[C]//Proc.
of the ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2003: 479-490.
[8] 郝忠孝. 时空数据库查询与推理[M]. 北京: 科学出版社, 2010.
编辑任吉慧
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议