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

第 35卷 第 11期 计 算 机 学 报 Vo_【35 NO．11 2012年 11月 CHINESEJOURNALOF COMPUTERS NOV．2012 空间数据上Top一 关键词模糊查询算法 胡 骏 范 举 李国良 陈姗姗 (清华大学计算机科学-b技术系数据库研究组 北京 100084) 摘 要 基于位置的服务(LBS)变得 日益普及 ，越来越多的研究开始关注如何对空间中的兴趣点 (POI)做有效的 检索．现有 的方法提 出了空间数据上的关键词检索，研究如何根据查询 的位置和关键词找到相关的POI点．然而， 现有方法主要对查询关键词进行精确匹配 ，不能支持模糊查询 ：当查询关键词与底层数据存在微小差异的时候 ， LBS系统不能返 回相关的结果．为 了满足移动用户 的模糊查询 需求 ，文 中对 空间数据上的 Top—k关键词模糊查询 问题进行研究 ：给定一组 POI点，检索与查询关键词近似匹配且空间上距离相近的 Top—k个结果 ．为 了提供高效的 模糊查询，文中首先定义了一种新型的相关性函数，综合考虑了文本相似性和空间距离，进而提出了一种有效的索 引结构RegionTrie，并基于RegionTrie设计了高效的Top—k算法．真实数据集上的实验结果表明，文中提出的Top一 算法十分高效 ，性能远好于对 比方法． 关键词 基于位置的服务 ；空 间数据上 的关键词检索 ；字符 串近似 匹配 中图法分类号 TP311 DOI号 ：10．3724／SP．J．1016．2012．02237 Top。kFuzzySpatialKeywordSearch HU Jun FAN Ju LIGuo—Liang CHEN Shan-Shan (DatabaseResearchGroup，DepartmentofComputerScienceandTechnology，TsinghuaUniversity，Beijing 100084) Abstract Location—BasedServices(LBS)havebecomemoreandmorepopularrecently．Existing LBS systemsemployaspatialkeywordsearchmethod toprovideservices．which findstherele— vantPOIsbyconsideringtextualrelevanceand spatialdistancewhen givenasetofpoints—of-in— terest(P0Is)．Existingmethodsonlyallow exactmatchesforquerykeywordsandfailtosupport fuzzysearch．Toprovideerror—tolerancesearchexperiences，westudythetop—kfuzzyspatialkey— wordsearch problem inthispaper：GivenasetofPOIsandaquerywithlocationandkeywords， wefindtherelevantPOIshavingsimilarkeywordswiththequery．Itcallsforefficientalgorithms toprovidereal—time search formobileusers．To addressthischallenge，we introduceanovel function to quantify therelevancebetween POIsand thequery，by considering the sim ilarity betweenkeywordsand spatialdistance．Then。wedevisean effective index structure．called