Luis Barguñó
Patrick Valduriez
ABSTRACT
The need for managing massive attributed graphs is becoming common in many areas such as recommendation systems, proteomics analysis, social network analysis or bibliographic analysis. This is making it necessary to move towards parallel systems that allow managing graph databases containing millions of vertices and edges. Previous work on distributed graph databases has focused on finding ways to partition the graph to reduce network traffic and improve execution time. However, partitioning a graph and keeping the information regarding the location of vertices might be unrealistic for massive graphs. In this paper, we propose Parallel-GDB, a new system based on specializing the local caches of any node in this system, providing a better cache hit ratio. ParallelGDB uses a random graph partitioning, avoiding complex partition methods based on the graph topology, that usually require managing extra data structures. This proposed system provides an efficient environment for distributed graph databases.
- N. Martínez-Bazan, V. Muntés-Mulero, S. Gómez-Villamor, J. Nin, M. A. Sánchez-Martínez, and J. L. Larriba-Pey. DEX: high-performance exploration on large graph for information retrieval. CIKM 2007:573--582. Google Scholar
Digital Library
- V. Muntés-Mulero, N. Martínez-Bazan, J-Ll. Larriba-Pey, E. Pacitti, P. Valduriez. Graph Partitioning Strategies for Efficient BFS in Shared-Nothing Parallel Systems. WAIM Workshops 2010:13--24. Google ScholarDigital Library
- L. G. Valiant. A Bridging Model for Parallel Computation. Commun. ACM (CACM) 33(8):103--111 (1990). 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. SIGMOD 2010:135--146. Google ScholarDigital Library
- D. Chakrabarti and C. Faloutsos. Graph mining: Laws, generators, and algorithms. ACM Comput. Surv. (CSUR) 38(1) (2006). Google ScholarDigital Library
- Josep M. Pujol, Vijay Erramilli, Georgos Siganos, Xiaoyuan Yang Nikos Laoutaris, Parminder Chhabra, Pablo Rodriguez. The Little Engine(s) That Could: Scaling Online Social Networks SIGCOMM 2010:375--386. Google ScholarDigital Library
- S. Trissl and U. Leser. Fast and practical indexing and querying of very large graphs. SIGMOD 2007:845--856. Google ScholarDigital Library
- Sameh Elnikety, Steven Dropsho, and Willy Zwaenepoel. Tashkent+: Memory-Aware Load Balancing and Update Filtering in Replicated Databases. EuroSys 2007:399--412. Google ScholarDigital Library
- D. Dominguez-Sal, N. Martínez-Bazan, V. Muntés-Mulero, Pere Baleta, and J. L. Larriba-Pey. A Discussion on the Design of Graph Database Benchmarks. TPCTC 2010:25--40 Google ScholarDigital Library
- A. Yoo, E. Chow, K. Henderson, W. McLendon, B. Hendrickson, and U. Catalyurek. A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L. SC 2005:25. Google ScholarDigital Library
- J. Cohen. Graph Twiddling in a MapReduce World. Computing in Science and Engineering (CSE) 11(4):29--41 (2009). Google ScholarDigital Library
- U. Kang, C. E. Tsourakakis, and C. Faloutsos. PEGASUS: A peta-scale graph mining system-implementation and observations. ICDM 2009:229--238. Google ScholarDigital Library
Index Terms
- ParallelGDB: a parallel graph database based on cache specialization
Recommendations
L(2,1)-labeling of dually chordal graphs and strongly orderable graphs
An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the ...
Computing a minimum outer-connected dominating set for the class of chordal graphs
For a graph G=(V,E), a dominating set is a set D@?V such that every vertex v@?V@?D has a neighbor in D. Given a graph G=(V,E) and a positive integer k, the minimum outer-connected dominating set problem for G is to decide whether G has a dominating set ...
Algorithmic aspect of stratified domination in graphs
Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-white) graph is a graph in which every ...
Comments