基于聚类的位置数据库动态重组

Vol.14,No.5©2003JournalofSoftware1000-9825/2003/14(05)0963*1+,1,2,1,2,1,11(,100871)2(,100871)DynamicReorganizationofLocationDatabasesBasedonClusteringMAShuai1+,WANGTeng-Jiao1,2,TANGShi-Wei1,2,YANGDong-Qing1,GAOJun11(DepartmentofComputerScienceandTechnology,PekingUniversity,Beijing100871,China)2(NationalLaboratoryonMachinePerception,PekingUniversity,Beijing100871,China)+Correspondingauthor:Phn:86-10-62756374,E-mail:[e-mail](5):963~969.:Howtoeffectivelyorganizeandstoretheprofileofmovingobjectsinamobileenvironment,whichcaneffectivelylowerthepagingandupdatecost,isanimportantprobleminlocationmanagement.Combiningdataminingintoamobileenvironmentisachallengingresearchtask,whichhasbroadprospectiveapplications.Inthispaper,asolutionisprovidedtooptimizetheplacementoflocationdatabasesfromtheaspectofdatamining.Firstanewhierarchicalclusteringalgorithmispresentedtoclusterthemovinglog,thenusetheclusteringresultstodynamicallyreunitelocationdatabases,thusthepagingandupdatecostcanbeloweredeffectively.Keywords:clustering;datamining;locationmanagement;mobileobject;locationdatabase:,(mobileobject)(locationmanagement).,.,.,,.:;;;;:TP391:A*SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2002AA4Z3440();theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.G1999032705((973));theFoundationoftheInnovationResearchInstituteofPKU-IBMofChina(-IBM):(1975),,,,,.964JournalofSoftware2003,14(5),(mobileobject),(locationmanagement),.(locationdatabases)[1](profile),(location).(HLR/VLR)[2].,HLR,;VLR.HLR/VLR,,.,.[3];[4],.,,,[5],[5],;[6].,.,,,,.1.2.31,.(1,,),,(zone)(cell)(,),..1,04;4,5,61.,,.1.11([1]).,(leastcommonancestor),.ij[1]LCA(i,j).1,0145,LCA(4,5)=1.2().,,,.ij(nodesofpath)NOP(i,j),,,,NOP(i,j)ij.NOP(4,0)={4,1,0}.3().(distanceofnodes),.ijDOP(i,j),DOP(i,j).1,40DOP(4,0)=3.1.2,,,.,Fig.1Multi-Tiersarchitecture11210119847650123012345687:965ProcedureGraph_Clustering(á){Step1:Graph=Build_Graph()Step2:ClusterInitialSet=GraphStep3:Do{CluserResultSet=Clustering(ClusterInitialSet,á)ClusterInitialSet=CluserResultSet}While(CluserResultSet.sizeClusterInitialSet.size)}Fig.2Graph_Clustering2.,,,.ij,iLCA(i,j)NOP(i,LCA(i,j)),02,0,41.,,(paging))),(,(),(jiLCAiDOPjiCOSTP=,(1)ij,DOP(i,LCA(i,j)),.,,3,iLCA(i,j)COSTd(i,j);LCA(i,j)COSTu(i,j);LCA(i,j)jCOSTi(i,j).(update)1)),,((*2),(+=jjiLCADOPjiCOSTU.(2)(1)(2),LCA(i,j).DOP(LCA(i,j),j)DOP(i,LCA(i,j)).,,,,.,〈old_zone,new_zone〉.,.,LCA(i,j)ij.,.,,.,G=(V,E)á∈[0,1],GSubGsets={G1,G2,…}.Gi[V],Gi[E]Gi;||,.SubGsets={G1,G2,…}(1)∀Gi∈SubGsets,Gi[V]⊆G[V]Gi[E]⊆G[E];(2)∀Gi,Gj∈SubGsets,Gi[V]Gj[V]=∅;(3)SubGsets={G1,G2,…},G1[V]G2[V]…=G[V];(4)∀Gi∈SubGsets,2|][||][|vGiiCEG*≥a;(5)∀Gi,Gj∈SubGsets,GiGj(1),G=(V,E);(2);(3);(4)á,á=1,;(5),.2,.[7].,ROCK[8];CHAMELEON[9]K-NEAREST;AMOEBA[10]DELAUNAY.,,966JournalofSoftware2003,14(5)ClassNode{IntegerIdSetVertexSetNeighborSetDegreeIntegerNumOfVertexIntegerNumOfEdge}Fig.3Datastructure3ProcedureClustering(ClusterInitialSet,á){Step1:CluserResultSet=∅Step2:i=1Step3:If(iClusterInitialSet.size)ThenGotoStep4ElseGotoStep5Step4:ReturnCluserResultSetStep5:Ci=ClusterInitialSet.elementAt(i)IfthereexisitsCj∈ClusterResultSet(1≤j≤ClusterResultSet.size)whichfulfilsGoodness(Ci,Cj)áandCo_neighbor(Ci,Cj)isthelargestoneThenCj=Merging_Clusters(Ci,Cj)ElseGenerateanewclusterCk=Ci(k=ClusterResultSet.size+1)ClusterResultSet=ClusterResultSetCkStep6:i++Step7:GotoStep3}Fig.4Clusteringprocedure4...,,,(bottom-up),,,(2),.2.1:Id;VertexIdid;NeighborVertex;Degree,;NumOfVertexVertex,1;NumOfEdgeVertex,,Vertex1,NumOfEdge0(3).2.2,Ci,CiGraph,CiCi:|Ci|=1:Goodness(Ci)≥a.|Ci|=2:2./.)(xNumOfVerteCiiiCNumOfEdgeCCGoodness=.(3)Co_link(Ci,Cj),Graph.,CiCj2../)),(_..(),(xNumOfVerteCxNumOfVerteCjijijijiCCClinkCoNumOfEdgeCNumOfEdgeCCCGoodness+++=.(4)Goodness(Ci,Cj)≥á.á∈[0,1].Graph,,á.,,á..2.3Build_Graph(),〈old_zone,new_zone〉,Graph(),;3:VertexId,Neighbor,NumOfVertex1,NumOfEdge0,Degree,1.Clustering(ClusterInitialSet,á)4.CluserResultSet∅,ClusterInitialSetCi(1≤i≤ClusteInitialSet.size),:967CluserResultSetCj(1≤j≤ClusteInitialSet.size)Goodness(Ci,Cj),Co_neighbor(Ci,Cj),CiCj,CluserResultSetCj;CluserResultSetCk(k=CluserResultSet.size+1).Merging_Clusters(Ci,Cj),Co_neighbor(Ci,Cj);Co_link(Ci,Cj).1,,,;2.,Goodness(Ci,Cj)≥á,Co_neighbor(Ci,Cj),á.,C=CiCjC.Vertex=Ci.VertexCj.Vertex,C.Neighbor=Ci.NeighborCj.Neighbor-C.Vertex,C.Degree=Ci.DegreeCj.Degree-C.Vertex.Degree,C.NumOfVertex=|C.Vertex|,C.NumOfEdge=Ci.NumOfEdge+Cj.NumOfEdge+1/2*((Ci.NeighborCj.Neighbor)C.Vertex).Degree.,CCiCj;CCiCj,;CCiCj(,),;CNumOfEdgeCiCjNumOfEdge,1/2(,1/2).2.4m,n.Build_Graph()O(n)m×m,O(m2)Graph.Clustering()O(m2),Graph_Clustering()O(n)+O(m2)+O(m3).,Graph_Clustering()O(n).,O(m3).2.5,1.2.,G=(V,E),2.3Goodness(Ci)≥á,,1.2(5),;Goodness(Ci,Cj)≥á,1.2(5);(5),1.2.,1.2.2.6StanfordSUMATRA(StanfordUniversityMobileActivityTRAces).SUMATRA:369