Graph OLAP: Towards online analytical processing on graphs

Chen Chen, Xifeng Yan, Feida Zhu, Jiawei Han, Philip S. Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

OLAP (On-Line Analytical Processing) is an important notion in data analysis. Recently, more and more graph or networked data sources come into being. There exists a similar need to deploy graph analysis from different perspectives and with multiple granularities. However, traditional OLAP technology cannot handle such demands because it does not consider the links among individual data tuples. In this paper, we develop a novel graph OLAP framework, which presents a multi-dimensional and multi-level view over graphs. The contributions of this work are two-fold. First, starting from basic definitions, i.e., what are dimensions and measures in the graph OLAP scenario, we develop a conceptual framework for data cubes on graphs. We also look into different semantics of OLAP operations, and classify the framework into two major subcases: informational OLAP and topological OLAP. Then, with more emphasis on informational OLAP (topological OLAP will be covered in a future study due to the lack of space), we show how a graph cube can be materialized by calculating a special kind of measure called aggregated graph and how to implement it efficiently. This includes both full materialization and partial materialization where constraints are enforced to obtain an iceberg cube. We can see that the aggregated graphs, which depend on the graph properties of underlying networks, are much harder to compute than their traditional OLAP counterparts, due to the increased structural complexity of data. Empirical studies show insightful results on real datasets and demonstrate the efficiency of our proposed optimizations.

Original languageEnglish (US)
Title of host publicationProceedings - 8th IEEE International Conference on Data Mining, ICDM 2008
Pages103-112
Number of pages10
DOIs
StatePublished - Dec 1 2008
Event8th IEEE International Conference on Data Mining, ICDM 2008 - Pisa, Italy
Duration: Dec 15 2008Dec 19 2008

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other8th IEEE International Conference on Data Mining, ICDM 2008
CountryItaly
CityPisa
Period12/15/0812/19/08

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Graph OLAP: Towards online analytical processing on graphs'. Together they form a unique fingerprint.

  • Cite this

    Chen, C., Yan, X., Zhu, F., Han, J., & Yu, P. S. (2008). Graph OLAP: Towards online analytical processing on graphs. In Proceedings - 8th IEEE International Conference on Data Mining, ICDM 2008 (pp. 103-112). [4781105] (Proceedings - IEEE International Conference on Data Mining, ICDM). https://doi.org/10.1109/ICDM.2008.30