Wenfei Fan
Jingbo Xu
Yinghui Wu
Abstract
We demonstrate GRAPE, a parallel <u>GRAP</u>h query <u>E</u>ngine. GRAPE advocates a parallel model based on a simultaneous fixed point computation in terms of partial and incremental evaluation. It differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole, without the need for recasting the entire algorithms into a new model. One of its unique features is that under a monotonic condition, GRAPE parallelization guarantees to terminate with correct answers as long as the sequential algorithms "plugged in" are correct. We demonstrate its parallel computations, ease-of-use and performance compared with the start-of-the-art graph systems. We also demonstrate a use case of GRAPE in social media marketing.
- W. Fan, X. Wang, Y. Wu, and J. Xu. Association rules with graph patterns. PVLDB, 8(12):1502--1513, 2015. Google Scholar
Digital Library
- W. Fan, J. Xu, Y. Wu, W. Yu, J. Jiang, B. Zhang, Z. Zheng, Y. Cao, and C. Tian. Parallelizing sequential graph computations. In SIGMOD, 2017. Google ScholarDigital Library
- M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. JACM, 34(3):596--615, 1987. Google ScholarDigital Library
- GRAPE. http://grapedb.io/.Google Scholar
- Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Distributed GraphLab: A framework for machine learning in the cloud. PVLDB, 5(8), 2012. Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, 2010. Google ScholarDigital Library
- G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 21(2):267--305, 1996. Google ScholarDigital Library
- I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In KDD, pages 1222--1230, 2012. Google ScholarDigital Library
- Y. Tian, A. Balmin, S. A. Corsten, and J. M. Shirish Tatikonda. From "think like a vertex" to "think like a graph". PVLDB, 7(7):193--204, 2013. Google ScholarDigital Library
- L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103--111, 1990. Google ScholarDigital Library
- D. Yan, J. Cheng, Y. Lu, and W. Ng. Blogel: A block-centric framework for distributed computation on real-world graphs. PVLDB, 7(14):1981--1992, 2014. Google ScholarDigital Library
Recommendations
GRAPE-4: A Teraflops Massively Parallel Special-Purpose Computer System for Astrophysical itN-body Simulations
Proceedings of the 8th International Symposium on Parallel ProcessingGRAPE-4: a one-Tflops special-purpose computer for astrophysical N-body problem
Supercomputing '94: Proceedings of the 1994 ACM/IEEE conference on SupercomputingWe describe the GRAPE-4 (Gravity Pipe 4) system, a special-purpose computer for astrophysical N-body simulations. In N-body simulations, most of the computing time is spent to calculate the force between particles, since the number of interactions is ...
GRAPE project for a dedicated tera-flops computer
PAS '95: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture SynthesisWe are constructing a one tera-flops machine dedicated to astronomical many-body problems. It consists of parallelized GRAPE machines connected to a host workstation. The GRAPE machines only calculate forces between particles in the system by pipeline ...
Comments