论文研究 RRTA:一种基于顺序读取的有效Top K查询算法.pdf

Top-K查询是一种被广泛应用的操作，它根据给定的评分函数在潜在的海量数据中返回k个分值最高的元组。传统的TA算法要求能够支持随机读，NRA算法虽然放宽了对随机读的限制，但是增长阶段需要在内存中维护大量的元组，运行时将占用大量的内存资源。提出的RRTA算法相比NRA算法对数据的存储进行了重新的规划，创建一个新的表将内存上的开销转换到较廉价的外存开销，只需顺序读取就可以进行有效的Top-K查询，同时将表进行了划分，在并行处理的情况下更能提高程序的效率，能够很好地运行在内存有限的环境中。l18013,49(17)Computer Engineering and4 pplications计算机工程与应用划分完成以后.可以对7进一步进行压缩,压缩后的T1只元组所在列文件集合LS中每个属性A1出现的行号值存储行数值ROW取值为每个了表的下一相邻了表的MUM44≤i≤m)组成,形如表8MIN(RO)-1的记录,并∏侏留最后一糸记录,同时增加表8由表1和表5,表6生成个属性列NUM表示划分表的编号,这时行号ROW也可以删除,此处保留是为了方便之后的证明,形如表7。NUMAIUMA5表5由表4划分的子表1表6由表4划分的子表2RDRID0.930.50.40.80.60.654以下的讨论只是针对局部的数据有改动的时候,也就表7由表5和表6生成是大部分数据保持不变。首先需要说明的是表T反映的NUMROM是整体数据集在属性列A(1≤≤m)上属性值的一个趋势当只是局部的数据有改动的时侯,并不会影响整体数据集50.3在每个属性列上属性值的整体趋势,也就无需对表进行32RRTA算法重新规划和修改,仍然能够使用表T1来进行阙值的计算设一共划分了A个長,1个线程 thread o读取長r并但是当大部分数据有改动的时候,T就无法正确地反映整计算r,B(≤B≤A个线程 thread i(≤i≤B读取划分的表体数据集在属性列A(1≤i≤m)上属性值的一个趋势,影响并计算各自的1pK國值τ的计算,进而降低查询的效率,就要重新规划表7(1)设定总体的mpKa、PO和z以及循环的次数和72cOm,并且初始化 epk all, P和t、 count o(1)不调整存储位置(2)如果Pam≥r程序结束。否则,对B个线程读取某一元组的属性值改变,更新表乃3中对应记录后仍满足A个表中剩下未读取过的B个编号最小的表,且 thread i不等式:MIN(ROW)≤MIN(NUMA)(≤≤m)≤MAX(RO)读取的表的编号小于 thread i+1,分别计算各自的 topk i。(ROW为该元组所在子表原先删除属性列的值,可以事先(3) thread(≤i≤B)读取完毕后,将自己的 zopE i合存储下每个子表的MIN(ROW)和MAX(ROW)),那么只并到 topK al中(合并时采取留大弃小的原则,即 topk all要更新表72中该元组的属性值无需调整元组的存储位置中最终的结果为 tonk i和 topk all中总体的k个最大(2)调整存储位置值),则该线程本次循环的任务结束①1某一元组的属性值改变,更新表73中对应记永后不满足(4)bad0读取表T中表编号MM为 Bx count id不等式MN(RO) MIN(, (Iism)≤M4x(RO)录的属性值然后使x等丁计算出的评价函数值, lA0从2子表中先删除元组原先的的记录,然后将更新的后记的本次循环的任务结束。录插入到满足上面不等式的72的子表中,再更新表73。(5)如果所有线程在本次循环的任务结束, count加1②删除一个元组:直接朋除72子表和表T3中元组对返回步骡(2),否则完成本次循环任务的线程等待未完成应的记录。的线稈。③增加一个新的元组:根据列文件集合LS先计算出元组在表T屮对应的属性值(NUMA,取值为列文件L,的4RRTA算法的性能分析和评价记录中A属性值大于等于该元组A,属性值的行号的最小4.1与TA比较值),然后将元组的信息添加到满足不等式MIN(ROW)≤RRTA相比于TA算法,建立了表T,以后可以省去 TA MIN(MM4)(≤≤m)≤MAX(ROW)的T2子表中,再更新中的重复计算,因为TA算法没有记录先前已经计算过评表73。如果新增数据集相对较多,可以考虑对新增的数据价函数值的元组,所以每次碰到一个元组的时候都是进行集进行规划,最后对两部分的结果进行合并。此时对新增次计算,这当然就有一些元组进行了重复的无用计算数据集建立对应的表TT2可以不破坏原有的数据集规但是建立这个表以后就可以省去这些没有必要的重复计划,并且相比对原有数据规划修改代价可能更小(需要说算,因为表72中没有任何两个元组标识符是相同的。但是明的是新增元组不属于原有数据集的改动,在此列出是为这也带来一些副作用,当有局部的数据修改后,需要对已了尽可能地包含现实中可能地情况并提出相应的解决办法)经规划好的表T、7,重新规划,下面对此进行讨论由以上的分析也可以看出RRTA适用于原有数据集变为了维护已经规划好的表71、T2需要建立一张表73,动相对较小的场合,因为频繁的数据变动将会增加维护的由元组属性标识符RD、元组所在T2了表的编号UM和代价。TA是建立在支持随机读的基础之的RRTA是为周腾腾,陈林祥,胡奥:RRTA:一种基于顺序读取的有效Top-K查询算法2013,49(17)119了解决随机读受限而提出一个解决方案,但是RRTA同样NRA算法的读取效率(令B>m)。叮以用在支持随机读的场合,因为可以从RRTA的算法中6)程序的并行性:RRTA算法的B+1个线程的独立看出RRTA就是用顺序读取表T2来代替TA算法屮随机性较高,只有当读完一个划分子表后才进行一次同步,除读取列文件的,因此RTA算法同TA算法相比,它们的效此之外各个线程之间是完全独立的,这样各个线程之间异率是同一数量级的。步性较高,降低了各个线程之间的制约。而NRA算法何次42与NRA比较计算阈值τ的时候都要进行同步,各个线程之问的独立性下面从以下几个方面进行分析(其中分析(3)、(4)需较羽要建立在T2了表相比r2很小的基础上上面就不同的方面对RRTA和NRA进行了比较,从中(1)内存的占用:NRA在增长阶段因为要维护遇到的叮以看出RRTA相对NRA的明显优势,因此基本可以断定在实践中RRTA的效率优于NRA。综合RRTA同TA、NRA元组信息,所以在处理海量数据的时候需要占用大量的内的比较可以发现,RRTA适用于短期内数据集变动较小且存,以至于无法装下这些信息。但是RRTA从需固定的内内存有限的场合。存来维护几个优先队列和一些中问数据,内存的占用相对同定而且很少(2)计算量NRA在执行过程中需要史新元组评价函5实验数据和行为分析下面的实验数据给出RRTA的一些性能表现。实验使数值的上下界,海量数据决定了这个计算量相当可观。而用的是Java来编写的RRTA程序,jdk版本为jdkl.6.002,RRTA是直接计算评价函数的确切值,大大地减少CPU的处理器为英特尔 Pentium双核T4400@2.20GHz,内存是T作量。使CPU有更多的时间处理其他的任务,加快程序2GB。在实验中,测试数据是均匀分布的数据(RT入同样的运行速度。可以处理非均匀分布的数据),属性值的区问为(0,11,m的入.(3结条件:RRTA读取的记录的总个数小于等于取值为5图1是执行时间与元组数量的对应关系,图2是MA的增长阶較任意一个列文件该取记录的总个数。因读取的记录行数与元组数量的对应关系。为NRA的结束条件是在收缩阶段满足PQ.min≥Ft(vt24000tc(C-PQ),而RRTA的结束条件是和TA一样的,当且仅当Pmm不小于z时,算法终止。NRA增长阶段结束的条件为P。mm≥r,而此时的P维护的为所有元组的评价函10000数的下界值的Top-K,由Pam(NR4)≤Pomn(RTA)(NRA增长阶段结束时的Pa、RRTA算法结束时的Pa),可知算法结束时τ(NRA)≤r(RRT4)。4)数据的读取量:令C(x)表示算法x的数据的读取量,则C(RRA)≤C(NRA(属性值均匀分布且属性间独立分布)。设NRA增长阶段结束时每个列文件读取了n1行1000记录,读取的数据项为2×mxm1(m个列文件各包含两个640属性),NRA结束时为n,行记录,读取的数据项为2345678910II1213|415元组数据Nl2xmxm2,那么可推出n2=m×n1,C(NRA)=2× m x I x FL1图1执行时间与元纽数量的对应关系RRTA结束时表T读取了a行记录(a可以忽略不计),最1400后一条记录的行号ROW为n3,表2读取了n1行记录,读l000取的数据项为(m+1)×n,(一个标识符和m个属性),可知n4=m×n3,C(RRTA)=m×(m+1)×n36由结束条件r(NR4)≤T(RRT可知n1≥n3令1=2xm×m,12=m11xm,山1-12=m×m-m≥0(m≥1)、n1≥n3,得C(RR7A)≤C(NRA)。(5)数据的读取时间:把表T,划分为A个表,并用B个线程进行读取后,可以缩短数据的读取时间:在海量数100据处理的时候,影响程序运行时间的主要因素之一就是数据的读取时问。因此能够提高数据的读取效率,就能减少程序的运行时间。RRTA运行的时候,是B个线程同时进行的读取,在多核或者多CPU的环境中,能够充分地发挥423467890l2131415多处理器的优势。NRA则不然,只有m(即属性的个数)元组数据N/10个。因此在多处理的环境下RRTA的数据读取效率要高于图2读取的记录行数与元组数量的对应关系120013,49(17)Computer Engineering and Applications计算机工程与应用RRTA把N个元组进行了划分,存储在A个子表中,参考文献:且每个子表大小基本一样(最后一个子表可能差别较1 Ilyas I F, Beskales G, Suliman M A.A survey of Top-k query大)。从RRIA算法可以推断出,影响程序运行时间的最主processing techniques in relational database systems JI要的因素就是读取的数据量的大小,更宏观一点就是渎取ACM Computing Surveys, 2008, 40( 4)的子表的个数。而每一个子表的读取时间可以认为是相[2] Fagin R, Lotem A, Naor M Optimal aggregation algorithms同的,所以RRIA程序的运行时间最终就由总共读取的T2for middleware[J]Journal of Computer and System Sciences划分的子表的个数决定的,而71几乎可以忽略(T在每2003,66(4):614-656次的循环中只是读取一条记录)。进而推出RRTA在海量[3 Guntzer J, Balke W T, Kiessling WTow ards efficient multi-ature queries in heterogeneous environments/Proceed数据情况下的运行吋间是同数据量正相关,即一旦具体的ings of the 2001 International Symposium on Information硬件设施确定以后,如果不再修改稈序,那么程序的运行Technology: Coding and Computing, Las vegas, NV, USA时间主要取决于数据的数据量,而基本上不再受硬件的制001:622-628约,RRTA算法的这一特性在处理海量数据中貝有明显的4] Mamoulis n, Cheng K H, Yiu m L, et al. Efficient aggrega优势。从图1可以看出当N到达一定的值后,RRTA算法Lion of ranked inputs[C]Proceedings of the 22nd Interna的运行时间与元组个数N基本成线性关系(斜率只是隋数ional Conference on Data Engineering(ICDE'06), Atlanta据量增加稍微减小,这是因为截止时读取的数据量占总数GiA,USA,2006:72-83据量的比例稍微减小),这验证了前面对于RRTA的运行时15 amounts. 1u, cng, ct al. Efficient Top-间与数据量的关系的分析。导致在开始阶段不成线性关aggregation of ranked inputs[.ACM Transactions on Data-系是因为在小数量进行实际测试的时俠,T2子表的划分与base Systems( TODS),2007. 32(3)[6 Marian A, Bruno N, Gravano L Evaluating Top-k queries大数据量时子表的大小不同,这么做是为了保证线程的个over web-accessible databasesJACM Transactions on Data数B不要太小,提高程序的运行效率。从图2可以看出当base Systems(TODS), 2004, 29(2): 319-362N到达一定值后,总共读取的记录的行数与N也基本成线[7] Hwang s W, Chang k CC Probe minimization hy schedule性关系,这验证了前面的结论:影响程序执行时间的主要optimization: supporting Top-k queries with expensive predi因素就是读取数据量的大小cates[J]. IEEE Transactions on Knowledge and Data EngineerIng,2007,19(5):646-6626结束语18 Pang HH, Ding X H, Zheng B H Efficient processing of文中针对海量数据在随机读受限场合的Top-K賽询进exact Top-k queries over disk-resident sorted lists.VLDB行了分析,并提出了自己的解决方案。首先对海量的数据Journa1,2010,19(3):437-456进行处理,改变数据的存储方式,使之尽可能有利于提高9 Fagin R, Kumar R. Sivakumar D Efficient similarity scarchand classification via rank aggregation[c]/proceedings of査询效率,同时降低査询的代价。由于硬件设施的限制the 2003 ACM SIGMod Internalional Con ference on Man实验没有与TA和NRA进行真实地比较,但是在文中已经agement of Data( SIGMOD03 ), San Diego, California, USA从不同的角度同TA,NRA进行了对比,从中可以明显地看2003:301-312出RRIA算法相对NRA的优势,而同TA要进行确切对比[0]韩希先,杨东华,李建中TKIP:海量数据上一种有效的就要用实验来比较驗证了。TopK查询处理算法门计算机学报,201033(8):1405-1417(上接102页)ence on Communications. 2011: 1-5[9] Rad H J, Abdizadeh M. Abolhassani B Joint optimization of [12] Qin Q, Zeng Z M, Zhang T K,et al.A multi-relay selectionpower allocation and relay selection in cooperative wirelessalgorithm based on the residual energylC'ieee Globalsensor networks[C]/EEE 3rd International SyInposiunn onMobile congress, 2010:1-5Advanced Networks and Telecommunication Systems, 2009[L3]龚渝钧,朱宇最小功耗的中继选择与功率分配的联合优化[1-3信息与电子工程,2012,10(1):7-12.[1O] Chen D, Ji Il, Li X, et al.A novel multi-relay selection1 14 Ikhlef A, Michalopoulos D s, Schober R Max-Max relay se-and power allocation optimization scheme in cooperativelection for relays with buffers[IEEE Transactions onnetworks[c]//Proceedings of IEeE Wireless CommunicaWireless Communications, 2012,1I(3): 1124-1135tions and Networking Conference 2010:1-6[15] Wci Y F, Richard F, Song M Encrgy cfficicnt distributcd relay[11 Chen D,Ji H, Li X An energy-efficient distributed relay seleclection in wireless coopcration nctworks with finitc statction and power allocation optimization scheme over wiremarkov channcls[c]/proccedings of TEEF. Telecommunicationsless cooperative nctworks[CEEE International ConferConference 2009: 1-6