空间近似关键字反远邻查询  

Approximate String Reverse Furthest Neighbors Search

作　　者：邰伟鹏[1,2] 岳建华[1] 邓育[2] 陈业斌[2] 秦锋[2] 

机构地区：[1]中国矿业大学资源与地球科学学院,江苏徐州221116 [2]安徽工业大学计算机与技术学院,安徽马鞍山243032

出　　处：《电子学报》2016年第6期1343-1348,共6页Acta Electronica Sinica

基　　金：国家自然科学基金项目(No.61003311);安徽高校省级自然科学研究重大项目(No.KJ2014ZD05);安徽高校省级自然科学研究重点项目(No.KJ2013Z023;No.KJ2013A058);安徽省振兴计划资助项目(No.2013ZDJY073)

摘　　要：空间数据集中的点普遍由空间信息及描述文本信息组成.空间近似关键字反远邻查询(Approximate String Reverse Furthest Neighbors Search,ASRFNS)问题是在一个空间数据集中搜索所有以给定查询点为最远邻,且满足文本相似度条件的目标.基于现有的空间反远邻查询算法以及近似关键字查询算法,我们提出了两个基本的解决算法:凸包最远单元交集(CHFCs Join)算法和凸包最远单元近似字符串串行查询(CHFCASSS)算法;我们又设计了一种包含空间和关键字信息的外存索引结构Filter-Rtree,并给出了相应的凸包最远单元过滤R树(CHFilterRtree)高效算法.通过真实数据集的实验测试,验证这三种算法的有效性,并分析比较了其性能与效率.The points of spatial dataset usually consist of the spatial information and the described text information. The problem of approximate string reverse furthest neighbors search（ASRFNS）query is defined to search all points in a spatial dataset that take the given query point as its furthest neighbor while their text satisfies the string similarity constraint. Based on the existing reverse furthest neighbors search algorithm and approximate string search algorithm,we proposed two solution algorithms：the convex hull furthest cells join algorithm（CHFCsJoin）and the convex hull furthest cell approximate string serial search algorithm（CHFCASSS）.In order to further improve the query performance,we also proposed an efficient algorithm of the convex hull furthest cell filter-Rtree（CHFilterRtree）which contains disk resident structure of space and keyword information.With the real dataset experiments and analysis,the results demonstrate that our proposed algorithms ob-tained a good performance.

关 键 词：查询 反远邻查询 空间数据库 外存索引 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]