空间数据上Top-k关键词模糊查询算法

• 作者: 李国良 胡骏 范举 陈姗姗
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 基于位置的服务 空间数据上的关键词检索 字符串近似匹配
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 研究论文
• 页码范围: 2237-2246
• 分类号: TP311
• 字数: 9689字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2012.02237

摘要

基于位置的服务(LBS)变得日益普及,越来越多的研究开始关注如何对空间中的兴趣点(POI)做有效的检索.现有的方法提出了空间数据上的关键词检索,研究如何根据查询的位置和关键词找到相关的POI点.然而,现有方法主要对查询关键词进行精确匹配,不能支持模糊查询:当查询关键词与底层数据存在微小差异的时候,LBS系统不能返回相关的结果.为了满足移动用户的模糊查询需求,文中对空间数据上的Top-k关键词模糊查询问题进行研究:给定一组POI点,检索与查询关键词近似匹配且空间上距离相近的Top-k个结果.为了提供高效的模糊查询,文中首先定义了一种新型的相关性函数,综合考虑了文本相似性和空间距离,进而提出了一种有效的索引结构RegionTrie,并基于RegionTrie设计了高效的Top-k算法.真实数据集上的实验结果表明,文中提出的Top-k算法十分高效,性能远好于对比方法.