中国科学技术大学学报JOURNALOFUNIVERSITYOFSCIENCEANDTECHNOLOGYOFCHINA第37卷第2期2007年2月Vol.37,No.2Feb.200:025322778(2007)02201472063基于位置的web搜索索引研究周英华,金培权,岳丽华,龚育昌摘要:针对基于位置的web搜索需要将网页中位置信息和文本信息相结合进行索引的应用需求,提出了先倒排表再R2tree索引和先R2tree再倒排表索引两种混合索引结构,同时处理文本和位置信息.大规模真实数据集上的实验表明,这两种方法在查询效率上明显优于已有的倒排表和R2tree相互独立的索引模式.关键词:基于位置的web搜索;位置索引;文本索引:TP391.1,TP311.12文献标识码:AResearchonindexoflocation2basedwebsearchZHOUYing2hua,JINPei2quan,YUELi2hua,GONGYu2chang(DepartmentofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230027,China)Abstract:Forlocation2basedwebsearch,geographicinformationshouldbeindexedwithtextualinformation.Twohybridindexstructureswereproposedtodealwithbothtextualandgeographicinformation:oneofinvertedfileprecedingtheR2treeandoneofR2treeprecedingtheinvertedfile.Experimentsonlargereal2worldwebdatasetsshowthattheproposedstructureshavebetterqueryperformancethantheexistingindexschemaofseparateinvertedfileandR2tree.于位置web搜索中的一个关键问题.最简单的方式是先用地名表示位置信息,建立类似文本的索引,然后利用关键词匹配的方式进行检索.这种方式忽略了基本的空间关系,不支持高级的空间查询,因此有必要设计出一种有效并兼顾考虑空间特征和文本特征的索引结构.这涉及两个关键问题:位置信息的表示和索引模式.相关研究已有一些成果[3～7].网页上有很多位置相关的信息,用来索引的只有大家认为与这个网页最相关的地理区域,即这个网页的地理范围(scope)[3].网页的地理范围可以通过分析网页的文本内容以及超链接的地理分0引言互联网中与位置相关的信息越来越普遍,统计表明,将近1/5web搜索的任务是与特定位置相关的[1,2],如“中关村附近的书店”等.越来越多的商业搜索引擎开始提供位置相关的服务,如本地搜索,本地广告和地图服务等.Google、百度等商业搜索引擎目前只提供基于黄页或其他付费列表的商业位置的搜索,本文针对更一般的、更具有普遍性的位置搜索,即搜索网页中与地理位置相关的内容.3收稿日期:2006201207;修回日期:2006204221基金项目:国家自然科学基金青年基金(604030200)资助.作者简介:周英华,女,1978年生,博士.研究方向:信息检索.E2mail:yhzhou@mail.ustc.edu.cn通讯作者:龚育昌教授E2mail:ycgong@ustceducn表1符号描述Tab.1Thedescriptionofsymbols到.为了支持空间语义,scope表示为两维的空间对象,考虑到表示的准确性和计算开销之间的平衡,用基于经纬度坐标的最小外接矩形(minimumboundingrectangle,MBR)表示一个地理区域.这些MBR可以用常见空间索引(如R2tree[4])有效地组织起来.因为一个网页的scope可能包含多个空间对象,所以本文将一个网页的scope表示为多个MBR.已有的索引模式可以分为两类.一是在文本检索结果的基础上再进行空间处理[5,6].这种方法的缺点是文本检索时只返回与文本特征最相关的网页,对于文本排名比较靠后的网页,其scope所包含的地理位置可能会被忽略,导致搜索结果不完整.二是在索引时同时集成文本和地理信息.文献[7]提出了倒排表和R2tree相互独立的索引结构,解决了第一类索引模式中的问题,但是在这种独立的索引结构中,每个网页在倒排表和R2tree结构中分别存储,两个独立结构中的网页列表都比较长,导致在磁盘读取和列表合并上消耗了较多的时间.本文提出了两种混合索引结构:先倒排表再R2tree索引,和先R2tree再倒排表索引.前者将倒排表中每个网页列表进行空间划分,划分的空间由R2tree进行索引;后者将所有的地理区域用一颗R2tree索引起来,然后对每个地理区域,找出scope包含这个区域的所有网页,再利用倒排表对这些网页符号描述MGKg(Q)PK(k)PM(m)PG(g)BListBR(x)TI/OTdiskTR(x)Tmg(地名辞典中MBR的数目数据集中geokeyword的数目词典中关键字的个数查询Q中涉及的geokeyword的个数...