For this prototype a new algorithm for compression is introduced

The algorithm represents a directed graph as a set of bitmaps. The use of bitmap encoding has two key benefits:

1. Bitmaps can encode information very efficiently. For example, a K64 complete graph with 64 vertexes and 2016 edges could be stored in just 64 words on a 64-bit architecture.
2. Binary logic operations can be performed very efficiently due to there support at the processor level.

¹⁾

The algorithm is described as follows:

• Let BD be the dimension of a single bitmap. This is usually based on the underlying platform. For example, for a 32 bit architecture it will be 32 and for a 64 bit architecture it will be 64. Sizing the

A taxomomy of lossless graph compression representations lists just one bitmap based scheme: the DEX general-purpose system for large graphs. ²⁾.

The DEX system is described in two papers, which provide a high level description of the way in which bitmap indices are used. They are one of data structures used alongside other map types, links and various auxiliary structures. ³⁾ The graph is represented as a set of object identifiers (oids) which may identify an vertex (vid) or edge (eid). Within a bitmap each position is allocated to an oid. If the bit is set for a position, then the corresponding object identified by the oid is included in the set. ⁴⁾

This is different from the proposed encoding. The propose encoding is two dimensional with positions represeting only vertices. An edge is represented by a bit value being set at the intersection between the from-vertex and the to-vertex.

A library search for the terms “Bitmap”, “Graph” and Compression“, with the term “Image” excluded, yielded one relevant paper regarding the BitTrain, a proposed technique for training deep learning models with a low memory footprint that allows the network to learn continuously after deployment. ⁵⁾ This approach creates a similar two-dimensional binary map but the setting of a bit represents a non-zero value and not a non-zero value. However, if we consider that to be a graph of all non-zero edges within a neurual network then the two representations are similar. It is possible that the proposed algorithm is a generalisation of the bitmap representation used within BitTrain. More detail of the BitTrain method is required to verify.

* Abdelrahman Hosny, Marina Neseem, and Sherief Reda. “BitTrain: Sparse Bitmap Compression for Memory-Efficient Training on the Edge.” arXiv.org (2021): n. pag. Web. * Besta, Maciej, and Torsten Hoefler. “Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations.” (2018): n. pag. Web. * Martinez-Bazan, N, S Gomez-Villamor, and F Escale-Claveras. “DEX: A High-Performance Graph Database Management System.” 2011 IEEE 27th International Conference on Data Engineering Workshops. IEEE, 2011. 124–127. Web. * Martínez-Bazan, Norbert et al. “Efficient Graph Management Based on Bitmap Indices.” Proceedings of the 16th International Database Engineering & Applications Sysmposium. ACM, 2012. 110–119. Web.