摘要
NoSQL数据库作为下一代巨型数据的存储模式,在科学计算和商业计算领域均发挥着重要作用,受到当前学术界和企业界的广泛关注。提出一种新的基于NoSQL数据库HBase的并行求取最短路径树的方法。首先利用Watts-Strogatz模型完成对巨型网络的数学建模,这种建模方式使得网络模型具有一定的聚类效果;其次利用HBase最近发布的Coprocessor简化和改进并行BFS方法,提高其计算效率。此外,还设计并实施了大量实验,得出了巨型网络的最短路径树,验证了该算法的正确性和有效性;同时对比其它路径算法,验证了该算法的高效性。
As the next generation of storage model of giant data, NoSQL database plays an important role both in the fields of scientific computing and commercial computing, and has gained wide attention in academia and business com- munity. We presented a new parallel method based on HBase to gain the shortest path tree. Firstly,Watts-strogatz mode was used to complete the mathematical modeling of giant network, therefore the network would have some cluster effects. Secondly, we made a simplification and improvement to the parallel breath-first search method, in order to im- prove its calculation efficiency. In addition, we designed and implemented a large number of experiments. According to the experiment resuhs,we obtained the giant network shortest path tree, and verified the correctness and validity of the algorithm. Meanwhile,Contrast to the other path algorithm, we verified the efficiency of the algorithm.
出处
《计算机科学》
CSCD
北大核心
2013年第3期228-231,共4页
Computer Science
基金
国家自然科学基金项目(61202163
61240035)
山西省自然科学基金(2012011015-1)
山西省科技攻关项目(20120313032-3)资助
