元搜索引擎系统合成算法的约束条件 : 搜索引擎技术与新闻 --- dbk2008.com收...

元搜索引擎系统合成算法的约束条件
资料来源 ：网络资料
 
搜索引擎(search engine,简称SE)是一种基于关键字检索的因特网信息查询工具,其核心是一个排序系统.由于因特网上的信息量巨大,没有一个搜索引擎能够覆盖整个网络.为了获得所需的信息,人们有时不得不使用多个搜索引擎.而元搜索引擎(meta search engine,简称MSE)则是多个搜索引擎的集成,其工作过程可以归纳为如下6步:(1) 接受用户的原始查询;(2) 把原始查询分别转换为各个成员搜索引擎能够接受的形式;(3) 向成员搜索引擎发送查询;(4) 收集各个搜索引擎的原始查询结果;(5) 对原始查询结果进行合成,形成最终结果;(6) 把最终查询结果递交给用户.Metasearch, SavvySearch,Metacrawler,Profusion,Inquirus和MetaGer等是一些有代表性的元搜索引擎系统.
从元搜索引擎的工作原理可以看出,查询结果合成是一个十分重要的环节.由于搜索引擎查询结果的规模常常比较庞大,而用户又通常缺乏足够的耐心、精力和时间去遍历所有的命中文档,他们一般只会检查前几条或几十条信息,因此,最终查询结果中各个项目的排列顺序是至关重要的.
查询结果合成在分布式信息检索系统中得到了广泛的关注,人们提出了许多种合成方法.在文献[1]中,J.P. Callan等人针对不同的情况给出了4种典型的合成算法.(1) 如果只有文档的原始顺序是已知的,则可以采用间隔排列合成法:首先把每个查询结果中的第1项交叉列出,然后再把各个查询结果中的第2项交叉列出,依此类推.(2) 如果可以得到文档的原始相关性分值,那么当这些分值可以直接比较时,则可以采用原始分值合成法:直接依据每个文档的原始相关性分值决定其合成排列次序.(3) 如果文档的原始分值不能直接比较,则可以通过对idf(倒排文档频率)等进行标准化来得到规范的相关性分值,并以之为根据确定文档的合成排列次序(规范分值合成).(4) 加权分值法:首先计算出各个信息源相应于查询条件的重要性,再以此为权乘上文档的相关性分值作为决定其合成排列次序的根据.
在文献[2]中,Kirsch给出了另一类典型的合成方法.这种方法要求对下层搜索引擎进行一些修改,以便返回诸如各个搜索项在文档中出现的次数和在整个数据库中出现的次数等额外信息.元搜索引擎则利用这些信息在客户端重新计算文档的相关性,并依此为根据决定文档的最终排列顺序.
实际的元搜索引擎系统所使用的合成方法是各种各样的.Metacrawler[3]引入概念可信度来决定文档与查询的相关程度.Metacrawler把可信度的取值范围限定在0~100 0之间.每个搜索引擎查询结果中第1项的可信度初值为1 000,第2项的可信度初值为999,依次递减.重复出现文档的可信度等于其所有初值之和.从本质上看,Metacrawler的合成策略允许各个搜索引擎就最终结果中文档的排列顺序进行投票,被多个搜索引擎选中的文档更有可能排在只被一个搜索引擎选中的文档前面.
Profusion[4]的合成算法其实就是规范分值法和加权分值法的一种集成.它由3个步骤组成:首先把搜索引擎给出的文档与查询之间的(原始)相关值规范映射到[0,1],然后把规范分值乘上搜索引擎的权,最后如果有重复出现的文档,则取其中的最大值作为文档的(最终)相关值.SavvySearch[5]的合成方法就是规范分值法,重复出现的文档则以其相关性分值之和作为排序的依据.
Inquirus[6]采用了客户端重新计算文档相关性的合成策略.与Kirsch不同,Inquirus首先对搜索引擎查询结果中的文档进行下载,然后再在客户端独立计算文档与查询之间的相关性.
虽然合成问题在MSE系统和其他分布式信息检索系统中得到了广泛的关注,但是,有一个关于合成的基本问题却从来没有被明确地讨论过即一个合理的合成算法需要满足的必要条件或基本限制.在分布式专家系统中,合成的类型、策略和约束等问题已经得到了较好的研究[7].而在分布式信息检索系统中却没有一个明确的算法合理性概念,也没有一个能够从理论上保证算法合理性的准则.
本文将集中讨论一个合理的MSE合成策略必须满足的约束条件.第1节给出MSE合成问题的形式化定义.在第3节中,将给出合成策略必须满足的一般性约束条件和在特定情况下应该满足的特殊约束条件.最后总结全文并给出今后工作的简单展望.
References:
[1] Callan, J.P., Lu, Z., Croft, W.B. Searching distributed collections with inference networks. In: Fox, E.A., Ingwersen, P., Fidel, R., eds. Proceedings of the 18th International Conference on Research and Development in Information Retrieval. ACM Press, 1995. 21~28.
[2] Kirsch, S.T. Document retrieval over networks wherein ranking and relevance scores are computed at the client for multiple database documents. United States Patent #5,659,732, 1997.
[3] Selberg, E.W. Towards comprehensive web search [Ph.D. Thesis]. University of Washington, 1999.
[4] Gauch, S., Wang, G., Gomez, M. Profusion: intelligent fusion from multiple, distributed search engines. Journal of Universal Computer Science, 1996,2(9):637~649.
[5] Lorence, S., Giles, C.L. Inquirus, the NECI meta search engine. Computer Networks and ISDN Systems, 1998,(30):95~105.
[6] Howe, A.E., Dreilinger, D. SavvySearch: a meta-search engine that learns which search engine to query. ACM Transactions on Information Systems, 1997,3(15):195~222.
[7] Zhang, M., Zhang, C. Potential cases, methodologies, and strategies of synthesis of solutions in distributed expert systems. IEEE Transactions on Knowledge and Database Engineering, 1999,3(11):498~503.
http://www.dmresearch.net/uploads/20060101/1000000007.pdf