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

空间数据集中的点普遍由空间信息及描述文本信息组成.空间近似关键字反远邻查询(Approximate String Reverse Furthest Neighbors Search,ASRFNS)问题是在一个空间数据集中搜索所有以给定查询点为最远邻,且满足文本相似度条件的目标.基于现有的空间反远邻查询算法以及近似关键字查询算法,我们提出了两个基本的解决算法:凸包最远单元交集(CHFCsJoin)算法和凸包最远单元近似字符串串行查询(CHFCASSS)算法;我们又设计了一种包含空间和关键字信息的外存索引结构Filter-Rtree,并给出了相应的凸包最远单元过滤R树(CHFilterRtree)高效算法.通过真实数据集的实验测试,验证这三种算法的有效性,并分析比较了其性能与效率.

Approxi mate String Reverse Fu rthest Neighbors Search

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.