书法推土机cpu

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
17,No.
11,November2006,pp.
22892301http://www.
jos.
org.
cnDOI:10.
1360/jos172289Tel/Fax:+86-10-625625632006byJournalofSoftware.
Allrightsreserved.
基于数据网格的书法字k近邻查询庄毅+,庄越挺,吴飞(浙江大学计算机科学与技术学院,浙江杭州310027)Answeringk-NNQueryofChineseCalligraphicCharacterBasedonDataGridZHUANGYi+,ZHUANGYue-Ting,WUFei(CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China)+Correspondingauthor:Phn:+86-571-87951853,E-mail:zhuangyi@cs.
zju.
edu.
cn,http://www.
zju.
edu.
cnZhuangY,ZhuangYT,WuF.
Answeringk-NNqueryofChinesecalligraphiccharacterbasedondatagrid.
JournalofSoftware,2006,17(11):22892301.
http://www.
jos.
org.
cn/1000-9825/17/2289.
htmAbstract:Inthispaper,anovelk-NearestNeighbor(k-NN)queryovertheChinesecalligraphiccharacterdatabasesbasedonDataGridisproposed.
Firstwhenuserinthequerynodesubmitsaquerycharacterandk,thecharacterfilteringalgorithmisperformedusingthehybriddistancemetric(HDM)index.
Thenthecandidatecharactersaretransferredtotheexecutingnodesinapackagemode.
Furthermore,therefinementprocessofthecandidatecharactersisconductedinparallelismtogettheanswerset.
Finally,theanswersetistransferredtothequerynode.
Ifthenumberofanswersetislessthank,thenthequeryprocedureisre-performedbyincreasingthequeryradiusuntiltheknearestneighborcharactersareobtained.
TheanalysisandexperimentalresultsshowthattheperformanceofthealgorithmisgoodinminimizingtheresponsetimebydecreasingnetworktransfercostandincreasingparallelismofI/OandCPU.
Keywords:Chinesecalligraphiccharacter;k-nearestneighborquery;clusterhypersphere;datagrid摘要:提出一种在数据网格环境下的书法字k近邻查询方法.
当用户在查询结点提交一个查询书法字和k时,首先以一个较小的查询半径,在数据结点进行基于混合距离尺度的书法字过滤,然后将过滤后的候选书法字以"打包"传输的方式发送到执行结点,在执行结点并行地对这些候选书法字进行距离(求精)运算,最终将结果书法字返回到查询结点.
当返回的书法字个数小于k时,扩大半径值,继续循环,直到得到k个最近邻书法字为止.
理论分析和实验表明,该方法在减少网络通信开销、增加I/O和CPU并行、降低响应时间方面具有较好的性能.
关键词:中文书法字;k近邻查询;类超球;数据网格中图法分类号:TP391文献标识码:A中国的悠久历史和灿烂文化留下了很多优秀的书法作品,如王羲之的《兰亭集序》等.
这些作品虽然可以通过书名、作者、朝代名等元数据信息进行检索,但由于书法作品图像难以通过OCR(opticalcharacterSupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
60533090(国家自然科学基金);theNationalScienceFundofChinaforDistinguishedYoungScholarunderGrantNo.
60525108(国家杰出青年基金);theChinaUSMillionBookDigitalLibraryProject(高等学校中英文图书数字化国际合作计划)Received2006-06-10;Accepted2006-08-252290JournalofSoftware软件学报Vol.
17,No.
11,November2006recognition)识别,因此无法根据书法字的内容进行高效检索.
本文提出一种基于数据网格环境的书法字k近邻(k-NN)查询方法.
为了充分利用网格中的资源,突出数据网格资源共享的特点,该算法把网格中性能较好的h个结点作为高维查询执行的结点,并且采用书法字过滤、"打包"传输和流水线并行机制来减少查询的响应时间.
同时,本文对该算法建立代价模型,并且说明各种参数对查询性能的影响.
由于k-NN查询是通过嵌套调用范围查询来完成的,当用户向数据结点发送一个查询请求时,首先利用基于混合距离索引对原始书法字集进行过滤,以减少网络传输的代价,再将过滤后的候选书法字以"打包"传输的方式发送到若干个执行结点,并行地完成候选书法字的求精(距离)运算.
最后,将得到的结果书法字集发送回查询结点.
这样就完成了一次高维书法字的范围查询.
当返回的候选书法字个数小于k时,再通过增大查询半径r的方式再次执行基于数据网格的范围查询,直到满足条件为止.
实验表明,该方法能够显著提高书法字检索的效率.
本文第1节回顾相关工作.
第2节介绍书法字过滤及"打包"传输的方式.
第3节提出网格环境下的k-NN查询算法.
第4节给出查询的代价模型.
第5节通过实验从不同角度证明该算法的有效性.
最后是总结及对未来工作的展望.
1相关工作1.
1手写体检索本质上说,书法字是一种手写体.
关于手写体的识别曾有很多研究,文献[1]回顾了在线和离线手写体识别的主流技术,其中提到目前较为成功的手写体识别研究有对华盛顿手稿进行识别[2]、对希伯来语的书写体进行分类[3].
然而,很少有文献介绍中文书法字的检索和索引方面的研究工作.
文献[4]提出了一种古籍内容检索方法.
该方法通过多级计算古籍中汉字质心的方式,成功地对书写规范的古籍汉字进行了检索,然而,对于书写不规范且来自不同朝代的书法作品,该方法难以奏效.
本文采用轮廓来表示原始书法字,避免了上述问题.
1.
2数据网格在数据网格研究领域,美国和欧洲等国已经进行了广泛、深入的研究,并且推出了一些实验系统,其中最著名的是欧洲数据网格项目[5]、美国的国际虚拟数据网格实验室IVDGL(InternationalVirtualDataGridLaboratory)项目[6]等.
最著名的数据网格系统工具是Globus中的数据网格支撑模块和SDSC(SanDiegoSupercomputerCentre)的SRB(storageresourcebroker)系统.
到目前为止,数据网格环境下有关数据存储、访问和传输的大多数工作,都是针对分布式文件系统的;同时,虽然目前对网格环境下的传统数据库查询进行了一定的研究[7,8],但是还很少有文献研究基于数据网格的书法字k近邻查询.
在数据网格环境下,各结点高度自治并且异构;所处理的数据一般都是海量数据;各结点之间的连接带宽不同,其传输速度可能会有很大的差异;网络环境不稳定,经常会出现结点之间连接不上以及连接中断的情况,这些都为基于数据网格环境的书法字k近邻查询提出了新的要求.
1.
3高维索引书法字索引属于高维索引范畴.
高维索引技术经历了20多年的研究[9],采用的技术主要分为3类.
一类是以R-tree[10]为代表的基于数据和空间分片的树形索引.
可是,该树形索引方法只适合维数较低的情况,随着维数的增加,其索引的性能往往比顺序检索要差,称为"维数灾难".
另一类是以VA-file[11]为代表的用近似方法表示多维向量.
尽管它通过对高维数据进行压缩和近似存储来加速顺序查找速度,然而,数据压缩和量化带来的信息丢失使得其首次过滤后的查询精度并不令人满意.
同时,尽管减少了磁盘的I/O次数,由于同时需要对位串解码进行计算,导致CPU运算代价很高.
由于书法字索引属于高维数据索引范畴,但与传统高维索引技术相比还是存在较大不同:首先,每个字的轮廓采样点个数(维数)非常高(150维以上),使得传统多维索引技术(如R-tree[10],VA-file[11]等)不能很好地支持高维书法字的快速检索;其次,由于书法字形的复杂程度不同,使得每个书法字的采样点个数(维数)也不同,而传统高维索引技术只针对维数固定的数据而设计,很难直接应用于书法字索引.
而基于距离尺度的索引方法[12,13]是一种有效的方法,因为它无须事先知道每个字的维数,只要采用文献庄毅等:基于数据网格的书法字k近邻查询2291[14]中介绍的方法求得任意两个字的距离即可.
这就是第三类高维索引方法.
这类方法是通过将高维数据转化为一维数据来进行高维查询,包括NB-Tree[12]和iDistance[13]等.
但是,这些方法都是采用单一尺度来过滤查询空间,当维数很高时,其范围查询效率并不理想.
以上高维索引都是针对单机环境,Jagadish[15]等人提出了在P2P环境下的多维索引方法——VBI-Tree,但该方法只是针对P2P环境而设计的,并不适合网格环境.
到目前为止,很少有文献讨论网格环境下的k-NN查询,尤其是书法字查询.
2相关知识为了支持高效的基于数据网格的高维书法字的k-NN查询,本节分别介绍书法字过滤算法和"打包"传输技术,以进一步缩小网络传输的代价,提高查询的并行性.
首先,我们简单回顾文献[14]中介绍的基于形状的书法字检索方法.
2.
1基于形状的书法字检索对于给定的书法字数据库={V1,V2,…,Vn},其中,Vi表示第i个书法字,且i∈[1,n].
由于每个书法字形状复杂程度不同,所提取的轮廓采样点个数也就不一样.
设Vi={pi1,pi2,…,pim},表示第i个字有m个采样点,每个采样点Pij由x,y两元组坐标构成,且j∈[1,m].
由于书法字是表形的(如图1(a)所示),因此,利用采样轮廓点来表达书法字的形状,通过比较字形的相似性来检索.
由于原始的书法页面在切分过程中已经过去噪、二值化,因此轮廓提取就较为简单:直接找出黑白邻接点即为轮廓点.
一般而言,采用如图1(b)所示的极坐标比笛卡尔坐标能够更好地描述笔画的方向性.
首先,将整个空间从方向上划分出8个区域;然后,在弦上按log2r划分为4份.
这样,整个空间就被分为32份(32bin).
Piwi(31)=28wi(25)=5(a)Anoriginalisolatedcalligraphiccharacterexample(a)一个已切分好的书法字(b)Theextractionoffeaturepoints(b)特征点的提取Fig.
1TheContourPointcontextofcalligraphiccharacter图1书法字轮廓点的表示对轮廓上的一个给定点pi,其属性用以pi点为中心的坐标系的32bin中落入每个bin的像素点个数wi(k)来描述:wi(k)=#{qj≠pi:qj∈bin(k)},k=0,1,…,31,其中,qj为落入第k个bin中的不同于pi点的轮廓上的点.
图1(b)中落入第25个bin的像素个数为5,即wi(25)=5.
在对样本字轮廓上的某一点mi,寻找候选书法字的中对应点nj时,此两点满足如下不等式:3)()(),(22lengthyyxxnmEDdistjijiji≤+==(1)其中ED(mi,nj)表示点mi与点nj的欧式距离,length=32为归一化的像素方阵长度.
在该约束下进行两个书法字的形状相似度匹配:对样本字中的每一个点mi,在候选字中寻找匹配点nj.
其中,Cij=C(mi,nj)表示两点的近似匹配程度大小,值越小则表明越相似.
∑=+*==3102)()()]()([21),(kjijijiijkwkwkwkwnmCC(2)2292JournalofSoftware软件学报Vol.
17,No.
11,November2006在两个字完全相同的极端情况下,可以找到精确的对应点qj,使得Cij=C(mi,nj)=0,即两个点完全匹配;否则,该点的匹配值PMCi按以下公式计算:PMCi=min{C(mi,nj):j=0,1,2,…,n}(3)最后,两个书法字匹配值可以用它们的所有轮廓点匹配值的总和TMC来表示:(4)∑=*+=niiiipcorresppEDPMCTMC1)))(,(1.
0(2.
2书法字集过滤定义1.
数据网格(datagrid)由结点(node)和边(edge)构成,表示为G=N*N*E,其中N表示结点,E表示结点之间的数据传输带宽.
定义2.
数据网格中的结点分为查询结点Nq、数据结点Nd和执行结点Ne,表示为N=Nq+Nd+Ne,其中:执行结点Ne由h个子执行结点构成,表示第i个执行结点,且i∈[1,h].
ieNieN如定义2所述,在网格环境中,结点在逻辑上分为查询结点Nq、数据结点Nd和执行结点Ne.
查询结点负责提交用户的查询请求;数据结点负责书法字库及其索引的存储;h个执行结点负责接收来自数据结点的经过过滤后的候选书法字,并行地执行求精(距离)运算,并将结果返回查询结点.
由于书法字集存储在数据结点,对于任意一个查询,不需要也没有必要将所有书法字都传输到执行结点进行距离运算.
本节提出在数据结点通过混合距离尺度索引快速地对书法字集进行过滤,从而有效地减少候选书法字集的网络传输代价.
2.
2.
1预备知识给定两个书法字Vi与Vj,它们之间的相似距离用d(Vi,Vj)来表示,即d(Vi,Vj)=TMC(Vi,Vj).
超球心Vq和半径r所构成的超球可以表示为Θ(Vq,r).
定义3(始点距离).
给定两个维数相同的字Vi和Vo,Vi的始点距离(startdistance,简称SD)是Vi与Vo的距离,记为SD(Vi)=d(Vi,Vo),其中,Vo中的每个采样点的坐标值都为0.
由于每个书法字字型的复杂程度不同,所提取的轮廓采样点个数也就不一样,这样得到的始点距离值显然无法比较,需要对其作维数统一化处理.
以下给出统一化始点距离(uniformstartdistance,简称USD)的概念.
定义4(统一化始点距离).
给定字Vi,Vi的统一化始点距离表示为DdVSDViii*=)()(USD,其中di为字Vi的维数,D为统一化的维数.
假设n个书法字通过层次聚类算法(如BIRCH[16])得到T个类,对于任意一个类Cj(其中j∈[1,T]),每个类中书法字的个数表示为||Cj||,且满足.
nCTjj=∑=1||||定义5(类半径).
对于任意一个类Cj,该类半径为其质心Oj到该类中距离其最远的点的距离,记作CRj.
给定任意一个类Cj及其类半径CRj,对应类超球表示为Θ(Cj,CRj).
定义6(质心距离).
给定一个书法字Vi,它的质心距离(centroiddistance,简称CD)为到其对应类Cj的质心Oj的距离,表示为CD(Vi)=d(Vi,Oj),其中,Vi∈Cj,且j∈[1,T].
基于混合距离尺度(hybrid-distance-metric,简称HDM)的书法字过滤方法是基于以下3点提出来的:首先,高维空间中,书法字之间的相似性可以通过该书法字与某个参考书法字的距离来度量和排序;第二,由于距离是一维值,可以使用B+树来对其建立索引;第三,单一基于质心[13]或统一化始点距离尺度[12]的书法字过滤方法很难有效过滤不相关书法字,而基于质心和统一化始点距离的混合距离可以较为有效地缩小搜索空间,从而进一步降低网络传输的代价.
2.
2.
2数据结构首先通过层次聚类[16]将n个书法字聚成T类,然后求得每个书法字的统一化始点距离和质心距离,这样,书法字Vi可以表示为一个四元组:Vi::=i,cid,USD,CD(5)其中,i为书法字Vi的编号,cid表示该书法字所属类的编号.
庄毅等:基于数据网格的书法字k近邻查询2293为了将书法字Vi对应的USD和CD的信息都包含在该书法字的索引键值中,以便建立一个统一的索引来更有效地过滤无关书法字,可以将其键值表达成如(6)式所示:USDVUSDVCDcVkeyiii_MAX)(),()(+*=θ(6)其中,由于CD(Vi)为实数,因此,CD(Vi),θ表示对CD(Vi)四舍五入取到其小数点后第θ位;c为一个足够大的常数,用于对CD(Vi),θ进行线形扩展,得到大于1的整数.
同时,由于USD(Vi)可能大于1,需要通过对其除以MAX_USD进行归一化,使得其值小于1,其中,MAX_USD也为常数.
这样就使得每个书法字对应的USD和CD的值域不重叠.
2.
2.
3索引生成算法HDM索引结构如图2所示,它由一张哈希表和T个分片索引构成,其中T为聚类个数.
通过聚类,每个类超球中的书法字采用一棵B+树建立索引,作为HDM的一个分片索引.
T个类需要建立T棵B+树,同时需要生成一张哈希表来根据书法字所在类的编号快速地定位到对应的分片索引.
一般采用最简单的一一对应的方式来完成哈希映射,即其分片索引的编号由某一书法字所在类的编号来确定.
该索引存储于网格中的数据结点.
HashtableSlicedindexesSindexT1Sindex1Sindex0B+treeB+treeB+treeFig.
2TheindexarchitectureoftheHDM图2HDM的索引框架算法1.
HDM索引创建.
输入:高维书法字集.
输出:高维索引bt(1toT).
1.
采用BIRCH聚类算法将高维书法字聚成T类;2.
forj:=1toTdo3.
bt(j)←newDMFile(j);4.
foreachcharacterinthej-thclusterdo5.
计算该类中书法字的USD及CD;6.
Key(Vi)=c*CD(Vi),θ+USD(Vi)/MAX_USD;7.
将Key(Vi)插入第j棵B+tree;8.
endfor;9.
returnbt(j)10.
endfor2.
3"打包"传输方式当从一个结点向另一个结点传输数据时,采取"打包(package)"传输方式可以极大地提高数据传输效率.
其主要思想是:把需要传输的书法字"打"成若干"包",每个"包"包含若干个书法字,每次把一个包当成一个消息进行传输,而不是把一个书法字当成一个消息进行传输.
(1)基于"打包"的书法字传输方式,既可以减少每一次数据传输所要消耗的启动传输的代价,又可以减少传输每个消息的头文件所耗费的代价.
(2)基于"打包"的书法字传输方式具有很好的鲁棒性.
如果传输失败,还能够恢复被中断的传输,即能够在2294JournalofSoftware软件学报Vol.
17,No.
11,November2006最后一个被传输的包的开始位置恢复传输.
(3)如果结点间每次传输一个书法字,那么网络上任意的延迟都会使接收数据的结点操作停止执行,而采用"打包"传输方式,执行结点可以把接收到的包中的书法字进行缓存,当下一个"包"出现网络延迟时,就可以对缓存中的书法字进行操作.
3网格环境下的k近邻查询算法问题表述:从查询结点Nq发出查询请求,要求对存储于数据结点Nd中的高维书法字集,执行以查询书法字Vq的k近邻查询,将查询结果传输到Nq.
网格是以资源共享为基础的协同计算环境,其中的任何资源,包括数据库、CPU、磁盘、设备等都可以被网格中的任一用户使用.
假设网格中存在h个具有更强的CPU处理能力和更快的网络传输速度的结点,,…,,我们可以将它们作为精确匹配操作的执行结点,并行地完成距离(求精)计算,再把结果传输到发出1eN2eNheN查询请求的结点Nq.
因此,本文提出了一种适用于数据网格环境的高维书法字k-NN查询算法.
本质上,k近邻查询是通过迭代执行范围查询完成的.
因此,先从网格环境下的范围查询算法开始研究.
假设通过预处理,已经建立了用于书法字集快速过滤的HDM索引.
当与查询超球Θ(Vq,r)相交的类超球为t个(t≤T)时,利用HDM索引得到过滤后的候选书法字′,利用散列函数对这t个相交的类超球中的候选高维书法字集′进行散列,得到h个桶,其中,h≤t.
然后采用流水线并行机制,把过滤后的书法字以"打包"方式传输到执行结点,,…,,在这些1eN2eNheN结点并行执行求精(距离)运算,最后把运算得到的结果书法字(记为″)传输到查询结点Nq.
该算法可以分为3个阶段,如图3所示.
AnswersetQueryrequestExecutelevelDatalevelQuerylevelHashmappingFig.
3Theworkflowofgrid-basedcharacterk-NNsearch图3基于网格的书法字k-NN查询执行流程(1)书法字过滤.
在该阶段,首先在查询结点Nq将用户的查询请求(即查询书法字Vq及半径r的查询超球)发送到数据结点Nd,然后在该结点判断查询超球Θ(Vq,r)与T个类超球是否相交,进而利用HDM索引对不相关的书法字进行快速排除(过滤),从而有效减少将候选书法字集从数据结点发送至执行结点的网络传输代价.
在数据结点Nd为书法字集设置一个输入缓冲区IB1,再设置一个输出缓冲区OB1,用于缓存产生的候选书法字集′,当OBl中候选书法字集的大小等于一个传输包的大小时,就以"打包"的方式把候选书法字传输到对应的执行结点Ne.
算法2.
书法字过滤(characterfilter).
输入:书法字集及查询超球Θ(Vq,r).
输出:被过滤后的候选书法字集′(1tot).
1.
fori:=1toTdo2.
ifΘ(Oi,CRi)intersectsΘ(Vq,r)then/*表示两个超球相交*/3.
′(i)←Search(Vq,r,i);4.
将得到的′(i)输出到输出缓冲区OB1;5.
elseifΘ(Oi,CRi)containsΘ(Vq,r)then/*表示类超球包含查询超球*/6.
′(i)←Search(Vq,r,i);7.
将得到的′(i)输出到输出缓冲区OB1;8.
endloop;庄毅等:基于数据网格的书法字k近邻查询22959.
endforSearch(Vq,r,i)/*在数据结点层面*/10.
left←c*d(Vq,Oi)r,θ+[USD(Vq)r]/MAX_USD;11.
right←c*CRi,θ+[USD(Vq)+r]/MAX_USD;12.
S←BRSearch[left,right,i];13.
returnS;在算法2中,函数Search(Vq,r,i)具体执行并且返回范围查询在第i个分片索引上得到的候选书法字集′(i).
需要说明的是,当查询超球与第i个类超球相交时,其对应的USD的查询范围为[USD(Vq)r,USD(Vq)+r],而CD的查询范围为[d(Vq,Oi)r,θ,CRi,θ],这样,将两者结合就得到总的查询范围,如第10行~第11行所示;BRSearch(left,right,i)用于对第i个分片索引进行标准的B+树范围查询.
(2)散列阶段.
经过第1阶段的过滤,得到候选书法字集′.
同时,由于′是由t个与Θ(Vq,r)相交的类超球中经过过滤后的书法字组成,令′(j)表示与查询超球相交的第j个类超球所对应的候选书法字集,且′=′∑=tjj1)(,其中,j∈[1,t].
在开始散列操作之前,首先通过网格资源发现机制,得到h个与数据结点连接速率最好的空闲执行结点,且h≤t,然后,分别将候选书法字集′(j)通过哈希映射并以"打包"方式发送至对应的执行结点中,i∈[1,h].
例如,将′(1)传输到执行结点,并在该结点进行距离计算.
同时,对子书法字集(2)进行过滤处理,得到过滤结果′(2),…,再把(h)的过滤结果′(h)传输到结点,并且在结点进行距离计算的同时,对书法字集的第(h+1)个桶中的子书法字集(h+1)先进行过滤,得到过滤结果′(h+1),这时就要查看到中是否存在一个结点处于"闲置"状态:假设结点处于"闲置"状态,就把′(h+1)传输到结点,并且进行距离计算操作;如果不存在,就要等待到中的某一个结点可用为止.
ieN1eNheNheNieNheNieNieNieNheN(3)求精阶段.
将散列到各执行结点的候选书法字分别并行地计算与查询书法字Vq的距离,将距离值小于或等于r的书法字返回给查询发送结点Nq,完成范围查询操作.
具体步骤为:在执行结点,为候选子书法字集′(j)设置一个输入缓冲区IB(j),M(j)为候选子书法字集′(j)在执行结点分配的内存空间,用于存储接收到的ieNieN′(j)中的书法字;再设置一个输出缓冲区OB(j),用于缓存产生的结果书法字集.
当OB(j)中结果书法字集的大小等于一个传输包的大小时,就以"包"的方式把结果书法字传输到发出查询请求的结点Nq.
算法3.
求精过滤(refinement).
输入:发送到某个执行结点的候选书法字′(j),查询书法字Vq及半径r.
输出:返回结果书法字″(j).
1.
″(j)←;2.
ifd(Vi,Vq)≤randVi∈′(j)then3.
将得到的结果书法字Vi输出到输出缓冲区OB(j);4.
endif与范围查询不同的是:开始是用一个较小的半径去进行范围查询(第1行),当得到的候选字个数小于k时(第3行),再重新增大查询半径(第4行).
由于通过上述方法得到的候选书法字个数不一定正好为k个,可能会大于k(第10行),当遇到该情况时,需要进行(||″||k1)次循环(第11行),依次找到在该结果书法字集″中距离查询字Vq最远的(||″||k1)个字(第12行),并将它们删除(第13行).
这样,恰好得到k个最近邻书法字,其中:函数CharacterFilter(Vq,r)为对进行以Vq为中心,r为半径的书法字过滤,如算法2所示;函数Refinement(′,Vq,r)为对′进行以Vq为中心,r为半径的书法字求精,如算法3所示;函数Farthest(S,Vq)用于返回候选书法字集S中与Vq距离最远的书法字.
下面是整个k-NN查询的完整算法.
算法4.
kNNSearch(Vq,k).
输入:查询字Vq,k.
输出:查询结果S.
2296JournalofSoftware软件学报Vol.
17,No.
11,November20061.
r←0,初始化*/2.
发送查询请求到数据结点Nd;3.
while(||″||k)then/*当返回结果书法字″个数大于k时*/11.
fori:=1to||″||k1do12.
Vfar←Farthest(″,Vq);13.
″←″Vfar;/*将Vfar从结果书法字集″中删除*/14.
endfor15.
endif16.
endwhile其中,第6步和第7步并行执行,因为过滤得到的候选书法字在发送至执行结点之前是先缓存于数据结点中的,当缓存中的书法字个数达到传输包大小时,再将它们"打包"发送到对应的执行结点.
同理,第8步和第9步也是并行执行的.
4代价模型由于k近邻查询是通过迭代调用范围查询来完成的,为简单起见,本节给出基于数据网格的范围查询的代价模型.
假设n为书法字的总数.
f表示B+树中每个节点的平均出度;TS为磁盘寻道时间;TL为延迟时间;TT为数据传输时间;TC为CPU进行一次判断所需的时间;TQuery为范围查询时间;TTotal表示总查询时间.
在数据结点,当查询超球Θ(Vq,r)与t个类超球相交(t≤T)时,如图4所示,第i个类超球中的书法字个数可近似表示为.
)),(()),(()(1nCROVolCROVoliNUMTjiiii*=∑=ΘΘrO4O3O2O1V0Fig.
4Anexampleofcalligraphiccharacterfiltering图4书法字过滤的例子庄毅等:基于数据网格的书法字k近邻查询2297同时,由于每个分片索引对应一棵B+树,因此,第i棵B+树(分片索引)的高度hi、每个节点的平均出度和元素个数NUM(i)近似满足式(8).
)(8)()1(1iNUMffih=+*求解式(8),得到该树的高度为1)1lg(lg)(lg++=ffiNUMhi(9)在数据结点上,对于第i个分片索引上的范围查询,整个查询分为两部分:首先是从根节点到叶节点,共访问hi个节点;其次为在叶节点上的范围查询,该范围查询对应到第i个分片索引中,需要访问的书法字总数为()()()()nCROVolCROrOVdOrVUSDVrVUSDVVolinumTjjjiiiqiqoqo*∩∩+∩=∑=1)),((,,),),((,))(,())(,()(ΘθΘθΘΘΘ(10)由于总共需要进行t次范围查询,因此,其总查询代价为∑=++*+++=tiTLSQueryTTTfinumffiNUMT1)()(1)1lg(lg)(lg(11)通过对书法字库()的过滤得到候选书法字集(′)之后需要对其进行散列,以便发送到执行结点进行距离运算.
散列操作的过程就是决定将这t组候选书法字发送到哪些执行结点,其I/O代价和判断所需的CPU代价可以忽略.
定义7.
从结点A向结点B传输一条消息的代价定义为TAB(X)=C0+CAB*X,其中,X表示结点A和结点B之间的数据传输量;C0表示两结点间通信初始化一次所花费的时间,近似于一个常数,通常包括为消息的传递所做的准备、通知目标结点它将会收到消息、处理目标结点的答复等等.
通常情况下,网络的传输带宽是随时间变化的,可以使用网络传输带宽的统计平均值.
假设结点A和B之间的网络传输率为一个常数CAB,表示单位数据传输所用的时间.
根据定义7可以得到,将候选书法字集(′)从数据结点传输至执行结点所需时间为|)|(||||PCCPTDEoTrans*+*′=(12)其中,|P|表示每个包的大小,CDE表示数据结点Nd到执行结点Ne之间的网络传输率.
又因为对候选书法字集(′)的求精运算是在若干个执行结点并行计算的,因此其CPU代价TCPU可表示为TCPU=max{TCPU(1),TCPU(2),…,TCPU(t)}(13)其中,TCPU(i)表示在第i个执行结点上的距离运算代价,且满足式(14).
()()()CTjjjiiiqiqoqoCPUTnCROVolCROrOVdOrVUSDVrVUSDVVoliT**∩∩∩=∑=1)),((,,),),((,)))(,())(,(()(ΘθΘθΘΘΘ(14)结果书法字(″)从执行结点发送回查询结点所需时间可表示为|)|(||||PCCPTEQoTrans*+*′′=′(15)其中:|″|表示返回查询结点的结果书法字个数,且nCROVolrVVolTjjjq*=′′∑=1)),(()),((|ΘΘ|;CEQ表示从执行结点Ne到发送结点Nq之间的网络传输率.
整个基于数据网格的范围查询的代价可以表示为TransCPUTransQuerytotalTTTTC′+++=(16)合并式(9)~式(16)得到式(17),可以看出,该查询代价正比于书法字总数,且反比于索引平均出度.
2298JournalofSoftware软件学报Vol.
17,No.
11,November2006+++*+++=∑=tiTLSTotalTTTfinumffiNUMT1)()(1)1lg(lg)(lg+*+*′+*|)|(||||PCCPTtDEocmax{TCPU(1),TCPU(2),…,TCPU(t)}+|)|(|||PCCPEQo*+*|′′(17)5实验结果与分析针对影响k-NN查询操作算法的各种参数,本文主要进行了3组模拟实验.
实验结果表明,该算法在减少网络通信开销、增加I/O和CPU并行、降低响应时间方面具有较好的性能.
我们用C语言实现了基于混合距离尺度的书法字过滤算法并将其部署在数据结点.
该算法采用B+树作为单维索引结构且索引页大小设为4096字节,所有实验的模拟运行环境为局域网.
本文测试所用的书法字库[17]来自中美百万册数字图书馆项目,它包含了从书法库中提取了12000个预先切分好的书法字的轮廓点形状特征,每个特征点为一个二元组,包括x和y的坐标值.
5.
1基于数据网格的书法字检索我们实现了一个基于数据网格的书法字检索系统,如图5所示.
从切分好的书法作品[17]中取12000个单字做测试,以其中一个"天"字为样本进行检索,前21个返回图像中有11个是正确的.
查全率和查准率[14]是图像检索领域中通用的衡量检索好坏的尺度.
图6给出了对30个样本检索后的平均查全率和查准率曲线图.
可以看出,本文提出的"形状相似性方法"的效果要优于基于"推土机原理"[18]以及"投影"[19]方式.
Recall1.
051.
000.
950.
900.
850.
800.
750.
700.
650.
600.
00.
20.
40.
60.
81.
0APCProjectingEMDPrecision68.
568.
969.
869.
970.
370.
771.
462.
263.
363.
564.
965.
167.
268.
445.
647.
652.
154.
356.
861.
262.
0Retrievalresult(rankedaccordingtomatchingcost)Query:Fig.
5Anretrievalexamplebasedonshape-similarity图5采用形状相似性方法的一个检索例子Fig.
6Recallvs.
precision图6查全率与查准率比较5.
2传输速率对查询性能的影响第1组实验研究网络传输速率对k-NN查询性能的影响.
假设查询结点Nq与数据结点Nd的速率为d1,数据结点Nd与执行结点Ne之间的网络传输速度为d2,执行结点Ne与查询结点Nq之间的网络传输速度为d3.
实验中采用有12000个书法字的数据库,用户从查询结点发送查询请求到数据结点的时间(T1)远远小于将候选书法字从数据结点传输到执行结点的时间(T2)和将结果书法字从执行结点传输到查询结点的时间(T3).
图7和图8中的δ和σ分别表示候选书法字传输时间(T2)和书法字传输时间(T3)占总响应时间的百分比与传输速率之间的关系.
可以看出,在书法字总数一定的情况下,随着网络连接速度的增加,候选书法字及结果书法字传输时间占总响应时间的百分比在逐步减少,但候选书法字传输时间比结果书法字传输时间要多,这是因为结果书法字是在候选书法字的基础上,通过在执行结点的求精(距离)运算而得到的,其数据量较之候选书法字大为减少.
庄毅等:基于数据网格的书法字k近邻查询22994060||=9000||=6000||=3000||=9000||=6000||=30005030σ(%)δ(%)4020301010020030040050060070080090010001002003004005006007008009001000Transferrate(d2)(MB/s)Transferrate(d3)(MB/s)Fig.
8σvs.
transferrate图8σ与传输速率Fig.
7δvs.
transferrate图7δ与传输速率5.
3书法字过滤对查询性能的影响本次实验研究书法字过滤对k-NN查询性能的影响.
方法1不进行书法字过滤:把书法字集直接从数据结点Nd传输到执行结点Ne进行距离计算.
方法2进行书法字过滤:利用书法字过滤算法把书法字集过滤为′后,再把′传输到执行结点Ne进行距离计算.
从图9可以看出,当k一定的情况下,经过过滤后的总查询响应时间明显要优于未经过过滤的查询响应时间,且随着k的增加,两者的性能差别越来越大.
这是由于过滤后的书法字可以明显减少网络传输及距离计算的代价,同时基于索引的书法字过滤所需的时间远远小于网络传输的代价,可以忽略不计.
CharacterfilteredNocharacterfiltered35302520151050Correspondingtime(s)1020304050kFig.
9Effectofcharacterfilteringonthequeryperformance图9书法字过滤对查询性能的影响5.
4数据量、k和T对性能加速比的影响我们分别对k-NN查询中的k及执行结点个数(h)对性能加速比做一个评估.
加速比表示为在单机上执行k-NN查询所需的时间与在网格环境执行相同k-NN查询的时间的比值.
从图10可以看出,随着数据量的增加,其查询加速比也随之提高.
当数据量为4200时,其加速比大于1.
这是因为对于数据量不大的基于网格的k-NN检索,其网络传输代价往往大于执行结点上的CPU距离计算代价,同时,由于书法字的相似匹配需要较高的CPU代价,因此当数据量达到一定程度时,网格的并行计算能力极大地加速了书法字的匹配速度.
从图中还可以2300JournalofSoftware软件学报Vol.
17,No.
11,November2006看出,并非数据量越大加速比就越高.
当书法字个数达到10000时,加速比的增长率减缓,这是因为大数据量所带来的网络传输代价会抵消并行计算所带来的系统性能的提升.
图11显示了k对其加速比的影响.
假定在书法字个数和执行结点个数一定的条件下,当k从10增加到50时,其对查询加速比的影响不是很大.
从图12可以看出,当执行结点个数(h)增加时,k-NN查询的性能加速比有所提高,但提高的幅度较为缓慢.
这是因为在执行结点个数增加的同时也增加了从数据结点发送到执行结点的代价,从而会抵消一部分性能的提高.
654321h1020304050Speedup54321Datasize200040006000800010000Speedup54321k1020304050SpeedupFig.
12hvs.
speedup图12h对加速比的影响Fig.
10Datasizevs.
speedup图10数据量对加速比的影响Fig.
11kvs.
speedup图11k对加速比的影响6总结与将来工作本文提出了一种基于数据网格的书法字k-NN查询算法.
该算法把网格中性能较好的h个结点作为查询执行的结点.
同时,采用基于混合距离尺度的书法字过滤、"打包"传输及流水线并行机制来减少查询的响应时间.
理论和实验结果表明,该k-NN算法在最小化网络通信开销和最大化I/O和CPU并行方面具有很好的性能,但是在网格环境下,该查询仍有大量尚未解决的问题,还有很多研究工作要做.
具体工作包括以下几个方面:1)在网格环境下,如果参与查询操作的高维书法字存在多个副本或者存在多个数据结点,如何将数据存储于这些结点从而增加操作的并行性;2)查询结果的缓存问题,即当一个数据库产生查询结果时,采用什么样的方式把结果进行缓存,使得以后的查询不用访问数据库就可以从缓存中得到所需要的查询结果.
References:[1]PalmondonR,SrihariSN.
On-Lineandoff-linehandwritingrecognition:Acomprehensivesurvey.
IEEETrans.
onPatternAnalysisandMachineIntelligence,2000,22(1):6384.
[2]RathTM,KaneS,LehmanA,PartridgeE,ManmathaR.
IndexingforadigitallibraryofGeorgeWashington'smanuscripts:Astudyofwordmatchingtechniques.
TechnicalReport,MM-36,Boston:UniversityofMassachusetts,2002.
[3]YosefIB,KedemK,DinsteinI,Beit-ArieM,EngelE.
Classificationofhebrewcalligraphichandwritingstyles:Preliminaryresults.
In:Proc.
ofthe1stInt'lWorkshoponDocumentImageAnalysisforLibraries.
PaloAlto,2004.
299305.
[4]ShiBL,ZhangL,WangY,ChenZF,Content-BasedChineseantiquebooksretrievalthroughvisualsimilaritycriteria.
JournalofSoftware,2001,12(9):13361342(inChinesewithEnglishabstract).
[5]SegalB.
Gridcomputing:TheEuropeandatagridproject.
In:Proc.
ofthe2000IEEENuclearScienceSymp.
andMedicalImagingConf.
Lyon,2000.
[6]HoschekW,Jaen-MartinezJ,SamarA,StockingerH,StockingerK.
Datamanagementinaninternationaldatagridproject.
In:Proc.
ofthe1stIEEE/ACMInt'lWorkshoponGridComputing.
Berlin:Springer-Verlag,2001.
1720.
[7]SmithJ,GounarisA,WatsonP,PatonNW,FernandesAAA,SakellariouR.
Distributedqueryprocessingonthegrid.
In:Proc.
ofthe3rdInt'lWorkshoponGridComputing.
Berlin:Springer-Verlag,2002.
279290.
[8]YangDH,LiJZ,ZhangWP.
Grid-Basedjoinoperation.
JournalofComputerResearchandDevelopment,2004,41(10):18481855(inChinesewithEnglishabstract).
[9]BhmC,BerchtoldS,KeimDA.
Searchinginhigh-dimensionalspaces:Indexstructuresforimprovingtheperformanceofmultimediadatabases.
ACMComputingSurveys,2001,33(3):322373.
庄毅等:基于数据网格的书法字k近邻查询2301[10]GuttmanA.
R-Tree:Adynamicindexstructureforspatialsearching.
In:YormarkB,ed.
Proc.
oftheACMSIGMODInt'lConf.
onManagementofData(SIGMOD'84).
Boston:ACMPress,1984.
4754.
[11]WeberR,SchekHJ,BlottS.
Aquantitativeanalysisandperformancestudyforsimilarity-searchmethodsinhigh-dimensionalspaces.
In:GuptaA,ShmueliO,WidomJ,eds.
Proc.
ofthe24thInt'lConf.
onVeryLargeDataBases(VLDB'98).
NewYork:MorganKaufmannPublishers,1998.
194205.
[12]FonsecaMJ,JorgeJA.
NB-Tree:Anindexingstructureforcontent-basedretrievalinlargedatabases.
In:Proc.
ofthe8thInt'lConf.
onDatabaseSystemsforAdvancedApplications.
Kyoto:IEEEComputerSociety,2003.
267274.
[13]JagadishHV,OoiBC,TanKL,YuC,ZhangR.
iDistance:AnadaptiveB+-treebasedindexingmethodfornearestneighborsearch.
ACMTrans.
onDataBaseSystems,2005,30(2):364397.
[14]ZhuangYT,ZhangXF,WuJQ,LuXQ.
RetrievalofChinesecalligraphiccharacterimage.
In:AizawaK,NakamuraY,SatohS,eds.
Proc.
ofthePacificRimConf.
onMultimedia(PCM2004).
Berlin,Heidelberg:Springer-Verlag,2004.
6384.
[15]JagadishHV,OoiBC,VuQH,ZhangR,ZhouAY.
VBI-Tree:Apeer-to-peerframeworkforsupportingmulti-dimensionalindexingschemes.
In:Proc.
ofthe22ndIEEEInt'lConf.
onDataEngineering(ICDE2004).
NewYork:IEEEComputerSocietyPress,2004.
[16]ZhangT,RamakrishnanR,LivnyM.
BIRCH:Anefficientdataclusteringmethodforverylargedatabases.
In:JagadishHV,MumickIS,eds.
Proc.
oftheACMSIGMODInt'lConf.
onManagementofData(SIGMOD'96).
NewYork:ACMPress,1996.
103114.
[17]Thecadalproject.
2006.
http://www.
cadal.
zju.
edu.
cn[18]CohenS,GuibasL.
Theearthmover'sdistanceundertransformationsets.
In:Proc.
oftheInt'lConf.
onComputerVision(ICCV'99).
NewYork:IEEEComputerSocietyPress,1999.
173187.
[19]WuYS,DingXQ.
TheRecognitionofChineseCharacter:Principle,ApproachandImplementation.
Beijing:HigherEducationPress,1992(inChinese).
附中文参考文献:[4]施伯乐,张亮,王勇,陈智锋.
基于视觉相似性的计算机古籍内容检索方法.
软件学报,2001,12(9):13361342.
[8]杨东华,李建中,张文平.
基于数据网格环境的连接操作算法.
计算机研究与发展,2004,41(10):18481855.
[19]吴佑寿,丁晓青.
汉字识别——原理、方法与实现.
北京:高等教育出版社,1992.
庄毅(1978-),男,浙江杭州人,博士生,主要研究领域为高维数据查询,网格计算和多媒体检索.
吴飞(1973-),男,博士,副教授,CCF高级会员,主要研究领域为多媒体检索,机器学习.
庄越挺(1965-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为多媒体检索,数字图书馆,视频动画.