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

被引：14

作者：

胡骏

范举

李国良

陈姗姗

机构：

[1] 清华大学计算机科学与技术系数据库研究组

来源：

计算机学报 | 2012年 / 35卷 / 11期

关键词：

基于位置的服务; 空间数据上的关键词检索; 字符串近似匹配;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

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

引用

页码：2237 / 2246

页数：10

共 4 条

[1] Location-aware type ahead searchon spatial databases:Semantics and efficiency .2 Roy S B,Chakrabarti K. Proceedingsof the SIGMOD Conference . 2011
[2] Approximate string joins in adatabase (almost).for free .2 Gravano L,Ipeirotis P G,Jagadish H V,Koudas N,Muth-ukrishnan S,Srivastava D. Proceedings of the VLDB . 2001
[3] http://www.wireless.att.com/lbs .
[4] Efficient query processingin geographic web search engines .2 Chen Y-Y,Suel T,Markowetz A. Proceedings of theSIGMOD . 2006

← 1 →