PMS: An effective approximation approach for distributed large-scale graph data processing and mining

Recently, large-scale graph data processing and mining has drawn great attention, and many distributed graph processing systems [6-8, 10, 11, 13, 14, 17, 20] have been proposed. However, large-scale graph processing remains a challenging problem. Because the computation time in some cases is still unacceptable especially when the time is limited. As illustrated in Table 1, nearly three hours are needed when running Single-Source Shortest Path algorithm on the USA-road dataset 1 using performant open-source distributed graph processing systems. In this paper, we propose an effective priority-based message sampling (PMS) approach to further improve the performance of distributed graph processing at the cost of some accuracy loss. Noticing that the passing and processing of messages dominates the computation time, our approach works by eliminating those less useful messages directly without passing them which can effectively reduce the computation overhead.We implement our approach basing on Apache Giraph [6], a popular open-source implementation of Google's Pregel [14] and report the primary results of our prototype system. The experimental results show that our approach can achieve reasonable accuracy with much less computation time.