Using entropy metrics for pruning very large graph cubes. (March 2019)

• Record Type: Journal Article
• Authors: Bleco, Dritan; Kotidis, Yannis
• Is Part Of: Information systems. Volume 81(2019)
• Page Start: 49
• Page End: 62
• Publication Date: 2019-03
• Subjects: Graph cube -- Entropy -- Big data; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2018.11.007
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Emerging applications face the need to store and analyze interconnected data. Graph cubes permit multi-dimensional analysis of graph datasets based on attribute values available at the nodes and edges of these graphs. Like the data cube that contains an exponential number of aggregations, the graph cube results in an exponential number of aggregate graph cuboids. As a result, they are very hard to analyze. In this work, we first propose intuitive measures based on the information entropy in order to evaluate the rich information contained in the graph cube. We then introduce an efficient algorithm that suggests portions of a precomputed graph cube based on these measures. The proposed algorithm exploits novel entropy bounds that we derive between different levels of aggregation in the graph cube. Per these bounds we are able to prune large parts of the graph cube, saving costly entropy calculations that would be otherwise required. We experimentally validate our techniques on real and synthetic datasets and demonstrate the pruning power and efficiency of our proposed techniques. Highlights: Propose entropy metrics for evaluating interactions within large graph datasets. Propose techniques to weigh possible OLAP drill-down operations on graph cubes. Present an efficient algorithm for fast selection of aggregated sub-graphs. Evaluation of the presented techniques in large real and synthetic graph datasets.