Paper Info
Title
Pagrol: Parallel graph olap over large-scale attributed graphs
Abstract
Attributed graphs are becoming important tools for modeling information networks, such as the Web and various social networks (e.g. Facebook, LinkedIn, Twitter). However, it is computationally challenging to manage and analyze attributed graphs to support effective decision making. In this paper, we propose, Pagrol, a parallel graph OLAP (Online Analytical Processing) system over attributed graphs. In particular, Pagrol introduces a new conceptual Hyper Graph Cube model (which is an attributed-graph analogue of the data cube model for relational DBMS) to aggregate attributed graphs at different granularities and levels. The proposed model supports different queries as well as a new set of graph OLAP Roll-Up/Drill-Down operations. Furthermore, on the basis of Hyper Graph Cube, Pagrol provides an efficient MapReduce-based parallel graph cubing algorithm, MRGraph-Cubing, to compute the graph cube for an attributed graph. Pagrol employs numerous optimization techniques: (a) a self-contained join strategy to minimize I/O cost; (b) a scheme that groups cuboids into batches so as to minimize redundant computations; (c) a cost-based scheme to allocate the batches into bags (each with a small number of batches); and (d) an efficient scheme to process a bag using a single MapReduce job. Results of extensive experimental studies using both real Facebook and synthetic datasets on a 128-node cluster show that Pagrol is effective, efficient and scalable.
Year
DOI
Venue
2014
10.1109/ICDE.2014.6816676
ICDE
Keywords
Field
DocType
large-scale attributed graphs,self-contained join strategy,parallel graph olap system,numerous optimization techniques,decision making,online analytical processing,conceptual hyper graph cube model,single mapreduce job,facebook,parallel algorithms,information networks,pagrol,data mining,graph theory,mrgraph-cubing,social networking (online),mapreduce-based parallel graph cubing algorithm,lattices,computational modeling,warehousing
Data mining,Graph database,Computer science,Theoretical computer science,Relational database management system,Online analytical processing,Data cube,Database,Graph (abstract data type),Scalability,Computation,Cube
Conference
ISSN
Citations 
PageRank 
1084-4627
19
0.70
References 
Authors
19
6
Name
Order
Citations
PageRank
Zhengkui Wang19110.46
Qi Fan2413.02
Hui-Ju Wang3373.90
Kian-Lee Tan46962776.65
Divyakant Agrawal582011674.75
Amr El Abbadi667671569.95