research-article

Graph cube: on warehousing and OLAP multidimensional networks

Authors:

Jiawei HanAuthors Info & Claims

SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of data

Pages 853 - 864

https://doi.org/10.1145/1989323.1989413

Published: 12 June 2011 Publication History

Abstract

We consider extending decision support facilities toward large sophisticated networks, upon which multidimensional attributes are associated with network entities, thereby forming the so-called multidimensional networks. Data warehouses and OLAP (Online Analytical Processing) technology have proven to be effective tools for decision support on relational data. However, they are not well-equipped to handle the new yet important multidimensional networks. In this paper, we introduce Graph Cube, a new data warehousing model that supports OLAP queries effectively on large multidimensional networks. By taking account of both attribute aggregation and structure summarization of the networks, Graph Cube goes beyond the traditional data cube model involved solely with numeric value based group-by's, thus resulting in a more insightful and structure-enriched aggregate network within every possible multidimensional space. Besides traditional cuboid queries, a new class of OLAP queries, crossboid, is introduced that is uniquely useful in multidimensional networks and has not been studied before. We implement Graph Cube by combining special characteristics of multidimensional networks with the existing well-studied data cube techniques. We perform extensive experimental studies on a series of real world data sets and Graph Cube is shown to be a powerful and efficient tool for decision support on large multidimensional networks.

References

[1]

C. C. Aggarwal and H. Wang. Managing and Mining Graph Data. Springer, 2010.

Digital Library

[2]

T. Baird. The Truth About Facebook. Emereo Pty Limited, 2009.

[3]

D. Burdick, A. Doan, R. Ramakrishnan, and S. Vaithyanathan. OLAP over imprecise data with domain constraints. In VLDB, pages 39--50, 2007.

Digital Library

[4]

S. Chaudhuri and U. Dayal. An overview of data warehousing and OLAP technology. SIGMOD Rec., 26(1):65--74, 1997.

Digital Library

[5]

C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu. Graph OLAP: Towards online analytical processing on graphs. In ICDM, pages 103--112, 2008.

Digital Library

[6]

D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs in massive graphs. In VLDB, pages 721--732, 2005.

Digital Library

[7]

J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Min. Knowl. Discov., 1(1):29--53, 1997.

Digital Library

[8]

P. J. Haas, J. F. Naughton, S. Seshadri, and L. Stokes. Sampling-based estimation of the number of distinct values of an attribute. In VLDB, pages 311--322, 1995.

Digital Library

[9]

J. Han, Y. Chen, G. Dong, J. Pei, B. W. Wah, J. Wang, and Y. D. Cai. Stream cube: An architecture for multi-dimensional analysis of data streams. Distrib. Parallel Databases, 18(2):173--197, 2005.

Digital Library

[10]

V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing data cubes efficiently. In SIGMOD, pages 205--216, 1996.

Digital Library

[11]

H. Karloff and M. Mihail. On the complexity of the view-selection problem. In PODS, pages 167--173, 1999.

Digital Library

[12]

K. LeFevre and E. Terzi. GraSS: Graph structure summarization. In SDM, pages 454--465, 2010.

[13]

J. Leskovec and C. Faloutsos. Sampling from large graphs. In KDD, pages 631--636, 2006.

Digital Library

[14]

X. Li, J. Han, and H. Gonzalez. High-dimensional OLAP: a minimal cubing approach. In VLDB, pages 528--539, 2004.

Digital Library

[15]

C. X. Lin, B. Ding, J. Han, F. Zhu, and B. Zhao. Text cube: Computing IR measures for multidimensional text database analysis. In ICDM, pages 905--910, 2008.

Digital Library

[16]

E. Lo, B. Kao, W.-S. Ho, S. D. Lee, C. K. Chui, and D. W. Cheung. OLAP on sequence data. In SIGMOD, pages 649--660, 2008.

Digital Library

[17]

K. Morfonios, S. Konakas, Y. Ioannidis, and N. Kotsis. ROLAP implementations of the data cube. ACM Comput. Surv., 39(4):12, 2007.

Digital Library

[18]

S. Navlakha, R. Rastogi, and N. Shrivastava. Graph summarization with bounded error. In SIGMOD, pages 419--432, 2008.

Digital Library

[19]

S. Navlakha, M. C. Schatz, and C. Kingsford. Revealing biological modules via graph summarization. Journal of Computational Biology, 16:253--264, 2009.

[20]

M. Newman. Networks: An Introduction. Oxford University Press, 2010.

Digital Library

[21]

Y. Qi, K. S. Candan, J. Tatemura, S. Chen, and F. Liao. Supporting OLAP operations over imperfectly integrated taxonomies. In SIGMOD, pages 875--888, 2008.

Digital Library

[22]

H. Thomases. Twitter Marketing: An Hour a Day. Wiley, 2010.

Digital Library

[23]

Y. Tian, R. A. Hankins, and J. Patel. Efficient aggregation for graph summarization. In SIGMOD, pages 567--580, 2008.

Digital Library

[24]

M. Wattenberg. Visual exploration of multivariate graphs. In CHI, pages 811--819, 2006.

Digital Library

[25]

N. Zhang, Y. Tian, and J. M. Patel. Discovery-driven graph summarization. In ICDE, pages 880--891, 2010.

[26]

Y. Zhou, H. Cheng, and J. X. Yu. Graph clustering based on structural/attribute similarities. PVLDB, 2(1):718--729, 2009.

Digital Library

Cited By

Tsoukanara EKoloniari GPitoura ETriantafillou P(2024)The GraphTempo Framework for Exploring the Evolution of a Graph Through Pattern AggregationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.341064736:11(7143-7156)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3410647
Zou KXie XLi HWang X(2024)Multithreading Heterogeneous Graph AggregationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3320127(1-15)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3320127
Shabani NWu JBeheshti ASheng QFoo JHaghighi VHanif AShahabikargar M(2024)A Comprehensive Survey on Graph Summarization With Graph Neural NetworksIEEE Transactions on Artificial Intelligence10.1109/TAI.2024.33505455:8(3780-3800)Online publication date: Aug-2024
https://doi.org/10.1109/TAI.2024.3350545
Show More Cited By

Index Terms

Graph cube: on warehousing and OLAP multidimensional networks
1. Information systems
  1. Data management systems
    1. Information integration
      1. Data warehouses
  2. Information systems applications
    1. Decision support systems
      1. Data warehouses
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

HMGraph OLAP: a novel framework for multi-dimensional heterogeneous network analysis
DOLAP '12: Proceedings of the fifteenth international workshop on Data warehousing and OLAP

As information continues to grow at an explosive rate, more and more heterogeneous network data sources are coming into being. While OLAP (On-Line Analytical Processing) techniques have been proven effective for analyzing and mining structured data, ...
An efficient method for maintaining data cubes incrementally

The data cube operator computes group-bys for all possible combinations of a set of dimension attributes. Since computing a data cube typically incurs a considerable cost, the data cube is often precomputed and stored as materialized views in data ...
ROLAP implementations of the data cube

Implementation of the data cube is an important and scientifically interesting issue in On-Line Analytical Processing (OLAP) and has been the subject of a plethora of related publications. Naive implementation methods that compute each node separately ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of data

June 2011

1364 pages

ISBN:9781450306614

DOI:10.1145/1989323

General Chair:
Timos Sellis
IMIS/RC Athena
,
Program Chair:
Renée J. Miller
University of Toronto
,
Publications Chairs:
Anastasios Kementsietsidis
IBM T.J. Watson Research Center
,
Yannis Velegrakis
University of Trento

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '11

Sponsor:

SIGMOD

SIGMOD/PODS '11: International Conference on Management of Data

June 12 - 16, 2011

Athens, Greece

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

113
Total Citations
View Citations
1,154
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tsoukanara EKoloniari GPitoura ETriantafillou P(2024)The GraphTempo Framework for Exploring the Evolution of a Graph Through Pattern AggregationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.341064736:11(7143-7156)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3410647
Zou KXie XLi HWang X(2024)Multithreading Heterogeneous Graph AggregationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3320127(1-15)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3320127
Shabani NWu JBeheshti ASheng QFoo JHaghighi VHanif AShahabikargar M(2024)A Comprehensive Survey on Graph Summarization With Graph Neural NetworksIEEE Transactions on Artificial Intelligence10.1109/TAI.2024.33505455:8(3780-3800)Online publication date: Aug-2024
https://doi.org/10.1109/TAI.2024.3350545
Papadaki MTzitzikas Y(2024)Unifying Faceted Search and Analytics over RDF Knowledge GraphsKnowledge and Information Systems10.1007/s10115-024-02076-966:7(3921-3958)Online publication date: 24-Mar-2024
https://doi.org/10.1007/s10115-024-02076-9
Papadaki MTzitzikas YMountantonakis M(2023)A Brief Survey of Methods for Analytics over RDF Knowledge GraphsAnalytics10.3390/analytics20100042:1(55-74)Online publication date: 17-Jan-2023
https://doi.org/10.3390/analytics2010004
Wang GZeng YLi RQin HShi XXia YShang XHong L(2023)Temporal Graph CubeIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327046035:12(13015-13030)Online publication date: 1-Dec-2023
https://doi.org/10.1109/TKDE.2023.3270460
Labzioui RLetrache KRamdani M(2023)New Strategy for Developing and Enhancing Online Analytical Processing Cubes on Graphs2023 14th International Conference on Intelligent Systems: Theories and Applications (SITA)10.1109/SITA60746.2023.10373687(1-8)Online publication date: 22-Nov-2023
https://doi.org/10.1109/SITA60746.2023.10373687
Zhou CZhou SHuang J(2023)Pretrained Node-Enhanced Graph Pruning Network for Inductive Link Prediction2023 China Automation Congress (CAC)10.1109/CAC59555.2023.10451319(8952-8957)Online publication date: 17-Nov-2023
https://doi.org/10.1109/CAC59555.2023.10451319
Yin DZou ZYang F(2022)Effective and efficient aggregation on uncertain graphsFuzzy Sets and Systems10.1016/j.fss.2021.07.017446(261-276)Online publication date: Oct-2022
https://doi.org/10.1016/j.fss.2021.07.017
Jo SPark BLee SKim J(2021)OLGAVis: On-Line Graph Analysis and Visualization for Bibliographic Information NetworkApplied Sciences10.3390/app1109386211:9(3862)Online publication date: 24-Apr-2021
https://doi.org/10.3390/app11093862
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents