Skip to content

Instantly share code, notes, and snippets.

@vasia

vasia/gist:11349886

Last active August 29, 2015 14:00
Show Gist options
  • Save vasia/11349886 to your computer and use it in GitHub Desktop.
Save vasia/11349886 to your computer and use it in GitHub Desktop.
Download ZIP
A list of applications used in evaluation sections of large-scale graph and iterative processing papers
Raw
gistfile1.md

Applications Used in Evaluation Sections of Large-Scale Graph & Iterative Processing Systems Papers (sorted by frequency)

Application Appears In
PageRank (and variations) 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24
Connected Components (and variations) 1 , 2, 6, 12, 13, 15, 16, 17, 19, 22, 23, 24
SSSP (and variations) 3, 6, 7, 10, 13, 14, 17, 22, 24
ALS 7, 14, 21, 23, 24
Belief Propagation (and variations) 4, 20, 21, 23, 24
Graph Coloring 7, 10, 12, 20
k-means 8, 9, 11, 14
Triangle count 6, 14, 23
SpMV 23, 24
Label Propagation 4
Graph Coarsening 19
Diameter Calculation 16
Adsorption 17
Random Walk 13
Minimum Cost Spanning Tree 24
Maximal Independent Set 24
Conductance 24
Clustering Coefficient 6
Community Detection 23
Minimum Spanning Forest 12
Approximate Maximum Weight Matching 12
Vertex Centrality 14
Edge Centrality 14
Find Mutual Neighbors 6
Gibbs Sampling 20
CoEM 20
Shooting algorithm 20
Compressed Sensing 20
Pairwise Distance Calculation 5
SMACOF 5
SALSA 1
Logistic Regression 8
n-body 11
Descendant Query 18
Affinity propagation -
Balanced label propagation -
Identifying weak ties 25
HITS -
SybilRank -
K-core -

Applications used as examples / pseudocode, but not for evaluation

  • BFS
  • Bipartite Matching
  • Semi-Clustering

References

  • [1] Frank McSherry, Derek G. Murray, Rebecca Isaacs, and Michael Isard, Differential dataflow, in Proceedings of CIDR 2013
  • [2] GraphX: Unifying Data-Parallel and Graph-Parallel Analytics, arXiv:1402.2394
  • [3] Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (SIGMOD '10). ACM, New York, NY, USA, 135-146.
  • [4] Guozhang Wang, Wenlei Xie, Alan J. Demers, Johannes Gehrke: Asynchronous Large-Scale Graph Processing Made Easy. CIDR 2013
  • [5] Jaliya Ekanayake, Hui Li, Bingjing Zhang, Thilina Gunarathne, Seung-Hee Bae, Judy Qiu, and Geoffrey Fox. 2010. Twister: a runtime for iterative MapReduce. In Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing (HPDC '10). ACM, New York, NY, USA, 810-818.
  • [6] Jiwon Seo, Jongsoo Park, Jaeho Shin, and Monica S. Lam. 2013. Distributed socialite: a datalog-based language for large-scale graph analysis. Proc. VLDB Endow. 6, 14 (September 2013)
  • [7] Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin(2012). "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs." Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI '12).
  • [8] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M.J. Franklin, S. Shenker, I. Stoica.Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, NSDI 2012, April 2012
  • [9] Optimization for iterative queries on MapReduce M Onizuka, H Kato, S Hidaka, K Nakano, Z Hu - Proceedings of the VLDB Endowment, 2013
  • [10] Philip Stutz, Abraham Bernstein, and William Cohen. 2010. Signal/collect: graph algorithms for the (semantic) web. In Proceedings of the 9th international semantic web conference on The semantic web - Volume Part I(ISWC'10)
  • [11] Russell Power and Jinyang Li. 2010. Piccolo: building fast, distributed programs with partitioned tables. InProceedings of the 9th USENIX conference on Operating systems design and implementation (OSDI'10).
  • [12] Salihoglu, Semih and Widom, Jennifer (2014) Optimizing Graph Algorithms on Pregel-like Systems. In: 40th International Conference on Very Large Data Bases, 1-5 September 2014, Hangzhou, China.
  • [13] Semih Salihoglu and Jennifer Widom. 2013. GPS: a graph processing system. In Proceedings of the 25th International Conference on Scientific and Statistical Database Management (SSDBM), Alex Szalay, Tamas Budavari, Magdalena Balazinska, Alexandra Meliou, and Ahmet Sacan
  • [14] Shivaram Venkataraman, Erik Bodzsar, Indrajit Roy, Alvin AuYoung, and Robert S. Schreiber. 2013. Presto: distributed machine learning and graph processing with sparse matrices. In Proceedings of the 8th ACM European Conference on Computer Systems (EuroSys '13)
  • [15] Stephan Ewen, Kostas Tzoumas, Moritz Kaufmann, and Volker Markl. 2012. Spinning fast iterative data flows.Proc. VLDB Endow. 5, 11 (July 2012).
  • [16] U. Kang, Charalampos E. Tsourakakis, and Christos Faloutsos. 2009. PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations. In Proceedings of the 2009 Ninth IEEE International Conference on Data Mining (ICDM '09)
  • [17] Yanfeng Zhang, Qixin Gao, Lixin Gao, and Cuirong Wang. 2011. PrIter: a distributed framework for prioritized iterative computations. In Proceedings of the 2nd ACM Symposium on Cloud Computing (SOCC '11).
  • [18] Yingyi Bu, Bill Howe, Magdalena Balazinska, and Michael D. Ernst. 2010. HaLoop: efficient iterative data processing on large clusters. Proc. VLDB Endow. 3, 1-2 (September 2010), 285-296.
  • [19] Yuanyuan Tian, Andrey Balmin, Severin Andreas Corsten, Shirish Tatikonda, John McPherson: From "Think Like a Vertex" to "Think Like a Graph". PVLDB 7(3): 193-204 (2013)
  • [20] Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M. Hellerstein (2010). "GraphLab: A New Parallel Framework for Machine Learning." Conference on Uncertainty in Artificial Intelligence (UAI).
  • [21] Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrinand Joseph M. Hellerstein (2012). "Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud." PVLDB
  • [22] Zhuhua Cai, Dionysios Logothetis, and Georgos Siganos. 2012. Facilitating real-time graph mining. InProceedings of the fourth international workshop on Cloud data management (CloudDB '12)
  • [23] Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: large-scale graph computation on just a PC. InProceedings of the 10th USENIX conference on Operating Systems Design and Implementation (OSDI'12)
  • [24] Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. 2013. X-Stream: edge-centric graph processing using streaming partitions. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles(SOSP '13)
  • [25] Abdul Quamar, Amol Deshpande, Jimmy Lin: NScale: Neighborhood-centric Large-Scale Graph Analytics in the Cloud. CoRR abs/1405.1499 (2014)
@aalexandrov
Copy link

This is A-M-A-Z-I-N-G!!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment