Exploiting the computation potential of multi-core Graphics Processing Units (GPUs) requires reducing memory access latency and memory transfer overheads. Although the GPUs provide fast processing capabilities, the memory on such devices is significantly less. Though the memory hierarchy of GPUs provide certain fast levels, these are limited in terms of storage. Also, in order to use the GPUs for computation, the data must be transferred into the memory of the same; hence, in order to reduce the memory latency for large volume of data transfer, efficient techniques are required. Analysis of graph data on GPUs have many practical applications, and has been studied by both academia and industry. The graph data must be stored on the GPU memory to perform computation and analysis on the same. There are different data structures that can be used to store graphs in the GPU memory. Employing compression techniques to reduce the size required by the data is useful; however, the computation must be performed on the compressed data itself since decompressing the data would not be feasible. In addition to saving space on the device, using compressed data structures also reduces the memory transfer overheads both between the CPU & GPU, and between the various levels in the memory hierarchy of the GPU, thereby compensating for some of the additional time to retrieve information from the compressed data. Storing data using efficient compression techniques and operating on the compressed data is therefore useful. Quadtree data structures are generally used for storing and representing images for various applications. However, graphs when represented as adjacency matrix are comparable to images; hence, using recursive partitioning techniques, the data can be effectively compressed. In this paper, we show techniques based on quadtrees to efficiently compress graph data for storing and computation on GPUs. Additional techniques are also introduced which result in hybrid data structures that perform better for specific cases. Empirical results show 80-90% decrease in the space requirements to store graphs with real-world properties.

Compression, Quadtree, Graph Compression, GPUs

[1] A. Chatterjee, S. Radhakrishnan, and John K. Antonio. Counting Problems on Graphs: GPU Storage and Parallel Computing Techniques. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International, pages 804–812. IEEE, 2012.
[2] P. Harish and P. J. Narayanan. Accelerating Large Graph Algorithms on the GPU Using CUDA. In Proc. of the IEEE Intl Conf. on High Performance Computing, LNCS 4873, pages 197–208, 2007.
[3] H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. SybilGuard: Defending Against Sybil Attacks via Social Networks. In Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM ’06, pages 267– 278, New York, NY, USA, 2006. ACM.
[4] Amin Rezaeipanah, Mousa Mojarad, Link Prediction in Social Networks Using the Extraction of Graph Topological Features, International Journal of Scientific Research in Network Security and Communication, Vol.7, Issue.5, pp.1-7, 2019
[5] A. Chatterjee, S. Radhakrishnan, and J. K. Antonio. Data Structures and Algorithms for Counting Problems on Graphs using GPU. International Journal of Networking and Computing (IJNC), Vol. 3(2):pages 264–288, 2013.
[6] A. Chatterjee, S. Radhakrishnan, and J. K. Antonio. On Analyzing Large Graphs Using GPUs. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, pages 751–760. IEEE, 2013.
[7] L. Becchetti, P. Boldi, C. Castillo, and A. Gionis. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’08, pages 16–24, New York, NY, USA, 2008. ACM.
[8] K. Parimala, G. Rajkumar, A. Ruba, S. Vijayalakshmi, Challenges and Opportunities with Big Data, International Journal of Scientific Research in Computer Science and Engineering, Vol.5, Issue.5, pp.16-20, 2017
[9] Tomás Feder and Rajeev Motwani. Clique Partitions, Graph Compression and Speeding-up Algorithms. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC ’91, pages 123–133, New York, NY, USA, 1991. ACM.
[10] Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph compression with communities. In Proceedings of the 2008 International Conference on Web Search and Data Mining, WSDM ’08, pages 95–106, New York, NY, USA, 2008. ACM.
[11] Keith H. Randall, Raymie Stata, Janet L. Wiener, and Rajiv G. Wickremesinghe. The link database: Fast access to graphs of the web. In Proceedings of the Data Compression Conference, DCC ’02, pages 122– , Washington, DC, USA, 2002. IEEE Computer Society.
[12] P. Boldi and S. Vigna. The webgraph framework i: Compression techniques. In Proceedings of the 13th International Conference on World Wide Web, WWW ’04, pages 595–602, New York, NY, USA, 2004. ACM.
[13] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan. On compressing social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, pages 219–228, New York, NY, USA, 2009. ACM.
[14] Narsingh Deo and Bruce Litow. A structural approach to graph compression. In In MFCS Workshop on Communications, pages 91– 101, 1998.
[15] Morihiro Hayashida and Tatsuya Akutsu. Comparing biological networks via graph compression. BMC Systems Biology, 4(Suppl 2), 2010.
[16] A. Chatterjee, S. Radhakrishnan, and C. N. Sekharan. Connecting the dots: Triangle completion and related problems on large data sets using GPUs. In 2014 IEEE International Big Data Workshop on High Performance Big Graph Data Management, Analysis, and Mining, pages 1–8. IEEE, 2014.
[17] Hanan Samet. Using quadtrees to represent spatial data. In Herbert Freeman and GoffredoG. Pieroni, editors, Computer Architectures for Spatially Distributed Data, volume 18 of NATO ASI Series, pages 229– 247. Springer Berlin Heidelberg, 1985.
[18] J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics, Vol. 6(1):29–123, 2009.
[19] Leskovec, Jure, and Rok Sosi?. SNAP: A General-Purpose Network Analysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology (TIST) 8.1 (2016): 1-20.
[20] Deepayan Chakrabarti and Christos Faloutsos. Graph Mining: Laws, Generators, and Algorithms. ACM Computing Surveys, 38(1), June 2006.
[21] J.M.Kleinberg, R.Kumar, P.Raghavan, S.Rajagopalan, and A.S.Tomkins. The web as a graph: measurements, models, and methods. In Proceedings of the 5th annual international conference on Computing and combinatorics, COCOON’99, pages 1–17, Berlin, Heidelberg, 1999. Springer-Verlag.