о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



SMDPAڷƵʵĶάݿռ㷨
̷ɡ
ժҪһݷģʽˡԡ˲ݿлƵʺԵĶάݿռõ㷨SMDPA㷨.ģⷢSMDPA㷨һģʽȻܵõõƽͲ.
ؼʡݿ⣬άݿռ䣬ݳ
ͼšTP311.133.2
SMDPA:A SIMILARITY-BASED MULTIDIMENSIONAL
DATA-SPACE-PLACING ALGORITHM
TAN Yu-Song, YANG Li*, and ZHOU Xing-Ming
(National Laboratory for Parallel & Distributed Processing,
National University of Defense Technology, Changsha 410073)
(Northeastern University, Shenyang 110006)
AbstractThis paper describes a new multidimensional data-space-placing algorithm, SMDP A. The algorithm can get the access relation between data hypercubes by using th eir priori frequency and similarities. Consequently, it can place the data hype rcubes efficiently even if they have different accessed frequency. The simulatio n result shows that the SMDPA algorithm may obtain better performance than tradi tional algorithms do.
Key wordsparallel database, multidimensional data space,data hypercube placement
1
70ĩżѸͷչԼӦõĽһƹ㣬ݿӦòϢݿ⣨GISϵͳOLTP֧ϵͳDSS.ǾҪص㣺ݿģԽԽ󣻢ͷǽṹӣ۲ѯӣʵʱҪ.ΪδܵݿӦҪ󣬶ݿо˼ս.
ݿ֮󣬲ݿΪоص㣬ȡ˼ĽչʵӦüֵ12.Բݿʷؼչչ˺ܺõܽ.ѳҵоòݿϵͳXPRS3ݣGamma4ݣGrace5ݣBubba1ݵ.
չ״ǸٵCPU͵ٵI/O֮ܲ.ԣΰѴݷڲݿϵͳĶԪϣI/OЧƥCPUĸ٣СݲѯӦʱ䣬ϵͳܣǲݿϵͳоһؼ.Ļһݷģʽݳ䱻ʵԣ˻ڷƵʺƶȵĶάݿռ㷨SMDPAsimilarly-based multidimensional data-sp ace placement algorithm.㷨ܵģ.
ĵĵ2ڼݷ㷨ϵо״ؽ3ϸSMDPA㷨4ڸSMDPA㷨㷨ܱȽϵģ.
2ع
ݷ÷ɴ·Ϊ4֣˳ļsequentially files methodṹtree-structured methodɢзhash methodļgrid files method.
ΪļܽϺõݿռڵķֲõݷֲ̬ԣԽרҵоҪڸļķ㷨.ҲҪ۸ļķ㷨.
㷨ݷάһΪά㷨Ͷά㷨.άݷ㷨򵥵ݷ㷨ѱĲݿϵͳʵʲ.һɷΪ2ݣRound-Robin㷨Hash㷨Range㷨.ά㷨ֻܽϺõ֧ڻϵݷʣάķܵЧ.ǻڶάԵݷ㷨.
ά㷨ݷõ㷨ͬ·Ϊ¼ࣺ
(1)ģ㷨modulo-based algorithms
DM6ݺCMD7㷨.㷨ǰݿԪȡģ.
(2)㷨exclusive-based algorithms
Field-wise Exclusive-OR Algorithm8ݱǵ㷨.㷨Ҫ˼ΪݵֵõӦĴԪ.ԪΪi1i2iNi1i2iNΪԪ鱻õĴԪ.
(3)ڱ㷨code-based algorithms
Error-Correcting Code Algorithm9ݼΪ㷨.㷨ͬҪֵжƱ룬ȻֵĶֵо㣬ñľ벿ֵõֵӶõӦĴ.
(4)ڿռߵ㷨space-filling curve based algorithms
㷨Ҫ÷μѧɷռĽ.Hilbert Curve Algo rithm10ݼΪ㷨.Hilbert߱ռе㣬ظཻ.Ӷ㷨еõеԱţӶ˱Žݷ. Row-wise Curve Algorithm11ݣPeano Curve Algorithm 12ݣGray Curve Algorithm9ݵ㷨ڸ㷨ķ.
(5)ʽ㷨heuristic algorithms
㷨ݷʵͳϢʽ㷨Чķ.磺Bubba㷨Disk Cooling㷨Ǹ㷨ĵ㷨.
Moon13ݸϸѧ֤DM/CMD㷨ֻСģĴԪĿݲѯԴģ£ǲܵõֵ.ңһЩѯʹӴԪĿҲܸϵͳӦʱ.ڻڱ롢㷨ҪݿϵͳĴԪĿΪ2ݴΣݿռ䱻ֵĿҲΪ2ݴ.Ȼ㷨ܺܺõ֧һ㻷µݷ.ڿռߵ㷨ΪҪάݿռе㷨ûеõܺõؽ㷨ܱ֤ڸӵĶάռиһʽı㷨ҶĳЩռ£Ͳܱе.
ϵ㷨иȱ㣬ûпݷʵģʽǻھȷʵϵͳ£ڸӵʵǲ̫ǡģܸЧ㷨.Щʽ㷨ķݷʵģʽǶƽԡûһ㷨ܺܺõۺϿ.
3SMDPA㷨
3.1ⱳ
1.ݲѯķʱݾʱʱ䳤֮ΪӦʱ䣨responsetime.ΪRT(Q).
ִָʱ紫ʱɺԲƣӦʱɼ򵥵صȼڸԪݷҳֵ.ĵ۶ڸü.
ݷ⣨data declustering problemDDPΪһDάѿݿռ䣺L1,U1ݡL2,U2ݡLD,UDݣռһʷֲݣݿϵͳкNԪ.һݿռĻ㷨ʹ㷨ݲѯӦʱС14.ף14֤һDDPNPC⣬ʶֻͼѰɵõŻĸЧ㷨.
Ϊһݷ㷨Ӧ÷Ϊ֣ݿռĻ㷨data space partition algorithmDSPAݳķ㷨data hypercube placement alg orithmDHPA.ǰ߰һưݿռ仮Ϊɸ壻Щ㷨ݿϵͳдԪ.
ڶάݿռDSPA㷨ϸۣһݷģʽ»ƵʾֵĻ㷨FMDA.Ľϸоݳķ㷨ʼݿռȱֳݳ.
3.2SMDPA㷨
еݷ㷨ǻڷģʽȷֲļ裬ȻüһʵӦñ²㣬Ը㷨ʵܽϲ.ȻЩʽ㷨ܻһķģʽǲûгйطģʽͳϢʶҲ̫.
ǵʵݷʵʱ/վֲԣݳ֮ķʴ.о÷Ե.
2.ɲݿϵͳϵͳķ־õݳıʸʳ֮Ϊݳ鱻ʸʣpriori accessed frequency.PAFAʾݳA鱻ʸ.
3.ǵӦϵͳķʱ/վֲԣݳAԸpʣݳBѱʣǳݳABֵΪpƶȣsimilarity.SimA,Bʾ.ʵϵͳУǿԼ򵥵ΪSimA,B=SimB,A.
4.ǵʵϵͳеݷʾֲԣǿΪϵͳͨݳĺ鱻ʸʣposteriori accessed frequencyʸݳ.ʹPeAFAʾݳAĺ鱻ʸ.
Ϊ߲ݿϵͳݲѯӦĲӦýͬʱʵݳõͬĴڵ.жЩݳܱͬʱأʵʵĲݿϵͳֻϵͳ־Ƶõݳ鱻ʸʣεõǵĺ鱻ʸʣҪƶȸ.ƶȶʵϵͳκݳķʾֲ.ѧĹ۵㣬ƶȱϺݳʵͬ.
ϵͳѷĳݳ壬֮ΪA.Ƕʣûбʵݳ壨ΪBԣAһͬݲѯʣҲǱʣǺݳһͬʣ.ǿPAFASimBAõBġα鱻ʸʣȽϸøֵB鱻ʸ.鱻ʸֵݳBֻԺСĸAͬʣ˵BԽϴʺAͬ.ʱǱҪBıʸֵȻΪ鱻ʸʡȻΪα鱻ʸʣҼ¼BAͬʵĽ.ȻϵıʸʱĹУݳġ鱻ʸʡֵԽԽ.
϶δʵݳһֵֵǱҪжһܱʵݳ.ȻոʵĹ۵㣬ÿѡĸñݳδʵݳıʸֵ.
˲ֺǱ㽫еݳѡ.еݳݱʵԣΪ.ͬһеݳ彫ԴʱͬʱʣȾнǿķʾֲ.ҶԪص˳Ǳηʵ˳.
ˣΪʹݿϵͳܽϺõز֧ݲѯӦýͬһеݳõͬĴڵ.ʱǱ԰Щݳ尴DMضʼڵ㿪ʼ.
ͬʱΪʹϵͳнϺõƽܣÿнзʱѡʼڵӦǵʱдڵеĴڵ.
˼룬ĸݳ㷨SMDPA
Input:
{PAF(DCi)|iʣ1,2,,K},УKݳ
{Sim(DCi,DCj)|i,jʣ1,2,,K};
N,ڵĿ.
Output:
{PUId(DCi)|iʣ1,2,,KݡPUId(DCi)ʣ1,2,,N},ʾݳ
屻õĴڵı
/*ȳʼ㷨ɲ*/
1.DC={DCi|iʣ1,2,,K}
2.Prob(DCi)=PAF(DCi),iʣ1,2,,K
3.ListId(DCi)=NULL,iʣ1,2,,K
4.NumOfLinkedList=-1
5.WorkLoad(PUi)=0,iʣ1,2,,N
/*ͬһڵĽڵнǿ*/
6.while(DC>0)do{
7.ѰҾ󱻷ʸʵݳ壬ΪDCi
8.DC=DC-{DCi}
9.ifListId(DCi)=NULLthen{
10.NumOfLinkedList=NumOf-LinkedList+1
11.LinkedList(NumOfLinkedList)={DCi}
12.ListId(DCi)=NumOfLinked-List}
Else
13.LinkedList(NumOfLinkedList)=LinkedList(NumOfLinkedList)+{DCi}
/*DCiĸֵδѡݳĺ鱻ʸֵ*/
14.for(all DCj in DCji)do{
15.TempFrequency=Prob(DCi)Sim(DCj,DCi)
16.if(TempFrequency>Prob(DCj))thendo{
17.Prob(DCj)=TempFrequency
18.ListId(DCj)=ListId(DCi)
}/*end of if*/
}/*end of for*/
}/*end of while*/
/*ѽеݳ嶼еУҪЩڵݳ
õеĴԪ*/
19.for(i=0;i<NumOfLinkedList;i=i+1)do{
20.List=LinkedList(i)
/*õеĴڵΪʼýڵ*/
21.k=GetIdleNodeID();
22.ݳ,do{
/*裬ڷDCj*/
23.PUId(DCj)=(j+k)mod N
24.WorkLoad(PUId(DCj))=Work Load(PUId(DCj)) +Prob(DCj)
}/*End of visits all data hyper-cubes in one linked list*/
}/* End of for, which visits all linked lists to place the data hyper-cubes*/
4㷨ܷ
ǸSMDPA㷨ģ.ȶܵĲ.
5.һݿռ仮ֺͷ㷨ݲѯQʵݳ屻ɸڵ.ЩڵĿ벢ݿϵͳдڵĿıֵ֮ΪݲѯĲжȣdegree of parallelismDP.DP(Q)ʾݲѯQĲж.
ȻݲѯDPֵ1.
6.һݿռ仮ֺͷ㷨ݲѯQʵݳ屻DP(Q)ڵ.ʽΪݲѯQƽȣdegree of balanceDB.

ʽУNumOfCube(PUi)ʾPUiд洢ݲѯQʵݳ.PUSet(Q)ʾݲѯQĴڵ㼯.ȻԪصĿDP(Q).
Ȼݿռ仮ֺͷ㷨ԣӦʹϵͳݲѯӦĲжȾܵشƽȾܵС.
ڱУ˶άݿռģ⣬4㷨ܱȽ.ǣCMD㷨Hilbert Curve(HCA)㷨FieldXOR(XOR)㷨FMDA/SDMPA㷨.
ģײȼݳڿռϵķֲһĸʷֲ.ǽ̬ʷֲģ.
ĸʷֲʷֲݳ.Ϊݿռڷ(peak point)ݿϵͳԷ㴦ݼ¼нϴķʸ.ζţڷ㸽ݼ¼ֲܼڷ㸽ݲѯܼ.
Ϊǰ3ַǼ򵥵Ľݿռֵֻ֣FMDA㷨ǽݿռбʸʵĸʾֻ.ʶݿռĻ㷨ʵֵַֻֻ֣ʾַֻ.
øݿռ仮ַлֺ󣬱õɸԵݳ.ֱ4㷨ݳķ.
ͼ1ʾ˾4ַ㷨󣬸ڵݳ屻ʸܺͣڵıʸ.

ͼ116/2500¸Ԫıʸܺ

4㷨УȻֻFMDA/SMDPA㷨ܻϽдڵıʸʱ.3㷨ʹִڵȣЩȴڵȻΪϵͳƿͬʱȴĴڵıʸʽϵͣЩڵ㽫ϵͳйнΪ.磬HCA㷨ʹ3ڵıʸʸߴ0.1343912ڵıʸȴֻ0.0342095֮ıߴ4.
ͼ2ͼ3ʾڴڵĿΪ16ݳĿΪ9004㷨ĲжȺƽܵıȽ.

ͼ216/900µĲ

ͼ316/900µƽ
ͼ4ͼ5ʾڴڵĿΪ16ݳĿΪ25004㷨ĲжȺƽܵıȽ.

ͼ416/2500µĲ

ͼ516/2500µƽ
ͼ6ͼ7ʾڴڵĿΪ32ݳĿΪ25004㷨ĲжȺƽܵıȽ.

ͼ632/2500µĲ

ͼ732/2500µƽ

ЩͼУǲѷFMDA/SMDPA㷨н3㷨õĲܺƽ.磬ģΪ32ڵ㡢ݳĿΪ2500ʱݲѯķʳΪ0.5SMDPA㷨Ĳжȸߴ0.8505ƽΪ0.0851.ͬʱHCA㷨Ӧֵȴֻ0.4755ƽΪ0.2154.
⣬ǻԷ֣䣬ڵĿʱFDMA/SMDPA㷨иõ.磬ڴڵΪ16ʱͬ0.5ĲѯʱSMDPA㷨ĲжֻΪ0.793ƽȴߴ0.1065.ӴڵĿʱSMDPA㷨ܸõؽͬһеݳڲͬĴڵ.㷨ķýڵѡҲˣûܺܺõݳķʾֲԣʶܸƲ.
䣬ݳĿʱFDMA/SMDPA㷨ҲнԵظ.磬ڵĿΪ16ݲѯΪ0.2ݳĿΪ900ʱSMDPA㷨ĲжȺƽȷֱΪ0.70980.1354ݳĿӵ2500ʱӦӵ0.7930.1065.ΪݳĿʱ㷨ùݳ屻ʵϢܸӳ֣ӶܸӾȷݳıʾֲԣܸõطЩݳ.
õȻѧĿ(Ŀ69673046).
߼飺̷ɣУ19769˶ʿоҪоΪݿ⡢Эͬ.
У19626ʿ󣬸ڣҪоΪݿ.
У193812пԺԺʿڣʿʦҪоΪ
ܼϵṹֲݿ⡢Эͬ.
ߵλ̷ɡ(Ƽѧֲصʵҡɳ410073)
(ѧġ110032)
ο
1BoralH et al.Prototyping Bubba:A highly parallel database system.IEEE Trans on Knowledge and Data Engineering,1990, 2(1): 14
2Dewitt, Jim Gray. Parallel database systems: The future of database pr ocessing or passing fad. Proc of ACM SIGMOD, 1990, 14(4): 104112
3Stonebrake. The Design of XPRS. In: Proc of 14th VLDB Conf on VLDB. L os Angeles, 1988. 1835
4Dewitt D J et al. The gamma database machine project. IEEE Trans on Knowledge and Data Engineering, 1990, 2(1): 4462
5Kitsuregawa M et al. Architecture and performance of relational al gebra machine GRACE. In: Proc of the 1984 International Conference on Parallel P rocessing. Los Angeles: IEEE Computer Society Press, 1984
6Du H C, Sobolewski J S. Disk allocation for cartesian product files on multi-disk system. ACM Trans on Database Systems, 1982, 7(1): 82101
7Li, Srivastava J. CMD: A multidimensional declustering method for para llel database system. In: Proc of 18th VLDB, 1992. 314
8Kim Myoang Ho, Pramanik Sakti. Optimal file distributions for partial match retrieval. Proc ACM SIGMOD, 1988, 17(3): 173182
9Faloutsos C. Gray codes for partial match and range queries. IEEE Tra ns on Software Engineering, 1988, 14(10): 13811393
10Faloutsos. Declustering using fractals, parallel and distributed. In: C onference on Parallel and Distributed Information System, San Diego, 1993. 1825 
11Samet. Applications of Spatial Data Structure. Reading, MA: Addison-We sley, 1990
12Orenstein, Merrett T. A class of data structure for associative search ing. In: Proc of ACM SIGMOD, Waterloo, 1984. 181190
13Moon B, Acharya A, Saltz J. Study of scalable declustering algorithm f or parallel grid files. In: Proc of the 10th International Parallel Processing Symposium. Los Alarnitos: IEEE Computer Society Press, 1996. 434440
14Bell D. Difficult data placement problems. The Computer Journal, 1984 , 27(4): 315320
15Faloutsos C, Metaxas D. Disk allocation methods using error correcting code. IEEE Trans on Computers, 1991, 40(8): 907914
16Faloutsos C, Metaxast D. Declustering using error correcting codes. In: Proc Symposium on Principles of Database System, 1989. 253258
17Grade, Gunther O. Multidimensional access methods. ACM Computing Surve ys, 1998, 30(2): 170231
18Hinrichs K. Implementation of the grid file: Design concepts and experi ence. BIT, 1985, 25(4): 569592
19Himatsingka, Srivastava J. Performance evaluation of grid based multi- attribute record declustering methods. In: Proc of 18th VLDB, 1994. 356365
ԭյڣ1999-04-08޸ĸյڣ1999-08-30.
