GMINESYS: Efficient approach to reduce storage area using LZW compression
Ulka A. Panchal, Vina M. Lomte · 2015
Now days there are several graph visualization tools exist to represent the graph. However, they are not able to handle large graphs, and/or they do not allow interaction. We are interested on large graphs, with hundreds of thousands of nodes. Such graphs bring two challenges: the first one is that any straightforward interactive manipulation will be prohibitively slow. The second one is sensory overload: even if we could plot and replot the graph quickly, the user would be overwhelmed with the vast volume of information because the screen would be too cluttered as nodes and edges overlap each other. Our GMine system addresses both these issues, by using summarization and multi-resolution. GMine offers multi-resolution graph exploration by partitioning a given graph into a hierarchy of communities-within-communities and storing it into a novel R-tree-like structure which we name G-Tree. GMine offers summarization by implementing an innovative subgraph extraction algorithm and then visualizing its output. Storage and processing of large data of the large graph is an significant challenge so by using LZW compression technique we can reduce the storage area required to store the huge data of the sparse graph without occurring the data loss. Keywords— Large Graph, Gmine System, Graph Tree, Graph Representation, Graph Partitioning, LZW compression and LZW decompression. INTRODUCTION: An important support for graph exploration is interactive visualization, which can help to quickly identify the main components of a graph, its outliers, the most important edges and communities of related nodes. Large graphs can be found in numerous real-life settings: web graphs, computer communication, recommendation, bipartite graphs of web-logs of who visits what page; blogs and similar [1]. At this magnitude, efficient graph visualization becomes prohibitive because of the excessive processing power requirements that prevent interaction. Besides that, hundred-thousand-node drawings result in unintelligible cluttered images that do not aid the user’s cognition. To face these challenges we present a system that explores two new ideas to address scalability in large graph visualization [5]. Thus here we put two ideas one is to represent large graph using Gmine system and then second to reduce the storage area required to store the huge data. The rest of this paper is structured as follows. Section 2 introduces the DBLP dataset that will be used along this work. Section 3 describes our graph representation in Gmine system idea and section 4 illustrates LZW compression algorithm to reduce the storage area. Section 5 concludes the work. 2. DBLP DATASET: Throughout this text we employ the DBLP dataset to illustrate the functionalities of our system. This dataset originates from the Digital Bibliography & Library Project (or DBLP). DBLP is a publicly available database of publication data that embraces authors (also co-authors) from the Computer Science community [7], Titles of the book and their published works. The version of DBLP dataset that we use defines a graph with n = 315,688 nodes and e = 1,659,853 edges, where each node represents an author or publication or title and each edge denotes a relationship between the authors or titles or publications. 3. GRAPH REPRESENTATIONS IN GMINE SYSTEM: 3.1 Construction of the GraphTree: For this work, initially we need to recursively and hierarchically partition a given graph. For the partitioning task we adopted METIS k-way partitioning [1]. The choice for a specific graph partitioning is independent of the Graph-Tree methodology [15]. Hence, given a graph, we perform a sequence of recursive partitioning to achieve a hierarchy of communities within-communities. At each recursion, each partition is submitted to a new partitioning cycle that will create another set of partitions [20]. This process repeats until we get the desired granularity for the partitions (communities). International Journal of Engineering Research and General Science Volume 3, Issue 2, March-April, 2015 ISSN 2091-2730 734 www.ijergs.org 3.2 Visualization and Interaction: We propose an innovative interactive presentation for large graphs. For this purpose, our system promotes the navigation across the levels of the tree that represents the partitioning of a large graph which is show in the figure 1. As the user interacts with the visualization, the system keeps track of the connectivity among communities of nodes at different levels of the partitioned graph [17]. When the user changes the focus position on the tree structure, the system works on demand to calculate and present contextual information [10]. Also system provides different graph representation layout view to view the large graph in an different angle which are Spring layout, KK layout, FR layout, ISOM layout and circle layout. The system provides zoom facility with increase and decrease form to zoom the graph to see a portion or whole large graph in one view clearly and detail. Node information is also get displayed when click on the node in the Node Information text box. Figure3.1Large graph representation using Gmine system 3.3 Graph Search: The system provides search facility to search a graph according to Author or Title or Publication by entering author name/ publication name/ title name whatever selected user can search the particular graph and view it. Figure 3.2 Search Graph 4. LZW COMPRESSION AND DECOMPRESSION TECHNIQUE: LZW is a data compression and decompression method that takes advantage of this repetition. LZW compression technique converts [27] a big file into a smaller file using a table-based lookup algorithm invented by Abraham Lempel, Jacob Ziv, and Terry Welch. A particular LZW compression algorithm takes each input sequence of bits of a given length (for example, 12 bits) and creates an entry in a table (sometimes called a or codebook) for that particular bit pattern, consisting of the pattern itself and a shorter code and for decompression it reverse the process and get the original data back [27]. 4.1 LZW Compression Algorithm: 1. Initialize the existing dictionary 2. Take the input character say s. 3. Check s is exist in the dictionary 4. If exist then {take next input character say c Check s+c exist in the dictionary If s+c exist in the dictionary then s= s+c International Journal of Engineering Research and General Science Volume 3, Issue 2, March-April, 2015 ISSN 2091-2730 735 www.ijergs.org else add s+c in the dictionary with new code } else add s in the dictionary with a new code 5. Repeat this process until end of the file =0 4.2 LZW Decompression Algorithm: 1. Initialize the existing dictionary with code and its appropriate characters. 2. Take the input code 3. Initially input string is empty {Take the first input code Write the character represented for the first input code in the dictionary} 4. Take the next input code 5. Write the character for next input code 6. Add the previous code character and first character in the next input code character. 7. Print it in the output string. 8. Assign a new code for {(previous code character)+(next input code character)} 9. Repeat this process until EoF=0 LZW Compression and Decompression Result: Now take the input string is “ABABBABCABABBA”, and apply the LZW compression algorithm which gives output codes as 1 2 4 5 2 3 4 6 1. Instead of sending 14 characters, only 9 codes are here. After decompression of these codes we get apparently, the output string is “ABABBABCABABBA”, a truly lossless result! [27]. Compression Result Table: Result Table1.1.For LZW Compression International Journal of Engineering Research and General Science Volume 3, Issue 2, March-April, 2015 ISSN 2091-2730 736 www.ijergs.org Result Table 1.2 for LZW Decompression