不同维数下空间对象的反最近邻查询.pdfVIP

第16卷第1期 报(自然科学版) 、，01．16No．1 2007年3月 ¨ 湖m 南酊 城№ 柚市C U 院№ 体 (NaturalScience) Mar．2007 学一y 学时 不同维数下空间对象的反最近邻查询 张奋8，黄铁6，潘梅森6 (湖南文理学院a计算机基础部；b．计算机科学系，湖南常德4l5000) 摘要：反最近邻查询是在最近邻查询基础上提出的一种新的查询类型，是空间数据库的应用拓展，在 不同维数下，根据不同的索引结构，反映出空间对象的反最近邻查询差异性较大，从不同索引结构的特性出 发，分析了低维环境下基于R％．树的反最近邻查询优势，提出高维环境下一种新的基于sRdnn一树索引结构的空 间对象反最近查询方法，优化了不同维数下空间对象的反最近查询性能，提高了查询效率． 关键词：R$．树；sRdnn．树；最近邻；反最近邻；空间对象 中图分类号：TP31l 文献标识码：A 文章编号：1672—7304(2007)01∞070-03 Nearest 点分裂，R*．树实行强制重插，选择离节点MBR中心最远 反最近邻(ReverseNei曲bor，RNN)查询是最 的r个元组，将其从该节点删除，并重新插到Rm．树中，有 近邻(NearestNei曲bor，NN)查询的一种拓展，在海量空 间数据的访问中，根据对象的相似性原理，提出了反最近 利于提高存储率和分区质量． 邻的影响集与反最近邻相一致的概念，即某一点口的反最 1．2 SR血n．树的逻辑结构 近邻就是找到数据集中将口作为其最近邻的点，这样的点 sR血n．树结构的设计思想建立在sR．树索引结构基 可以是多个．有效执行反最近邻查询在地理信息系统中是 础上，叶子节点记录形式为(q，咖n)，咖n是日和最近邻之间 一个新研究热点，在空间对象数据挖掘中，根据RNN查 的距离值；非叶子节点记录形式为 询确定位置，可使得某一对象在那里可以发挥最大影响． 不同维数下，根据不同的索引结构，其查询的性能大 c^j坳fr指向节点为根的子树内点，余下记录与sR．树相 不相同，基于R*一的反最近邻查询中，叶子节点存储了以p 同．与标准sR一树不同，sRdnn．树在节点的记录中，加入 为圆心以砌ns(p)为半径的圆的最小包围矩形区域或是最 了最近邻信息，叶子节点L和中间节点^，结构如下： 近邻的距离，RNN查询简化为简单的最近邻查询，在低 L：(EJ…．，B)，(m匹n曼ML)￡f：(q，如胁) 维空间中效率较高；sRdnn一树将最小包围矩形区域和圆域 Ⅳ：(C，’．．，G)，(mⅣ≤n：蛳)G：(S，尺，w，拍f坳fr) 相结合，利用它们的交集将数据分配到直径和容量均较小 的区域，从一查询点到其区域的最小距离应该是查询点到 表示叶子节点中记录数目的最小值和最大值；每个记录 最小包围矩形的最小距离和到最小包围圆的最小距离中 日包含数据点p和属性数据如加，与sS．树中相同．中间节 的大者，这对非均匀分布尤其是集中在某一范围内满足群 分布的高维空间数据查询是非常有利． 点的最小和最大的记录数目，sR一树就是在ss一树中引入了 最小包围矩形尺，也可以说是在R+一树中引入了最小包围 1 空间索引结构 圆s和点数w． 1．1 R+一树的逻辑结构 2不同维数下的反最近邻查询算法描逮 R+一树是R．树中间节点利用对象或点的最小包围矩形 的扩展，插入新的数据时，R．树用容量作为选择分枝的原 2．1 反最近邻查