In-memory representations for mining big graphs

Abstract

Graphs are ubiquitous and are the best data structure for representing linked data because of their flexibility, scalability, and power to deal with complexity. Storing big graphs in graph databases leads to difficult computation and increased time complexity. The best alternative is to use inmemory representations such as compact data structures. They compress the graph sufficiently such that it can be stored in memory and can allow all the possible operations in compressed form itself. In this paper we discuss about five compression techniques: WebGraph, Re-pair, BFS, k2, and dk2. In addition, we compare them based on four parameters: compression ratio, supported functionalities, supported graph types, and dynamic support. The paper is concluded by bringing out the need to have a more advanced, dynamic, and versatile compression technique. � 2016 IEEE.