Ӧ
COMPUTER APPLICATIONS
1999 19 9 Vol.19 No.9 1999



ʱĴ洢ۼ
Ƴܡ塡л
ժҪ˴ʱ졢洢Լۼ㷨N23㷨չEN23㷨ԷؽһNN>3άתΪά󽵵I/OЧʡ
ؼʡݲɾۼ㣬ʱ̬
THE STORAGE AND AGGREGATION ON THE DATA
CUBE FOR TIME SERIES
Tang ChangjieYang FengYu ZhonghuaXiang LiminZuo Jie
Computer Department,Sichuan UniversitySichuan.Chengdu 610064
AbstractThis paper proposes the algorithms to build, storage and aggregate the data cube for temporal data. Among them the algorithm N23 and EN23 can convert the N dimensional data cube into a 3 dimensional data cube with low I/O cost and high performance.
KeywordsData mining, Data cube, Aggregation, Temporal data
ʵУдʱйص,Ϊʱ(ʱ̬)ʱзָʾ(ģʽ)й㷺Ӧǰ
1ʱݲɾ弰ѵ
ھ֮ǰҪʷ(ʱ̬)˽ضĹɺƣδԤ⡣磬߽зЩ˸ӿܻʼӦ ԤѴĿܽ,ԤʣʣԤ̨ڸֽĿµʣԸõرŽĿӹȵȡ
ʱзֹɣѡ󣻷ģʽ()㷨߾ָ̽άǽЩѵĻݽṹ֮һ
ΪOLAP()ĹߣάʵʱַڹϵݿROLAPͻڶάݿMOLAPROLAPݵԪΪԪ飬ʺڴ͵ݼϡڹϵݿбдøӽܡMOLAPֱʹݽṹϡ飩ʵֶάάΪᡣһݵԪϡеλãƵڶάе׼ȷλáǣݱȽϡʱַЧʵ͡ѹΪҪĹؼ⡣

ͼ1ά
2άռλʸһά黥
豻ݶNάֱΪD0,D1,,DN-1ÿһάӸֵSumDi άϵֵΪ (di0,di1,diSUM)Ϊ˷㣬diSUM ʾΪDiDi ÿһάDi УDi+1 ֵʸVv0,v1,vN-1 ԪάռеλáһԪĵַһvj ڣDj j0jN ʸV(D0,DN-1 ʾԪӦڷSum
1ͼ1УάάD0,D1,D2ĴСΪD0=5,D1=4,D2=3 di00di1 1ơi=0,1,2ԪV(5,4,3)ʹŵԪV(Sum,Sum,Sum) ַV(5,0,0)ݵԪڲݵԪĺ{ V(0,0,0), V(1,0,0), V(2,0,0), V(3,0,0), V(4,0,0) }ݵԪV(5,4,2)ҲһЩڲݵԪĺͣS1={V(5,0,0), V(5,1,0), V(5,2,0), V(5,3,0)} S2={V(0,4,0), V(1,4,0), V(2,4,0), V(3,4,0), V(4,4,0)}ⲿݵԪV(5,4,0)ֵҪڲݵԪS1S2еֵ
ѯõģάĿֱҪ󷢳֮ǰδ֪ġάһάʵֵġ 磬ͼеĵԪеģV(0,0,0)V(0,1,0)ֱһάеĵ0͵1λáһݵԪV(5,4,3,)ڵ119λãΪһ(5+1)*(4+1)*(3+1)=120ݵԪ
㷨1λתΪάռλʸ㷨˼·ƣƪȥϸڣμhttp//:202.115.48.10 
㷨1λתΪάռλʸ
Procedure Vector2Index(Vector V(v0,vN-1))
{ index = 0; //Nά
for (i=0; i<N-1; i++)
{
index += vi; 
index *= (DI+1+1);
} //end for
index += vN-1;
return index;
}
3Ĵ洢
άʱѯѸӡΪ̽ȽϲͬЧǼеķûʹʱѡ䡣
31ѹһά
ͨOLAP20%ݷ㡣ųЩյԪǼЧķֻ¼ǿյԪݼƫϡѹ֮ǰͲ䣬ѹ齫ǸݵԪƫġ򣬻ظԪʱ任ռķ
3.2B+-ѹ
ڴ棬ʹԵԪƫΪֵ,ݵԪB+-ѽСҶڵָָݵԪǰƫеġݼֵͿԷʶάеκһǿյԪ
3.3ֿ洢
ֿ飬ÿһϡ,ɷڴСֻֿⲿԪֻڲԪͨⲿԪԶԶСڲԪһڲԪƵʡһNάֿ洢ķֽΪȽСĿ飬ҽÿһΪһ洢СֿڸάͬĴСÿһֿ鶼ΪݵԪ
34ROLAP洢
ѹڹϵݿıУаֶΣݵԪƫõԪڶάռеĸάĶһάڶάȵȡÿһԪһѹݵԪеݵԪ뵽֮ǻᱻɿٵزҵָԪ
4ۼ
ۼ㣨ֵֵܺͣСֵǴͳķߡоۼǶһݲֿ⽨ҪĿġϣоۼʱ٣һҪѡСάм㡣ͼ1УΪ˼ⲿݵԪSumѡD2м㡣
4.1ʾۼ㷨
룺nάAD0,D1,Dn-1ݣDiΪiάĳ(1<=i<=n)GΪһۼ{Di0, Di1, ,Din-2}Ϊ{D0, D1,,Dn-1}Ӽ{D0, D1,,Dn-1}-{Di0,Di1,,Dik}= {Dj}(0<=j<n)
{Di0,Di1,,Din-2}Ӧn-1άB
裺D0*D1**Dj-1ݵռM
//ѭ
for (dn-1=0; dn-1<Dn-1; dn-1++)
for (dn-2=0; dn-2<Dn-2; dn-2++)

for (dj+1=0; dj+1<Dj+1; dj+1++)
{ 
for (dj-1=0; dj-1<Dj-1; dj-1++)

for (d1=0; d1<D1; d1++)
for (d0=0; d0<D0; d0++)
{keyС˳B-жһԪ飬ӵM d0ݣݣd1ݣݡdj-1ݣݵԪС
}
//ʾBB-С
for (dj-1=0; dj-1<Dj-1; dj-1++)
or (d1=0; d1<D1; d1++)
for (d0=0; d0<D0; d0++)
{keyĶBмµkey;
{keyMd0ݣݣd1ݣݡdj-1ݣ}Ԫ
뵽ʾBB-С
}}
㷨NάۼΪN-1άãɽNάۼһݵԪ档ʵУҪNάN3 ۼΪάԱ۲ݡˣµĸĽ㷨
4.2ۼĽ㷨(N23㷨)
룺n (n>3)άAD0,D1,Dn-1ݣDiΪiάĳ(1<=i<=n)GΪһۼ{Di0,Di1,Di2}Ϊ{D0,D1,,Dn-1}Ӽ0 i0,i1,i2n-1 i0i1,i1i2,i0i2
{Di0,Di1,Di2 }Ӧ3άB
裺For (I=1; I<Di0; I++)
For (J=0; J<Di1; J++)
For (K=0; K<Di2; K++)
{ BIݣJݣK =
Ad0ݡIݡJݡKݡdn-1 ,
dpI,dpJ,dpK
} 
㷨ɸĽΪN2M㷨NάһתΪMάM<N
4.3ۼƹ㷨(N2M㷨)
룺nάAD0,D1,Dn-1ݣDiΪiάĳ(1<=i<=n)GΪһۼ{Di0,Di1,,Dim-1}Ϊ{D0,D1,,Dn-1}Ӽ0i0,i1,i2,im-1  n-1i0i1im-1
{Di0,Di1,,Dim-1}Ӧmm<nάB
裺
For (I=1; I<Di0; I++)
For (J=0; J<Di1; J++)
For (K=0; K<Di2; K++)
{ BIݣJݣK =
Ad0ݡIݡJݡKݡdn-1ݣ
dpI,dpJ,dpK 
}
4.4N23չ㷨(EN23㷨)
N23㷨ϴI/O϶࣬ⲿݵԪʱžۼмֵ԰Чһ㷨Ҫ¡
裺 (D0ݣ+1)*(D1ݣ+1)**(Dn-1ݣ+1)ռ䣻
 AȡһݵԪaj0ݣj1ݡj(n-1)ݣ
 aj0ݣj1ݡj(n-1)ݷֱڸάӦSumԪͶӰASumݣj1ݡj(n-1)ݣAj0ݣSumݡj(n-1), , Aj0ݣj1ݡSumݣ
 AȡһݵԪִТۣûиݵԪתݣ
 ά
For (I=1; I<Di0; I++)
For (J=0; J<Di1; J++)
For (K=0; K<Di2; K++)
{BIݣJݣK=ASumݡIݡJݡKݡAdp ,
dpI,dpJ,dpK
}
5
 ˼ôSimon FraserѧƷݲɾϵͳDBMinerʾݡݴ洢ΪMicrosoft AccessMDBļCategory, Detailed-category, name, region, country, city, cost, revenue, quantitytime10ֶΣһ1000¼
ӲWin95 +Pentium 200 CPU32Mڴ档
ݡۼ㡢ʹòɾڹɡ
ҪԽѡάֶΣʹN23㷨ԼҪ14ӵʱ䣻ʹEN23㷨ԼֻҪ1ӵʱ䡣ɼEN23㷨N23㷨Чһֵܸ(ڲɾڹɵ㷨)
עоõȻѧ(69773051)ͽѧعԱ
߼飺Ƴܡڡ
塡˶ʿ
л񡡸ڡ
˶ʿооΪݿ⡢֪ʶ̡
ߵλĴѧϵĴ.ɶ610064
ο
1ݡW.H.Inmon. Building the Data Warehouse. Q.E.D Technical Publishing Group, Wellesley, Massachusetts,1992
2ݡR.Kimball. The Data Warehouse Toolkit. John Wiley & Sons, New York, 1996
3ݡS.Chaudhuri, U.Dayal. An overview of data warehousing and OLAP technology. ACM SIGMOD Record, 1997;26:65-74
4ݡR.Agrawal, R.Srikant. Mining sequential patterns. In Proc. 1995 Int. Conf. Data Engineering, March,1995; 3-14
5ݡƳ,.Webвɾڹ.ݿоչ98ʮȫݿѧļɶ1998
6ݡHongjun Lu, Jiawei Han. Stock Movement Prediction And N-Dimensional Inter-Transaction Association Rules. Simon Fraser University,1998
ո:1999-06-28
