邰伟鹏,岳建华,邓　育,陈业斌,秦　锋

(1.中国矿业大学资源与地球科学学院,江苏徐州 221116; 2安徽工业大学计算机与技术学院,安徽马鞍山 243032)



邰伟鹏1,2,岳建华1,邓育2,陈业斌2,秦锋2

(1.中国矿业大学资源与地球科学学院,江苏徐州 221116; 2安徽工业大学计算机与技术学院,安徽马鞍山 243032)

空间数据集中的点普遍由空间信息及描述文本信息组成.空间近似

反远邻查询(Approximate String Reverse Furthest Neighbors Search,ASRFNS)问题是在一个空间数据集中搜索所有以给定查询点为最远邻，且满足文本相似度条件的目标.基于现有的空间反远邻查询算法以及近似

查询算法，我们提出了两个基本的解决算法：凸包最远单元交集(CHFCsJoin) 算法和凸包最远单元近似字符串串行查询(CHFCASSS) 算法；我们又设计了一种包含空间和

信息的外存索引结构Filter-Rtree，并给出了相应的凸包最远单元过滤R树(CHFilterRtree)高效算法.通过真实数据集的实验测试，验证这三种算法的有效性，并分析比较了其性能与效率.

近似

查询；反远邻查询；空间数据库；外存索引

1　引言

RFN作为空间数据库查询的一部分，近年来逐渐被许多学者深入研究.Bin Yao等人对于单色反远邻问题提出的改进的高效算法凸包最远单元算法(CHFC，the Convex Hull Furthest Cell algorithm)，证明了只有在查询点位于凸包上或者凸包外侧时，查询点才会有最远voronoi单元，以凸包求出最远voronoi单元，进而在R-tree上执行一个范围查询，可以高效的得到查询点的反远邻[4].而近似字符串查询算法一直以来都是广大学者的研究热点[10～12]，大多数算法采用q-gram技术，依靠倒排列表来产生……