基于数据网格的书法字k近邻查询

基于数据网格的书法字k近邻查询 ISSN1000—9825.CODENRUXUEW JournalofSoftware,Vo1.17,No.II,November2006,PP.2289—2301 DOI:10.13600os172289 @2006byJournalofSoftware.Allrightsreserved. 基于数据网格的书法字k近邻查询 庄毅,庄越挺,吴飞 (浙江大学计算机科学与技术学院,浙江杭州310027) E—mail:jos@iscas.ac.cn Tel/Fax:+86—10.62562563 Answeringk-NNQueryofChineseCalligraphicCharacterBasedonDataGrid ZHUANGYi,ZHUANGYue-Ting,WUFei (CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China) +Correspondingauthor:Plan:+86?571-87951853,E?mall:zhuangyi@cs.zju.edu.cn,http:HWWW.zju.edu.cn ZhuangY,ZhuangYT,WuF.Answeringk-NNqueryofChinesecalligraphiccharacterbasedondatagrid. JournalD,Software,2006,17(11):2289-2301. Abstract:Inthispaper,anovelk-NearestNeighborf七一 NN)queryovertheChinesecalligraphiccharacter databasesbasedonDataGridisproposed.Firstwhenuserinthequerynodesubmitsaquerycharacterandk,the characterfilteringalgorithmisperformedusingthehybriddistancemetric(HDM)index.Thenthecandidate charactersaretransferredtotheexecutingnodesinapackagemode.Furthermore,therefinementprocessofthe candidatecharactersiSconductedinparallelismtogettlleanswerset.Finally,tlleanswersetiStransferredtotlle querynode.Ifthenumberofanswersetislessthank,thenthequeryprocedureisre-performedbyincreasingthe queryradiusuntiltheknearestneighborcharactersareobtained.Theanalysisandexperimentalresultsshowthat theperformanceofthealgorithmisgoodinminimizingtheresponsetimebydecreasingnetworktransfercostand increasingparallelismofI/OandCPU. Keywords:Chinesecalligraphiccharacter;k-nearestneighborquery;clusterhypersphere;datagrid 摘要:提出一种在数据网格环境下的书法字七近邻查询方法.当用户在查询结点提 交一个查询书法字和k时. 首先以一个较小的查询半径,在数据结点进行基于混合距离尺度的书法字过滤,然 后将过滤后的候选书法字以 "打包"传输的方式发送到执行结点,在执行结点并行地对这些候选书法字进行距 离(求精)运算,最终将结果书法 字返回到查询结点.当返回的书法字个数小于k时,扩大半径值,继续循环,直到得 到k个最近邻书法字为止.理论 分析和实验 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,该方法在减少网络通信开销,增加I/O和CPU并行,降低响应时间 方面具有较好的性能. 关键词:中文书法字;七近邻查询;类超球:数据网格 中图法分类号:TP391文献标识码:A 中国的悠久历史和灿烂文化留下了很多优秀的书法作品,如王羲之的《兰亭集序》 等.这些作品虽然可以 通过书名,作者,朝代名等元数据信息进行检索,但由于书法作品图像难以通过 OCR(opticalcharacter ?SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60533090( 国家自然科学基金);theNational ScienceFundofChinaforDistinguishedYoungScholarunderGrantNo.60525108(国家杰出青年基金):theChinaUSMillionBook DigitalLibraryProject(高等学校中英文图书数字化国际合作计划) Received2006?-06?-10;Accepted2006?-08?-25 2290JournalofSoftware软件Vo1.17,No.11,November2006 recognition)识别,因此无法根据书法字的内容进行高效检索.本文提出一种基于数据网格环境的书法字k近邻 (kNN)查询方法.为了充分利用网格中的资源,突出数据网格资源共享的特点,该算法把网格中性能较好的h个 结点作为高维查询执行的结点,并且采用书法字过滤,"打包"传输和流水线并行 机制 综治信访维稳工作机制反恐怖工作机制企业员工晋升机制公司员工晋升机制员工晋升机制图 来减少查询的响应时间. 同时,本文对该算法建立代价模型,并且说明各种参数对查询性能的影响.由于k-NN查询是通过嵌套调用范围 查询来完成的,当用户向数据结点发送一个查询请求时,首先利用基于混合距离索引对原始书法字集进行过滤, 以减少网络传输的代价,再将过滤后的候选书法字以"打包"传输的方式发送到若干个执行结点,并行地完成候 选书法字的求精(距离)运算.最后,将得到的结果书法字集发送回查询结点.这样就完成了一次高维书法字的范 围查询.当返回的候选书法字个数小于k时,再通过增大查询半径,的方式再次执行基于数据网格的范围查询, 直到满足条件为止.实验表明,该方法能够显着提高书法字检索的效率. 本文第1节回顾相关工作.第2节介绍书法字过滤及"打包"传输的方式.第3节提出网格环境下的k-NN查 询算法.第4节给出查询的代价模型.第5节通过实验从不同角度证明该算法的有效性.最后是 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 及对未来工 作的展望. 1相关工作 1.1手写体检索 本质上说,书法字是一种手写体.关于手写体的识别曾有很多研究,文献【1]回顾了在线和离线手写体识别的 主流技术,其中提到目前较为成功的手写体识别研究有对华盛顿手稿进行识别[2】,对希伯来语的书写体进行分 类【3】.然而,很少有文献介绍中文书法字的检索和索引方面的研究工作.文献【4]提出了一种古籍内容检索方法. 该方法通过多级计算古籍中汉字质心的方式,成功地对书写规范的古籍汉字进行了检索,然而,对于书写不规范 且来自不同朝代的书法作品,该方法难以奏效.本文采用轮廓来表示原始书法字,避免了上述问题. 1.2数据网格 在数据网格研究领域,美国和欧洲等国已经进行了广泛,深入的研究,并且推出了一些实验系统,其中最着 名的是欧洲数据网格项,美国的国际虚拟数据网格实验室IvDGL(IntemationalVirtualDataGrid Laboratory)项6】等.最着名的数据网格系统工具是Globus中的数据网格支撑模块和SDSC(SanDiego SupercomputerCentre)的SRB(storageresourcebroker)系统.到目前为止,数据网格环境下有关数据存储,访问和 传输的大多数工作,都是针对分布式文件系统的;同时,虽然目前对网格环境下的传统数据库查询进行了一定的 研究【1.8】,但是还很少有文献研究基于数据网格的书法字k近邻查询.在数据网格环境下,各结点高度自治并且异 构;所处理的数据一般都是海量数据;各结点之间的连接带宽不同,其传输速度可能会有很大的差异:网络环境 ,经常会出现结点之间连接不上以及连接中断的情况,这些都为基于数据网不稳定 格环境的书法字k近邻查询 提出了新的要求. 1.3高维索引 书法字索引属于高维索引范畴.高维索引技术经历了20多年的研究【,采用的技术主要分为3类.一类是以 R—tree[t01为代表的基于数据和空间分片的树形索引.可是,该树形索引方法只适合维数较低的情况,随着维数的 增加,其索引的性能往往比顺序检索要差,称为"维数灾难".另一类是以VA—file[…为代表的用近似方法表示多 维向量.尽管它通过对高维数据进行压缩和近似存储来加速顺序查找速度,然而,数据压缩和量化带来的信息丢 失使得其首次过滤后的查询精度并不令人满意.同时,尽管减少了磁盘的I/O次数,由于同时需要对位串解码进 行计算,导致CPU运算代价很高.由于书法字索引属于高维数据索引范畴,但与传统高维索引技术相比还是存在 较大不同:首先,每个字的轮廓采样点个数(维数)非常高(150维以上),使得传统多维索引技术(如 R.tree['.】,VA—file["】等)不能很好地支持高维书法字的快速检索;其次,由于书法字形的复杂程度不同,使得每个 书法字的采样点个数(维数)也不同,而传统高维索引技术只针对维数固定的数据而设计,很难直接应用于书法 字索引.而基于距离尺度的索引方法【l'】是一种有效的方法,因为它无须事先知道每个字的维数,只要采用文献 庄毅等:基于数据网格的书法字k近邻查询2291 f141中介绍的方法求得任意两个字的距离即可,这就是第三类高维索引方法.这类方法是通过将高维数据转化 为一维数据来进行高维查询,包括NB.Tree[】和iDistance[?】等,但是,这些方法都是采用单一尺度来过滤查询空 间,当维数很高时,其范围查询效率并不理想. 以上高维索引都是针对单机环境,JagadishI】等人提出了在P2P环境下的多维索引方法——vBI.Tree,但该 方法只是针对P2P环境而设计的,并不适合网格环境.到目前为止,很少有文献讨论网格环境下的k-NN查询,尤 其是书法字查询. 2相关知识 为了支持高效的基于数据网格的高维书法字的k-NN查询,本节分别介绍书法字过滤算法和"打包"传输技 术,以进一步缩小网络传输的代价,提高查询的并行性.首先,我们简单回顾文献【14】中介绍的基于形状的书法字 检索方法. 2.1基于形状的书法字检索 对于给定的书法字数据库{,,...,j,其中,表示第i个书法字,且f?【1,,l】.由于每个书法字形状复杂 程度不同,所提取的轮廓采样点个数也就不一样.设=,跏,,咖},表示第i个字有m个采样点,每个采样点 P由>两元组坐标构成,Jlj~[1,】, 由于书法字是表形的(如图1(a)所示),因此,利用采样轮廓点来表达书法字的形状,通过比较字形的相似性 来检索.由于原始的书法页面在切分过程中已经过去噪,二值化,因此轮廓提取就较为简单:直接找出黑白邻接 点即为轮廓点.一般而言,采用如图l(b)所示的极坐标比笛卡尔坐标能够更好地描述笔画的方向性.首先,将整个 空间从方向上划分出8个区域;然后,在弦上按log2r划分为4份.这样,整个空间就被分为32份(32bin), _(a)Anoriginalisolatedcalligraphiccharacterexample (a)一个已切分好的书法字 (b)Theextractionoffeaturepoints (b)特征点的提取 Fig,1TheContourPointcontextofcalligraphiccharacter 图1书法字轮廓点的表示 对轮廓上的一个给定点P,其属性用以Pf点为中心的坐标系的32bin中落入每个bin的像素点个数W( 来描述:wl<{卵f:qj~bin(k)},k=-O,l….,31,其中,g为落入第k个bin中的不同于Pj点的轮廓上的点.图t(6)ee 落入第25个bin的像素个数为5,即Wf(25)=5.在对样本字轮廓上的某一点mf,寻找候选书法字的中对应点ni时, 此两点满足如下不等式: dist=ED(f,,)=?(一Xj)+(一<length.(1) 其中ED(mi,)表示点m与点nj的欧式距离,length=32为归一化的像素方阵长度.在该约束下进行两个书法字的 形状相似度匹配:对样本字中的每一个点mf,在候选字中寻找匹配点n2.其中,Co=C(mf,)表示两点的近似匹配程 度大小,值越小则表明越相似. Co=C(mi,ny)=× k=0 2292JournalofSoftware软件Vo1.17,No.11,November2006 在两个字完全相同的极端情况下,可以找到精确的对应点,使得Co=C(m,nj)=O,即两个点完全匹配;否则, 该点的匹配值PMC按以下公式计算: PMC,--min{C(mi,hi)j=O,l,2….,}(3) 最后,两个书法字匹配值可以用它们的所有轮廓点匹配值的总和TMC来表示: TMC=?1(PMCI+o.1xED(pf,corresp(p)))(4) 2.2书法宇集过滤 定义1.数据网格(datagrid)~结点(node)和边(edge)构成,表示为G=NxNxE,其中?表示结点,E表示结点之 间的数据传输带宽. 定义2.数据网格中的结点分为查询结点,数据结点和执行结点,表示为+?,其中: 执行结点由h个子执行结点构成,表示第i个执行结点,且ie[1,hi. 如定义2所述,在网格环境中,结点在逻辑上分为查询结点,数据结点和执行结点.查询结点负责 提交用户的查询请求;数据结点负责书法字库及其索引的存储;^个执行结点负责接收来自数据结点的经过过 滤后的候选书法字,并行地执行求精(距离)运算,并将结果返回查询结点.由于书法字集存储在数据结点,对于任 意一个查询,不需要也没有必要将所有书法字都传输到执行结点进行距离运算.本节提出在数据结点通过混合 距离尺度索引快速地对书法字集进行过滤,从而有效地减少候选书法字集的网络传输代价. 2.2.1预备知识 给定两个书法字与,它们之间的相似距离用,)来表示,即,Vj)=TMC(Vi,).超球心Vq和半径r 所构成的超球可以表示为,r). 定义3(始点距离).给定两个维数相同的字和Iio,的始点距离(startdistance,简称SD)是与的距离, 记为)()=,),其中,中的每个采样点的坐标值都为0. 由于每个书法字字型的复杂程度不同,所提取的轮廓采样点个数也就不一样,这样得到的始点距离值显然 无法比较,需要对其作维数统一化处理.以下给出统一化始点距离(uniformstartdistance,简称USD)的概念, 定义4(统一化始点距离).给定字,的统一化始点距离表示为usD():D,其中di为字的维 d 数为统一化的维数. 假设个书法字通过层次聚类算法(如BIRCH【)得到T个类,对于任意一个类G(其中?[1,71),每个类中 书法字的个数表示为llll,且满足?::.1lcjll=. 定义5(类半径).对于任意一个类G,该类半径为其质心D,到该类中距离其最远的点的距离,记作cR,. 给定任意一个类及其类半径CR,,对应类超球表示为G,CRi). 定义6(质心距离).给定一个书法字,它的质心距离(centroiddistance,简称CD)为到其对应类G的质心 的距离,表示为cD()=d(Vi,),其中,?G,且?[1,71. 基于混合距离尺度(hybrid-distance—metric,简称HDM)的书法字过滤方法是基于以下3点提出来的:首先, 高维空间中,书法字之间的相似性可以通过该书法字与某个参考书法字的距离来度量和排序;第二,由于距离是 一 维值,可以使用B+树来对其建立索引;第三,单一基于质心【l或统一化始点距离尺度【l的书法字过滤方法很 难有效过滤不相关书法字,而基于质心和统一化始点距离的混合距离可以较为有效地缩小搜索空间,从而进一 步降低网络传输的代价. 2.2.2数据结构 首先通过层次聚类【1将个书法字聚成类,然后求得每个书法字的统一化始点距离和质心距离,这样,书 法字可以表示为一个四元组: ::(f,cid,USD,CD)(5) 其中,i为书法字的编号,cid表示该书法字所属类的编号. 庄毅等:基于数据网格的书法字k近邻查询2293 为了将书法字对应的USD和CD的信息都包含在该书法字的索引键值中,以便建立一个统一的索引来 更有效地过滤无关书法字,可以将其键值表达成如(6)式所示: key(V,)…LCD(B),J+(6) 其中,由于cD()为实数,因此,LCD(V3,表示对cD()四舍五入取到其小数点后第 of;t;c为一个足够大的常数, 用于~LCD(,进行线形扩展,得到大于1的整数.同时,由于USD(可能大于l,需要通过对其除以 MAX— USD进行归一化,使得其值小于l,其中,MAX— USD也为常数.这样就使得每个书法字对应的USD和CD 的值域不重叠. 2.2.3索引生成算法 HDM索引结构如图2所示,它由一张哈希表和个分片索引构成,其中为聚类个数.通过聚类,每个类超 球中的书法字采用一棵B+树建立索引,作为HDM的一个分片索引.T个类需要建立棵B+树,同时需要生成一 张哈希表来根据书法字所在类的编号快速地定位到对应的分片索引.一般采用最简单的一一对应的方式来完 成哈希映射,即其分片索引的编号由某一书法字所在类的编号来确定.该索引存储于网格中的数据结点. Fig.2TheindexarchitectureoftheHDM 图2HDM的索引框架 算法1.HDM索引创建. 输入:高维书法字集. 输出:高维索引bt(1ton. 1.采用BIRCH聚类算法将高维书法字聚成类: 2.forj:=1toTdo 3.bt(])<---newDMFile(j); 4.foreachcharacterinthe,.thclusterdo 5.计算该类中书法字的USD及CD; 6.()=c~LCD(V3,USD(~)/MAX— USD; 7.将Key(插入第j『棵B+tree; 8.endfar; 9.return6f(,) l0.endfor 2.3"打包"传输方式 当从一个结点向另一个结点传输数据时,采取"~(package)"传输方式可以极大地提高数据传输效率. 其 主要思想是:把需要传输的书法字"打"成若干"包",每个"包"包含若干个书法字,每次把一个包当成一个消息进 行传输,而不是把一个书法字当成一个消息进行传输. (1)基于"打包"的书法字传输方式,既可以减少每一次数据传输所要消耗的启动传输的代价,又可以减少 传输每个消息的头文件所耗费的代价. (2)基于"打包"的书法字传输方式具有很好的鲁棒性.如果传输失败,还能够恢复被中断的传输,即能够在 JournalofSoftware软件Vo1.17,No.11,November2006 最后一个被传输的包的开始位置恢复传输. (3)如果结点间每次传输一个书法字,那么网络上任意的延迟都会使接收数据的结点操作停止执行,而采 用"打包"传输方式,执行结点可以把接收到的包中的书法字进行缓存,当下一个"包"出现网络延迟时,就可以对 缓存中的书法字进行操作. 3网格环境下的k近邻查询算法 问题表述:从查询结点发出查询请求,要求对存储于数据结点心中的高维书法字集执行以查询书法字 的k近邻查询,将查询结果传输到. 网格是以资源共享为基础的协同计算环境,其中的任何资源,包括数据库,CPU,磁盘,设备等都可以被网 格中的任一用户使用.假设网格中存在h个具有更强的CPU处理能力和更快的网 络传输速度的结点, ?….,?,我们可以将它们作为精确匹配操作的执行结点,并行地完成距离(求精)计算,再把结果传输到发出 查询请求的结点.因此,本文提出了一种适用于数据网格环境的高维书法字k-NN查询算法.本质上,k近邻查 询是通过迭代执行范围查询完成的.因此,先从网格环境下的范围查询算法开始研究.假设通过预处理,已经建 立了用于书法字集快速过滤的HDM索引.当与查询超球,r】相交的类超球为t个(时,利用HDM索引得 到过滤后的候选书法字,利用散列函数对这t个相交的类超球中的候选高维书法字集进行散列,得到h个 桶,其中,.Ilf.然后采用流水线并行机制,把过滤后的书法字以"打包"方式传输到执行结点,?….,?,在这些 结点并行执行求精(距离)运算,最后把运算得到的结果书法字(记为")传输到查询结点. 该算法可以分为3个阶段,如图3所示. Answerset Fig.3Theworkflowofgrid-basedcharacterk-NNsearch 图3基于网格的书法字k-NN查询执行流程 (1)书法字过滤.在该阶段,首先在查询结点将用户的查询请求(即查询书法字及半径r的查询超球) 发送到数据结点?然后在该结点判断查询超球,r)与T个类超球是否相交,进而利用HDM索引对不相关 的书法字进行快速排除(过滤),从而有效减少将候选书法字集从数据结点发送至执行结点的网络传输代价.在 数据结点心为书法字集设置一个输入缓冲区馏1,再设置,个输出缓冲区OB1,用于缓存产生的候选书法字集 "的方式把候,当OBl中候选书法字集的大小等于一个传输包的大小时,就以"打包选书法字传输到对应的执 行结点. 算法2.书法字过滤(characterfilter). 输入:书法字集及查询超球,r】. 输出:被过滤后的候选书法字集(1to. 】.forf:=】tod0 2..fDf,CRf)intersectsZq,r)then 3.(i)<---Search(Zq,r,f); 4.将得到的(f)输出到输出缓冲区OB1; 5.elseifOi,cry)containsZq,then 6.(i)<---Search(Zq,r,f); 7.将得到的(f)输出到输出缓冲区OB1; 8.endloop; /?表示两个超球相交?/ /?表示类超球包含查询超球?/ 庄毅等:基于数据网格的书法字k近邻查询2295 9.endfor Search(,r,f)/在数据结点层面}/ 10.1eft~c~k*(G,0f)一r,+【uD()一r]/MAX—USD; l1.right~--cx[CRf,0.]+[USD(Vq)+r]/MAX_ USD; 12.S~-BRSearch[1efi,right, 13.return; 在算法2中,函数Search(Vq,r,f)具体执行并且返回范围查询在第i个分片索引上得到的候选书法字集(f). 需要说明的是,当查询超球与第f个类超球相交时,其对应的USD的查询范围为[USD(G)一r,USD(Vq)+r],而CD 的查询范围为tta(~q,0i)一r,oJICRf,oJ],这样,将两者结合就得到总的查询范围,如第10行,第ll行所 示;BRSearch(1eft,right,i)用于对第i个分片索引进行 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的B+树范围查询. (2)散列阶段.经过第1阶段的过滤,得到候选书法字集.同时,由于是由t个与,r)相交的类超球中 经过过滤后的书法字组成,令(,)表示与查询超球相交的第个类超球所对应的候选书法字集,且 ?:,(.,)--,O,其中?[1,.在开始散列操作之前,首先通过网格资源发现机制,得到h个与数据结点连接速率 最好的空闲执行结点,且h<t,然后,分别将候选书法字集(,)通过哈希映射并以"打包"方式发送至对应的执行 结点中,f?[1,.1l】.例如,将(1)传输到执行结点,并在该结点进行距离计算.同时,对子书法字集[2)进行过 滤处理,得到过滤结果(2)….,再把.11)的过滤结果(.11)传输到结点,并且在结点进行距离计算的同 时,对书法字集的第(斛1)个桶中的子书法字集n(h+O先进行过滤,得到过滤结果(斛1),这时就要查看到 中是否存在一个结点处于"闲置"状态:假设结点处于"闲置"状态,就把(斛1)传输到结点,并且进行 距离计算操作;如果不存在,就要等待到中的某一个结点可用为止. (3)求精阶段.将散列到各执行结点的候选书法字分别并行地计算与查询书法字的距离,将距离值小于 或等于r的书法字返回给查询发送结点,完成范围查询操作.具体步骤为:在执行结点,为候选子书法字集 (,)设置一个输入缓冲区tSq),MO')为候选子书法字集(,)在执行结点分配的内存空间,用于存储接收到的 f2(,)中的书法字;再设置一个输出缓冲区OBQ),用于缓存产生的结果书法字集.当OBq)O结果书法字集的大小 等于一个传输包的大小时,就以"包"的方式把结果书法字传输到发出查询请求的结点. 算法3.求精过滤(refinement). 输入:发送到某个执行结点的候选书法字(,),查询书法字及半径r. 输出:返回结果书法字"(『). 1."(,)卜; 2.if,)<rand?(,)then 3.将得到的结果书法字输出到输出缓冲区0(『); 4.endif 与范围查询不同的是:开始是用一个较小的半径去进行范围查询(第1行),当得到的候选字个数小于枷寸(第 3行),再重新增大查询半径(第4行).由于通过上述方法得到的候选书法字个数不一定正好为k个,可能会大于 H第10行),当遇到该情况时,需要进行(1ln"Il-1)次循环(第ll行),依次找到在该结果书法字集"中距离查询 字最远的(1ln"ll-k-1)个字(第12行),并将它们删除(第13行).这样,恰好得到k个最近邻书法字,其中:函数 CharacterFilter(Vq,r)为对Q进行以Vq为中心,r为半径的书法字过滤,如算法2所示;函数Refinement(O',,r)为 对进行以Vq为中心,r为半径的书法字求精,如算法3所示;函数Fa~hest(S,)用于返回候选书法字集S中与 距离最远的书法字.下面是整个k-NN查询的完整算法. 算法4.kNNSearch(Vq,曲. 输入:查询字Vq,k. 输出:查询结果. 2296JournalofSoftware软件Vo1.17,No.11,November2006 1.r卜0,卜,"卜;/初始化/ 2.发送查询请求到数据结点; 3.while(1l"II<k)/?当从执行结点返回的结果书法字个数小于k时,继续循环?/ 4.rr+r;/Ar很小,用于逐步增加半径值/ 5.利用资源管理机制在网格中找到h个性能较好的结点作为求精操作的执行结 点: 6.~--CharacterFilter(,r);/在数据结点完成书法字过滤/ 7.把中的候选书法字按照"打包"方式传输到h个执行结点: 8."*--Refinement(f2',,r);/在执行结点完成求精过滤/ 9.将f2"中的结果书法字按照"打包"方式发送到查询结点?口;/?第8步和第9步并行执行?/ 10.if(1l"II>七)then/当返回结果书法字"个数大于k时/ 11.forf:=1toll"ll一^_-1do 12.Vfar~""Farthest(.C2",; 13."卜"一,;/将,从结果书法字集"中删除/ 14.endfor 15.endif l6.endwhile 其中,第6步和第7步并行执行,因为过滤得到的候选书法字在发送至执行结点之前是先缓存于数据结点中的, 当缓存中的书法字个数达到传输包大小时,再将它们"打包"发送到对应的执行结点.同理,第8步和第9步也是 并行执行的. 4代价模型 由于k近邻查询是通过迭代调用范围查询来完成的,为简单起见,本节给出基于数据网格的范围查询的代 价模型.假设,l为书法字的总数表示B+树中每个节点的平均出度;为磁盘寻道时间;死为延迟时间;为数 据传输时间;为CPU进行一次判断所需的时间;为范围查询时1"3;fro,口,表示总查询时间. 在数据结点,当查询超球,r)--~f个类超球相交(7)时,如图4所示,第f个类超球中的书法字个数可近似 表示为 NUM(i):(旦:!! ?:.,((,c)) Fig.4Anexampleofcalligraphiccharacterfiltering 图4书法字过滤的例子 庄毅等:基于数据网格的书法字k近邻查询2297 同时,由于每个分片索引对应一棵B+树,因此,第i棵B+树(分片索引)的高度hi,每个节点的平均出度和元 素个数NUM(i)近似满足式(8). +1)=NUM(i)(8) fX(厂 求解式(8),得到该树的高度为 hi= llg(fI"I+1)l, 在数据结点上,对于第i个分片索引上的范围查询,整个查询分为两部分:首先是从根节点到叶节点,共访问 hi个节点;其次为在叶节点上的范围查询,该范围查询对应到第i个分片索引中,需要访问的书法字总数为 num(i)=雯:?::::: ?;roz(o(o:,""(10) 由于总共需要进行t次范围查询,因此,其总查询代价为 l[『1+l+『)]… 通过对书法字库(的过滤得到候选书法字集()之后需要对其进行散列,以便发送到执行结点进行距离 运算.散列操作的过程就是决定将这t组候选书法字发送到哪些执行结点,其I/O代价和判断所需的CPU代价 可以忽略. 定义7.从结点A向结点8传输一条消息的代价定义为TAB(X)=CO+CA×置其中表示结点A和结点B之 间的数据传输量;Co表示两结点间通信初始化一次所花费的时间,近似于一个常数,通常包括为消息的传递所做 的准备,通知目标结点它将会收到消息,处理目标结点的答复等等.通常情况下,网络的传输带宽是随时间变 化的,可以使用网络传输带宽的统计平均值.假设结点A和之间的网络传输率为一个常数,表示单位数据 传输所用的时间. 根据定义7可以得到,将候选书法字集()从数据结点传输至执行结点所需时间为 =×(c0+cDE×IPI)(12) 其中,表示每个包的大小,CDE表示数据结点?d到执行结点之间的网络传输率. 又因为对候选书法字集()的求精运算是在若干个执行结点并行计算的,因此其CPU代价Tcp,可表示为 Tceo=max{Tced1),Tcpv(2)….,Tcpf))(13) 其中,Tepv(O表示在第i个执行结点上的距离运算代价,且满足式(14). (f)=O(V—o, U—SD(一Vq)-r)nO(Vo,usD(G)一r))n0(0i,L(e(rq,01『)一r)'n(01『,LcR,,oJ) ?Vol(O(Oj,CRj))Xnx砭(14) 结果书法字(")从执行结点发送回查询结点所需时间可表示为 :×(Co+×lPI)(15) 其中:Irl表示返回查询结点的结果书法字个数,且IIVol(O(Vq,r)) ×;c表示从执行结点到发 送结点?0之间的网络传输率. 整个基于数据网格的范围查询的代价可以表示为 cl,0=z+z+1尸+z(16) 合并式(9),式(16)得到式(17),可以看出,该查询代价正比于书法字总数,且反比于索引平均出度. 2298JournalofSoftware软件Vo1.17,No.11,November2006 [(]_?哪小+max{Tced1),2),…,f)}+I-0"1×(C o+CEexlP1)(17) 5实验结果与分析 针对影响k-NN查询操作算法的各种参数,本文主要进行了3组模拟实验,实验结果表明,该算法在减少网络 通信开销,增加I/O和CPU并行,降低响应时间方面具有较好的性能,我们用C语言实现了基于混合距离尺 度的书法字过滤算法并将其部署在数据结点,该算法采用B+树作为单维索引结构且索引页大小设为4096字 节,所有实验的模拟运行环境为局域网.本文测试所用的书法字库【】来自中美百万册数字图书馆项目,它包含了 从书法库中提取了12000个预先切分好的书法字的轮廓点形状特征,每个特征点为一个二元组,包括X和Y的 坐标值, 5.1基于数据网格的书法宇检索 我们实现了一个基于数据网格的书法字检索系统,如图5所示.从切分好的书法作】中取12000个单字 "字为样本进行检索,前21个返回图像中有11个是正确的.做测试,以其中一个"天 查全率和查准率【?】是图像检 索领域中通用的衡量检索好坏的尺度,图6给出了对30个样本检索后的平均查全率和查准率曲线图.可以看出, 本文提出的"形状相似性方法"的效果要优于基于"推土机原理"t1以及"投影"【1方式. 天,Retrievalresult(rankedaccordingtOmatchingcost) 63.564.9 ?蠹一其一先68.568.969.869.970.370.7 68.4 ? 71.4 Fig,5Anretrievalexamplebasedonshape-similarity 图5采用形状相似性方法的一个检索例子 5.2传输速率对查询性能的影响 o.70 o.65 0.60 o.oo.2o.4o.6o.8 Recall Fig.6RecallVS.precision 图6查全率与查准率比较 1.0 第1组实验研究网络传输速率对k-NN查询性能的影响.假设查询结点与数据结点的速率为d.,数据 结点?d与执行结点之间的网络传输速度为,执行结点与查询结点?d之间的网络传输速度为以.实验中 采用有12000个书法字的数据库,用户从查询结点发送查询请求到数据结点的时间()远远小于将候选书法字 从数据结点传输到执行结点的时间()和将结果书法字从执行结点传输到查询结点的时间f).图7和图8中 的和盯分别表示候选书法字传输时间()和书法字传输时间()占总响应时间的百分比与传输速率之间的关 系.可以看出,在书法字总数一定的情况下,随着网络连接速度的增加,候选书法字及结果书法字传输时间占总 响应时间的百分比在逐步减少,但候选书法字传输时间比结果书法字传输时间要多,这是因为结果书法字是在 候选书法字的基础上,通过在执行结点的求精(距离)运算而得到的,其数据量较之候选书法字大为减少. ?舳 llOOOOO 皇.一?一u.1 庄毅等:基于数据网格的书法字七近邻查询 Transferrate(d2)(MB/s) Fig.7VS.transferrate 图7与传输速率 b 2299 l00200300400500600700800900l000 Transferrate(d3)(MB/s) Fig.8VS.transferrate 图8与传输速率 5.3书法字过滤对查询性能的影响 本次实验研究书法字过滤对k-NN查询性能的影响,方法1不进行书法字过滤:把书法字集直接从数据结 点M传输到执行结点M进行距离计算.方法2进行书法字过滤:利用书法字过滤算法把书法字集立滤为 后,再把传输到执行结点M进行距离计算.从图9可以看出,当七一定的情况下,经过过滤后的总查询响应时间 明显要优于未经过过滤的查询响应时间,且随着七的增加,两者的性能差别越来越大.这是由于过滤后的书法字 可以明显减少网络传输及距离计算的代价,同时基于索引的书法字过滤所需的时间远远小于网络传输的代价, 可以忽略不计. 一 g 口 bD 皇 皇 . 匕 o U k Fig.9Effectofcharacterfilteringonthequeryperformance 图9书法字过滤对查询性能的影响 5.4数据量,k和对性能加速比的影响 我们分别对k-NN?