《毕业论文（设计）SCBR 基于数据库模式展现数据库关键词检索结果.doc》由会员分享，可在线阅读，更多相关《毕业论文（设计）SCBR 基于数据库模式展现数据库关键词检索结果.doc（16页珍藏版）》请在三一办公上搜索。
1、ISSN 1000-9825, CODEN RUXUEWE-mail: josJournal of Software, Vol.19, No.2, February 2008, pp.323-337DOI: 10.3724/SP.J.1001.2008.00323Tel/Fax: +86-10-62562563 2008 by Journal of Software. All rights reserved.S-CBR:基于数据库模式展现数据库关键词检索结果*Supported by the National Natural Science Foundation of China under
2、Grant Nos.60473069, 60496325 (国家自然科学基金)Received 2007-04-02; Accepted 2007-07-17彭朝晖1,2,3+, 张 俊1,2,4, 王 珊1,21(中国人民大学 信息学院,北京 100872)2(教育部数据工程与知识工程重点实验室,北京 100872)3(山东大学 计算机科学与技术学院,山东 济南 250014)4(大连海事大学 计算机科学与技术学院,辽宁 大连 116026)S-CBR: Presenting Results of Keyword Search over Databases Based on Database
3、 SchemaPENG Zhao-Hui1,2,3+, ZHANG Jun1,2,4, WANG Shan1,21(School of Information, Renmin University of China, Beijing 100872, China)2(Key Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education of China, Beijing 100872, China)3(School of Computer Science and Technology, Shando
4、ng University, Jinan 250014, China)4(School of Computer Science and Technology, Dalian Maritime University, Dalian 116026, China)+ Corresponding author: E-mail: pengchPeng ZH, Zhang J, Wang S. S-CBR: Presenting results of keyword search over databases based on database schema. Journal of Software, 2
5、008,19(2):323-337. Abstract:In this paper, a result presentation method of keyword search over databases named S-CBR (schema-based classification, browsing and retrieving) which includes three phases of result classification, user browsing, and retrieving is proposed. Firstly, S-CBR uses database sc
6、hema and query keywords to produce the first-level classes automatically and classify results into them. For large classes, it further partitions them based on the content of keyword nodes. Furthermore, S-CBR gives each class a readable description, and presents the description and each result graph
7、ically to help users understand the results easily. Users also can retrieve the class which they are interested in based on the information of the first-level classes to find the results they need or acquire more relevant results. Experimental results verify the methods effectiveness and efficiency.
8、Key words:classification; result presentation; keyword search over database; database schema; heuristic search摘 要:提出一种基于数据库模式的数据库关键词检索结果展现方法S-CBR(schema-based classification, browsing and retrieving),包括结果分类、用户浏览和再次检索3个过程.S-CBR首先利用数据库模式和查询关键词自动产生第一级类别,将检索结果分配到各个类中;对于比较大的类,按关键词节点内容进行第二级分类;另外赋给每个类别一个类别
9、描述,并将类别描述和每个结果图形化地展现出来,使用户容易阅读和理解检索结果.用户还可以根据S-CBR提供的结果类别模式信息对感兴趣的类别作进一步检索,以尽快找到所需结果或获取更多的相关结果.实验证明了S-CBR方法的有效性.关键词:分类;结果展现;数据库关键词检索;数据库模式;启发式检索中图法分类号:TP311文献标识码: A关系数据库关键词检索(keyword search over relational databases,简称KSORD)使得普通用户能够使用关键词来检索关系数据库,而不需要了解数据库模式和SQL语言1,2.目前,关于KSORD已有许多研究工作,从实现机制上可分为基于数据图
10、的和基于模式图的两种.基于数据图的系统包括BANKS3,4,ObjectRank5, DETECTOR6,7等;基于模式图的系统包括DBXplore8,DISCOVER9,IR-Style10,SEEKER11,Hunter12等.各个KSORD系统对检索结果的定义有所差别:在ObjectRank系统中,检索结果被定义为单个元组,这个元组与查询相关但是不必包含查询关键词;而在DBXplorer,BANKS,DETECTOR,IR-Style等大多数系统中,每个检索结果必须包含查询关键词,通常,结果是来自多个关系的元组的连接(元组连接树).检索结果面临的一个重要问题是,如何改进系统的结果展现,使
11、用户能够迅速地理解结果,进而尽快找到所需的结果.KSORD结果展现并不是简单的问题1:一方面,系统检索结果是单个元组或多个元组构成的元组连接树,这种形式很不直观;另一方面,系统往往产生大量的结果,其中很多结果是相似的,尽管系统提供排序(rank)机制,但是排序的规则并不一定符合当前查询的需要,用户往往不容易从结果列表中发现自己所需的结果.进一步来说,好的结果展现应当不但能让用户读懂结果,还能主动提供一定的启发信息,帮助用户作进一步的查询.本文针对返回结果为元组连接树的KSORD系统,提出一种基于数据库模式的结果展现方法S-CBR (schema-based classification, br
12、owsing and retrieving).S-CBR采用按结构分类和按内容聚类相结合的方法,将检索结果组织成两级类别,有助于用户快速浏览结果.在此基础上,用户可以对某些感兴趣的类别做进一步的检索.与其他的KSORD结果组织方法相比,S-CBR是一种新的KSORD结果展现架构,其优点在于,使用户能够观察到可能的检索结果的全貌,给用户提供了启发信息,能够支持用户作进一步更深入的检索.本文第1节介绍本文所要用到的基本概念.第2节详细介绍S-CBR方法的体系结构和算法.第3节介绍实验评估结果.第4节介绍与本文相关的工作.第5节总结全文并提出未来工作.1 基本概念为便于描述问题,我们首先定义要用到的
13、基本概念,其中的定义1定义4基于文献3,12,并根据本文的需要作了少许修改.定义1(模式图). 一个关系数据库的模式可以表示为一个无向的模式图G(V,E),V是节点集,E是边集.其中,对于数据库中的每个关系R,G中有一个相对应的节点uRV;对于数据库中每一对关系R和S,如果R和S之间存在主外码联系,G中就包含一条无向边uR,uSE.图1所示为DBLP13数据库的模式图.DBLP数据库由Author,Paper,Write,Cites这4个关系组成,这几个关系之间存在着主外码联系,在模式图中,用阿拉伯数字表示边的序号.PaperIDTitleTypeAuthorIDNameAuthorIDPap
14、erIDCitingCited4321AuthorWritePaperCitesFig.1 DBLP database schema graph图1 DBLP数据库模式图定义2(数据图). 一个关系数据库的数据可以表示为一个无向带权的数据图GD(V,E),V是节点集,E是边集.其中,对于数据库中的每个元组t,GD有一个相对应的节点utV,本文中,我们对数据库中的元组和数据图中的节点不加区别;对于数据库中的每一对元组s和t,如果s和t之间存在主外码联系,GD中就包含一条无向边us,utE;GD中的每个节点和边被预先按照一定规则赋予一个权重3.定义3(关键词查询). 用户的一次输入被定义为一个关键
15、词查询Q,由一组关键词k1,kn组成(n1),表示为Q(k1,kn).若节点包含关键词作为其属性值的一部分,则称该节点和该关键词是相关的,并称该节点为关键词节点.通常,KSORD的第1步是利用RDBMS提供的全文索引,对每一个关键词ki确定与其相关的关键词节点集合Si.定义4(结果树). 关键词查询的一个结果是一棵有根无序的带权树(元组连接树),它是数据图的一个子图,包含每个Si中的至少1个节点,而且每个叶子节点必然是关键词节点.结果树的根称为信息节点,因为它将所有的关键词节点连接起来,并尽可能多地反映了关键词节点之间的关系.每棵结果树有一个相关性分数,它是根据各节点和各边的权重来计算的,结果
16、树应该按照相关性分数降序排列,系统返回用户所要求的Top-k结果树.例如,在DBLP数据库上,给定关键词查询(Hristidis,Papakonstantinou),KSORD系统将从DBLP的数据图中检索出Top-k结果树,每棵结果树其实是DBLP数据图的一个子图.图2给出了其中一棵结果树的示例,其含义是Hristidis和Papakonstantinou合作了一篇论文,论文题目是“Efficient IR-Style Keyword Search.”.TitleNamePaperIDVagelis HristidisEfficient IR-style keyword search1551
17、79Yannis PapakonstantinouAuthorIDAuthorID(root node)Author tupleAuthor tupleHristidisGP03HristidisGP03HristidisGP03PaperIDWrite tupleWrite tuplePaper tuple15517947694769Fig.2 A result tree of DBLP database (data subgraph)图2 DBLP数据库的结果树(数据子图)Fig.3 An example of result-tree-schema图3 结果树模式示例AuthorWrite
18、PaperWriteAuthor定义5(结果树模式). 利用数据库模式信息对结果树的节点和边作标号,即可得到结果树模式,它是一种有根无序的标号树.其标号采用如下两个规则:规则1(树节点标号). 假设节点t关系R,则t的标号为R.规则2(树边标号). 假设边t1,t2,其中,t1关系R1,t2关系R2,假定边所对应的外码和主码属性分别为R1的属性(A1, Ai,Ar)(1ir)和R2的属性(B1,Bi,Br)(1ir),则t1,t2的标号为(A1,Ai,Ar),(B1,Bi,Br).例如,图3即为图2结果树的结果树模式,为简化起见,图3中省略了边的标号,该结果树模式的含义是:两个作者合作写了一篇
19、论文.2 S-CBR方法我们首先要解决的问题是给出一种良好的组织结果树的方法,从而提高用户浏览结果的效率.大量的观察和实验证实14,许多结果树具有同样的结构,表达了相似的语义.例如在,DBLP数据库中,关键词查询(Jim Gray, Transaction)会产生很多结果,其中一些结果的含义是Jim Gray写了关于Transaction的论文,另一些结果的含义是Jim Gray的论文被关于Transaction的论文引用,还有一些结果是Jim Gray的论文引用了关于Transaction的论文.这样,将这些结果树按照结构的异同组织成不同的类别,对每个类别给出可读性好的类别描述,就有助于用户
20、快速浏览结果.对于每次查询,S-CBR方法首先从模式图出发,利用查询关键词信息,生成结果树模式,每个结果树模式代表一种结构(语义),作为一个类别,这样就形成了检索结果的第一级类别;然后,S-CBR将系统返回的Top-k结果按照结构的异同分配到第一级类别中,对于包含结果数量较大的类别,再按照各个结果树的关键词节点的内容异同作聚类,形成第二级类别;将这两级类别按照一定规则排序后,S-CBR将类别描述和每个结果用图形化的方式展现出来.在此基础上,用户可以对感兴趣的类别作进一步的检索.S-CBR方法的框架如图4所示.Clustering based on k1Clustering based on k
21、2Clustering based on knGroups whose sizethresholdA keyword queryExecute the queryNoNoNoYesYesFilter results based onthe specified classIs it retrieving again?Have found k results?The specified classResult treesRooted treesLabel the treesSelect root nodeTraverse the treesClassificationExpansionSelect
22、 root nodeTraverse the treesJudging relevanceRooted treesLabeled treesSchema graphThe first-level classes(set of result-tree-schemas)The second-levelclassesOutput inorderSelect a class and retrieve the query againKeywordsFind the needed results?FinishedStandard codesUser browsing resultsGroups whose
23、 sizethresholdGroups whose sizethresholdStandardcodesLabeled treesYesResult treesFig.4 Framework of S-CBR图4 S-CBR框架2.1 结果树和类别的匹配我们先介绍如何将一棵结果树分类到某一个类别中,然后在下一节介绍如何产生这些类别.我们知道,每次查询产生的结果树是一棵有根无序树,对它加标号之后得到的结果树模式是一种有根无序的标号树,我们采用判断树同构的方法实现结果树的分类.也就是说,若一棵树的结果树模式和一个类别(本身也是结果树模式)同构,则将这棵树分到这一类中,否则不属于这一类.这样,我们
24、就把结果分类问题转化为有根无序标号树的同构判断问题.下面介绍关于树同构的一些结论,包括定理1定理3的内容,其详细说明可参见文献12.定理1. 两棵有根有序标号树是同构的,当且仅当它们的先序遍历编码相等.定义6(标准编码). 设T是一棵有根无序标号树,从T派生的所有有根有序树为T1,T2,Tn,它们的先序遍历编码分别为S1,S2,Sn.我们称其中的最小编码Smin为T的标准编码.算法1. 生成标准编码(GetStandardCode算法).输入:有根无序标号树T的根节点root,特殊符号“#”和“$”(“#”“$”所有的标号).输出:T的标准编码St.Begin01 Stlabel(root)+
25、“$”; /“+”表示字符串连接,函数label获取节点或边的标号02 for 从root到其儿子的每条边e do03 St2label(e);04 获取e的另一个端点n;05 将St2+GetStandardCode(n)+“$”插入到集合S中;06 将S中的字符串按升序排列;07 for S中的每个串s do08 StSt+s;09 return St+“#”;End定理2. 算法1正确地计算了有根无序标号树T的标准编码.定理3. 两棵有根无序标号树是同构的,当且仅当它们的标准编码相等.由定理3可知,只要对结果树模式计算它们的标准编码,然后判断标准编码是否相同,就可以完成结果的分类.但是,
26、由于KSORD系统检索机制的原因,同一结构的不同结果树,它们的根可能是不对应的,这样会影响分类的正确性.例如,图5和图2的树不相同(两个作者合作的论文题目不同),但是具有相同的结构,都表示两个作者合作写一篇论文.然而,它们的根节点并不对应,这样,两棵树对应的结果树模式作为有根树就不是同构的.因此,我们需要重新确定每棵结果树的根,确保同一结构的树的根节点是对应的;同时,根节点还应该包含尽可能多的信息.显然,在图5中,结果树的根节点应为Paper Tuple.TitlePaperIDVagelis HristidisDISCOVER: Keyword search155179Yannis Papa
27、konstantinouAuthorID(root node)Author tupleAuthor tupleHristidisGP02HristidisGP02HristidisGP02Write tupleWrite tuplePaper tuple1551794769PaperIDAuthorIDNameFig.5 A result tree in the same pattern with the tree in Fig.2图5 与图2的结果树同结构的一棵结果树我们首先考虑选择度最大的节点,若满足条件的节点有多个,则从中选择最靠近树的中心的节点.通常,满足上述两个条件的候选节点只有1个
28、.如果这样的节点仍有多个,则分别以每个候选节点为根,采用算法1分别计算树的标准编码,选择产生最小标准编码的候选节点为根.如果有多个候选节点产生同样的最小标准编码,我们就可以选择其中任意一个作为根节点,因为它们产生同样的标准编码,对树同构的判断没有影响.2.2 类别生成S-CBR产生的第一级类别其实就是结果树模式.我们首先介绍结果树模式的生成,然后介绍它的排序.2.2.1 结果树模式生成S-CBR采用扩展的方法从模式图出发产生结果树模式.定义7(扩展). 在模式图G中,e是节点u和v之间的边,则称v是扩展u得到的,并称这个扩展使用了产生式uuev.将图1中DBLP模式图的4个关系Author,P
29、aper,Write,Cites简称为A,P,W,C,则可以生成的产生式集合是F=AA1W,WW1A,WW2P,PP2W,PP3C,CC3P,PP4C,CC4P.分别从模式图的每个节点出发,使用这些产生式可以扩展得到不同的结果树模式.图6给出了DBLP模式图上的6个结果树模式的示例以及从A节点开始生成它们的扩展步骤.AWAAAAAWWWWWWWWAAPPPP111111112111222(e)(f)(d)(a)(b)(c)Fig.6 The result-tree-schemas expanded from the schema graph图6 从模式图扩展产生的结果树模式算法2给出了生成结果
30、树模式的算法,其中,需要我们指定结果树模式的最大允许大小(节点个数)MaxSize作为程序结束的条件.算法2. 生成结果树模式.输入:模式图G,结果树模式最大允许大小MaxSize,关键词查询Q(k1,kn).输出:结果树模式集合PTSet.V:队列,存储等待扩展的无根树Z:队列,存储和V中元素相对应的有根树Begin01 for 模式图G中的每一个关系Ri,i=1,m do02 根据G生成产生式集合F;03 以Ri为根,生成单节点的无根树T,将T插入到V的队尾;04 由T生成有根树T,将T插入到Z的队尾;05 调用扩展算法Expand,获得部分结果树模式的集合PTSet1;06 将PTSet
31、1的元素加入到PTSet;07 从G中删除关系Ri;End算法2中调用了算法3,算法3使用无根树作为扩展的基础,每次扩展一条边,产生一棵新的无根树,然后使用第2.1节中的方法选定根节点,把它转化为有根树(结果树模式).对有根树计算其标准编码,然后判断它和队列中已经产生的树是否同构,若不同构,则把新产生的树加入到队列中.算法3. 树扩展(Expand算法).输入:队列V,Z,产生式集合F,结果树模式最大允许大小MaxSize,关键词查询Q(k1,kn).输出:部分结果树模式的集合PTSet1.Begin01 while V不为空 do02 取出V的队首元素U,取出Z的队首元素U;03 if Is
32、Relevant(U) then将U插入到PTSet1的队尾;04 if U的大小MaxSize then05 for U的每一个节点n do06 从F中获取n可以使用(符合规则3至规则5)的产生式集合F1;07for F1的每一个产生式f do08 从n出发利用f扩展一条边,形成一棵新树T;09 由T生成有根树T,调用算法1生成T的标准编码;10 if 和Z中每棵树的标准编码都不相同 then11 将T插入到Z的队尾,将T插入到V的队尾;12 从V中删除队首元素U,从Z中删除队首元素U;End需要注意的是,算法3使用产生式对每个节点作扩展时,选择的产生式必须满足以下3个规则,否则可能扩展出一
33、些无效的结果树模式.这些无效结果树模式不对应任何结果树.规则3. 在扩展节点R时,只能选用形如RReS的产生式.规则4. 若关系R和S之间存在“外码主码”联系,R是外码所在关系,S是主码所在关系,节点R是使用产生式SSeR扩展节点S得到的,则在扩展R时,不能选用产生式RReS.例如,关系W和A之间存在“外码主码”联系,W是外码所在关系,A是主码所在关系,在图6(e)中,节点A使用AA1W扩展出了节点W,节点W又使用WW1A扩展出一个新的节点A,这样得到的图6(e)是不能与任何结果树相对应的.假设存在一棵结果树与图6(e)相对应,这棵树对应节点W的元组为w关系W,对应两个节点A的元组为a1关系A
34、,a2关系A,那么,w的外码既是a1的主码又是a2的主码,因此,元组a1,a2的主码相同,它们是同一个元组,这在实际的结果树(数据子图)中是不可能出现的情况.所以,图6(e)是无效的结果树模式.规则5. 若关系R和S之间存在“外码主码”联系,R是外码所在关系,S是主码所在关系,则在扩展节点R时,产生式RReS最多只能选用一次.算法3中调用了算法4,算法4判断有根树队列Z中的结果树模式与当前查询的相关性,按照结果树的定义,叶子节点一定是关键词节点,如果结果树模式的叶子节点所对应的关系不包含当前查询的任何关键词,则该结果树模式与当前查询不相关.例如,假设我们在关系Write上不建立全文索引,则关系
35、Write的所有元组都不是关键词节点,图6(d)的叶子节点W对应的关系就不包含任何关键词,那么,图6(d)就与当前查询不相关.算法4. 结果树模式与关键词查询的相关性判断(IsRelevant算法).输入:结果树模式T,关键词查询Q(k1,kn).输出:T是否与当前查询Q相关.Begin01 for T的每一个节点n do02 if n是叶子节点 then03 if n所对应的关系的元组不包含任何关键词 then04 return false;05 return true;End定理4. 算法2能够从模式图G产生所有不大于MaxSize的与当前查询相关的不同构的有效结果树模式.S-CBR规定,
36、只有与当前查询相关的有效的结果树模式才可以作为第一级类别.定理4说明,算法2产生的结果树模式都可以作为第一级类别.结合第2.1节和文献12中的定理4.1,可以很容易地证明定理4.2.2.2 结果树模式排序作为第一级类别而产生的结果树模式,应当按照合理的顺序展现给用户.需要注意的是,一些结果树模式类别中可能不包含任何结果,其可能的原因有二:一种是数据库数据本身产生的结果树全都不具备这些模式;另一种是因为系统只返回Top-k结果,而这Top-k结果恰好都不具备这些模式.我们对结果树模式采用如下规则排序:(1) 将不包含任何结果的结果树模式都排在包含结果的结果树模式后面;(2) 对包含结果的模式,以
37、其包含结果的最大相关性分数作为该模式的分数,按此分数降序排列各模式;(3) 对不含结果的模式,按照它们的大小由小到大排列,结果树模式越小越排在前面(符合人们的阅读习惯).对于相同大小的结果树模式,我们提出如下打分机制对它们打分,按分数将其降序排列.对结果树模式的打分,需考虑其节点和边的权重.我们根据应用特征,预先给模式图的每个节点和边赋予一个权重,并将这个权重作为结果树模式对应节点和边的权重.节点的权重应反映该节点关系的重要程度,边的权重应反映关系间主外码联系的重要程度,节点和边的权重越大,它们的分数越高,结果树模式的分数也越高.假定节点u的权重表示为N(u),最大的节点权重为Nmax,则节点
38、u的分数为NScore(u)=log(1+N(u)/Nmax).假定边e的权重表示为W(e),最大的边权重为Wmax,则边e的分数为EScore(e)=log(1+W(e)/Wmax).结果树模式的分数是Score=eEScore(e)l+ uNScore(u)(1-l),其中,l是控制因子,它决定边和节点的分数在计算结果树模式分数时分别所起的作用大小.2.3 内容聚类在第一级分类之后,发现某些类别所包含的结果树仍然很多,考虑根据内容实现第二级分类.因为用户最敏感的是他们输入的查询关键词,所以,考虑根据关键词节点的内容来分类.各个关键词不能被同等看待,实际上,不同的关键词在数据库中有不同的出现
39、频率.例如查询(Gray,Database),Gray只出现在少数元组上,而Database出现在大量元组中.可以根据与低频率关键词相关的节点的内容异同来对结果数量超过阈值的第一级类别作进一步划分.在本例中,首先根据Gray分类,这样,与不同的Gray(如Jim Gray和W.A. Gray)相关的结果树就分离开了.用户只需检查每一个子类别的标签(Jim Gray)或(W.A. Gray),就能决定哪个子类是他们所感兴趣的.内容聚类的过程如图4所示,即首先将关键词根据其在数据库中的出现频率排序,出现频率等于与该关键词相关的关键词节点的个数,假定排序后的关键词顺序为k1,k2,.,kn.然后,我
40、们检查各类别的结果数目,对数目超过阈值的类别,首先按照关键词k1分组,即如果两棵结果树中与k1相关的节点的内容相同,则将这两棵树分为一组;否则,它们属于不同的组.若新产生的组的元素个数仍然大于阈值,我们将继续基于关键词k2分组,直到各组的元素个数都小于阈值或者所有的关键词使用完毕.需要说明的是,内容聚类产生的组都作为第二级类别.2.4 结果展现S-CBR采用图形化的用户接口将检索结果图示出来,使用Windows资源管理器的风格展示两级类别,如 图7所示.第2.2.2节已介绍了第一级类别的排序规则,第二级类别的排序是以其包含的结果的最大相关性分数作为本类别的分数,按分数降序排列.对于每一类中的结
41、果树,都按照它们的相关性分数降序排列.S-CBR对每个类别给出一个类别描述,第一级类别描述以图3所示的结果树模式为基础,二级类别描述即是产生该类时所依据的关键词的值.S-CBR将类别描述和每个结果都以直观的“树”的形式图示出来,当鼠标点击界面左侧的两级类别时,S-CBR在界面画板中图示该类的类别描述;当点击类中的树时,S-CBR在画板中图示所选择的结果树,例如,图7画板中显示的就是第7类结果的第3子类的第1棵结果树,表示Gray的合作者Raymond A. Lorie写了关于Database的论文.为了提高结果和类别描述的可读性,S-CBR在图示时做了一些工作:一是类描述和结果树都可以由系统管
42、理员为关系和属性名称配置别名,为边配置方向.这样,对用户隐藏了数据库的模式信息,展示的内容更接近自然语言;二是可以预先配置每个关系只选择部分属性在结果树中显示,以突出主要信息;三是每棵结果树按照其结果树模式的标准编码图示,这样,同类的结果树的图示结构相似,便于用户浏览.对于不包含结果的第一级类别,我们使用特殊符号(*)将其标出,例如图7中第10类之后的类都是空类别,用户可以对空类别再次进行检索.Fig.7 The result tree in GUI and the heuristic search interface图7 GUI中的结果树及启发式检索接口2.5 启发式检索系统返回的是Top-
43、k结果,然而,一个潜在的问题是,用户并不知道如何选择这个k值:如果k太小,则可能找不到需要的结果;如果k太大,则会检索出很多无用的结果,使用户感到疲倦.S-CBR方法的一个优点是根据模式图预先产生类别模式,将不包含结果的类别模式也显示出来,给用户提供了全局信息,使用户能够了解到可能的所有结果的结构(语义).这些类别模式(如图3所示)就是我们所说的启发信息,用户能够在此基础上作启发式检索.具体来说,对于空类别,用户可以双击该类别,系统对这一类再次检索,检索出来的Top-k结果全都属于这一类;对于非空的类别,也可用同样的方式再次检索,获取该类的更多结果.这样,用户开始检索时可以先用较小的k值,然后
44、根据反馈的启发信息再次查找,最终找到所需要的结果.这种启发式检索对于用户提交查询时不知道如何确定Top-k的k值这种情况非常有效.启发式检索的接口如图7所示.对于启发式检索的实现,我们采用了简单的结果过滤的方法,如图4所示,即只有与指定的类别相匹配的结果才允许返回给用户.这种实现方法的优点是在KSORD检索引擎的外部实现结果匹配,不需要修改KSORD内核,能够适用于多种KSORD系统.3 实验评估我们使用Java实现了结果分类系统,系统接收用户输入,传给KSORD系统;对于KSORD返回的结果,用户可以选择两种结果展现方式:List和S-CBR.List是传统的结果展现方法,只是简单地将结果按
45、相关性分数降序排列出来.我们的实验使用AMD844*4 CPU和4G内存的曙光服务器,操作系统是Windows 2000 Advanced Server,数据库使用Oracle9i,KSORD系统选用我们基于文献3实现的BANKS系统,通过JDBC连接Oracle9i.数据集采用DBLP真实数据的一个子集,所产生的数据图包括497 000个节点和567 000条边.我们在Author的Name属性,Paper的Title和Type属性上建立了全文索引.3.1 对参数MaxSize的评估MaxSize是S-CBR方法的一个重要参数,选择MaxSize的值需要综合考虑各种因素.在本节的每个实验中,我们都是随机产生100个查询,计算平均值.查询所用的关键词随机抽取自数据集,去掉了生僻和没有实际含义的词.3.1.1 MaxSize和第一级类别个数的关系一般来说,MaxSize越大,产生的结果树模式和第一级类别就越多.但是,因为只有与当前查询相关的结果树模式才能作为第一级类别,所以对于给定的MaxSize,第一级类别的个数还受到查询关键词的影响.图8给出了当MaxSize从5增长到10、关键词个数分别为25的关键词查询所产生的第一级类别的个数情况.可以看出,随着MaxSize的增多,第一级类别个数增
