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

Top-k Fuzzy Spatial Keyword Search

作　　者：胡骏[1] 范举[1] 李国良[1] 陈姗姗[1] 

机构地区：[1]清华大学计算机科学与技术系数据库研究组,北京100084

出　　处：《计算机学报》2012年第11期2237-2246,共10页Chinese Journal of Computers

摘　　要：基于位置的服务(LBS)变得日益普及,越来越多的研究开始关注如何对空间中的兴趣点(POI)做有效的检索.现有的方法提出了空间数据上的关键词检索,研究如何根据查询的位置和关键词找到相关的POI点.然而,现有方法主要对查询关键词进行精确匹配,不能支持模糊查询:当查询关键词与底层数据存在微小差异的时候,LBS系统不能返回相关的结果.为了满足移动用户的模糊查询需求,文中对空间数据上的Top-k关键词模糊查询问题进行研究:给定一组POI点,检索与查询关键词近似匹配且空间上距离相近的Top-k个结果.为了提供高效的模糊查询,文中首先定义了一种新型的相关性函数,综合考虑了文本相似性和空间距离,进而提出了一种有效的索引结构RegionTrie,并基于RegionTrie设计了高效的Top-k算法.真实数据集上的实验结果表明,文中提出的Top-k算法十分高效,性能远好于对比方法.Location-Based Services （LBS） have become more and more popular recently. Existing LBS systems employ a spatial keyword search method to provide services, which finds the relevant POIs by considering textual relevance and spatial distance when given a set of points-of-in- terest （POIs）. Existing methods only allow exact matches for query keywords and fail to support fuzzy search. To provide error-tolerance search experiences, we study the top-k fuzzy spatial keyword search problem in this paper. Given a set of POIs and a query with location and keywords, we find the relevant POIs having similar keywords with the query. It calls for efficient algorithms to provide real-time search for mobile users. To address this challenge, we introduce a novel function to quantify the relevance between POIs and the query, by considering the similarity between keywords and spatial distance. Then, we devise an effective index structure, called RegionTrie to organize the POIs and develop efficient search algorithm based on the RegionTrie. We conducted experiments on real datasets, and the experimental results show that our algorithms achieve high performance.

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

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