电子学报 ›› 2016, Vol. 44 ›› Issue (6): 1343-1348.DOI: 10.3969/j.issn.0372-2112.2016.06.012

• 学术论文 • 上一篇    下一篇

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

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

  1. 1. 中国矿业大学资源与地球科学学院, 江苏徐州 221116;
    2. 安徽工业大学计算机与技术学院, 安徽马鞍山 243032
  • 收稿日期:2014-10-15 修回日期:2014-04-12 出版日期:2016-06-25 发布日期:2016-06-25
  • 作者简介:邰伟鹏 男,1979生出生于安徽马鞍山,博士研究生,副教授.研究方向为时空数据库、移动互联网.E-mail:taiweipeng@ahut.edu.cn;岳建华 男,1964年出生于山东济宁,教授,博士生导师,研究方向为地球物理,GIS系统;邓育 男,1990年出生于安徽六安,硕士研究生.研究方向为时空数据库;陈业斌 男,1971年出生于安徽滁州,教授.研究方向为时空数据库;秦锋 男,1962年出生于安徽马鞍山,教授.研究方向为人工智能.
  • 基金资助:

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

Approximate String Reverse Furthest Neighbors Search

TAI Wei-peng1,2, YUE Jian-hua1, DENG Yu2, CHEN Ye-bin2, QIN Feng2   

  1. 1. School of the Earth Science and Resources, China University of Mining and Technology, Xuzhou, Jiangsu 221008, China;
    2. School of Computer Science, Anhui University of Technology, Ma'anshan, Anhui 243032, China
  • Received:2014-10-15 Revised:2014-04-12 Online:2016-06-25 Published:2016-06-25

摘要:

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

关键词: 近似关键字查询, 反远邻查询, 空间数据库, 外存索引

Abstract:

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 obtained a good performance.

Key words: approximate string search, reverse furthest neighbors search, spatial database, disk resident index

中图分类号: