基于穿行次数的大规模图数据路径查询.pdf

ISSN1000—1239／CN 计算机研究与发展 1I-1777]TP !呈坚!竺!!呈!呈呈竺呈竺坠坠!!!竺!!呈!呈!：!!竺呈竺!呈! 基于穿行次数的大规模图数据路径查询 许世峰 高 军 杨冬青 王腾蛟 (北京大学信息科学技术学院计算机科学技术系 北京 100871) (xsfpku@gmail．corn) Pass—·Count--BasedPath on Datasets QueryBigGraph Xu iao Shifeng，GaoJun，YangDongqing，andWangTengj Scienceand Electronics and University， (DepartmentofComputer Technology。Schoolof EngineeringComputerScience，Peking 100871) Beijing AbstractDistanceand in arefundamentaltonumerous from pathqueriesgraphs toInternet ofthese involve and hugegraphs geographicnavigationsystems routing．Someapplications uire newdatastructureiscreatedfor alldistancesina fast representing yetreq queryanswering．A datastructureisdistributedinthesensethatit beviewedas labelstothe graph．The may assigning the ofUand vertices，suchthata verticesU beanswered labels involving and口may usingonly query tO the offl vertexinthe 口．Inthis new count”is measure paper，aconcept“passproposed importance onthe heuristicruleisusedtObuilddistancelabelsforeachvertex graph．Basedpass—count，aspecial ofthe distance and canbe onthoselabels graph。so queriespathqueries processed methodisefficient traversal，andhencereducestime count