CAJ | 학술논문

最小生成树(minimum spanning tree,MST)是图论中最为经典算法之一.基于MST结构的聚类、分类和最短路径查询等复杂图算法,在效率和结果质量方面均有显著提高.然而,随着互联网的迅猛发展,图数据规模也变得越来越大,包含千万甚至上亿个顶点的大图数据越发常见.因此,如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一.除此之外,由于大图数据的动态性特征,如何动态地维护算法结果也势必成为最受关注的问题之一.针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim,PP)算法,基于此提出了顶点驱动的并行MST算法——PB(PP Bor(u)vka)算法,并论证了PB算法的正确性.另外,基于MapReduce和BSP框架实现了PB算法.针对只删除动态图特征,提出了MST维护算法,以实现高效的增量计算.对提出的计算和维护算法进行了代价分析和比较.最后,使用真实和模拟数据集,验证了PB算法和维护算法的有效性、高效性和可扩展性.
최소생성수(minimum spanning tree,MST)시도론중최위경전산법지일.기우MST결구적취류、분류화최단로경사순등복잡도산법,재효솔화결과질량방면균유현저제고.연이,수착호련망적신맹발전,도수거규모야변득월래월대,포함천만심지상억개정점적대도수거월발상견.인차,여하재대도수거상실현사순처리화수거알굴산법이성위극대해결적문제지일.제차지외,유우대도수거적동태성특정,여하동태지유호산법결과야세필성위최수관주적문제지일.침대목전집중식적최소생성수산법무법해결해량화동태도수거적문제,수선제출료분구Prim(partition Prim,PP)산법,기우차제출료정점구동적병행MST산법——PB(PP Bor(u)vka)산법,병론증료PB산법적정학성.령외,기우MapReduce화BSP광가실현료PB산법.침대지산제동태도특정,제출료MST유호산법,이실현고효적증량계산.대제출적계산화유호산법진행료대개분석화비교.최후,사용진실화모의수거집,험증료PB산법화유호산법적유효성、고효성화가확전성.