Differences

This shows you the differences between two versions of the page.

--- retegraphprocessing:elements:prototyping:new_algorithm [2023/05/15 09:33] – gedbadmin
+++ retegraphprocessing:elements:prototyping:new_algorithm [2024/01/19 17:46] (current) – removed gedbadmin
@@ Line 1: / Line 1: @@
-====== New Algorithm Prototype ======
-===== Introduction =====
-For this prototype a new algorithm for compression is introduced
-===== The Algorithm =====
-==== Description ====
-The algorithm represents a directed graph as a set of bitmaps.  The use of bitmap encoding has two key benefits:
-  - 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.
-  - Binary logic operations can be performed very efficiently due to there support at the processor level.
-((Martínez-Bazan, Norbert et al. 2012))
-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
-==== Originality ====
-A taxomomy of lossless graph compression representations lists just one bitmap based scheme: the DEX general-purpose system for large graphs.  ((Besta, Maciej, and Torsten Hoefler. 2018)).
-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.  ((Martínez-Bazan, et al. 2011))  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.  ((Martínez-Bazan, et al. 2012))
-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.  ((Abdelrahman, etal. 2021))  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.
-====== References ======
-* 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.