Visualizing data structures in sdsl

In this post, I want to present a new feature of the succinct data structure library, which I really like. The problem was the following. When you read a theory paper on succinct data structures you can get easily lost in all those space complexity terms. Often it is hard to imagine how big e.g. \(\log\frac{1}{H_k}\) would be or which constant is hidden in a \(\Order{\cdot}\)-term. It is even worse, if the data structure is composed of many other succinct substructures.

In sdsl you can easily determine for each object how many space is consumed. Say you have an object X then the methods util::get_size_in_bytes or util::get_size_in_mega_bytes will answer you the question. However, you do not know the breakdown to the different components of the data structure. We have addressed that problem and now it is possible to call

write_structure<JSON_FORMAT>(X, std::cout);

to get a hierarchical decomposition of the space usage of a object. The type of the output can be specified by the template parameter. Right now we support output in the JSON format (JSON_FORMAT) and as R lists (R_FORMAT).

Here is an example of the output of an object of a compressed suffix array which is based on a run-length encoded wavelet tree which uses SD arrays. The output contains the information we want to know, however it is hard to read. Therefore lets press to button Show serialize and the JSON output will be transformed in a nice SVG graphic which shows the information in a more accessible way.

{"class_name":"csa_wt","name":"","size":"166327272","children":[{"class_name":"wt_rlmn","name":"wavelet_tree","size":"166313164","children":[{"class_name":"unsigned long","name":"size","size":"8"},{"class_name":"sd_vector","name":"bl","size":"56699449","children":[{"class_name":"unsigned long","name":"size","size":"8"},{"class_name":"unsigned char","name":"wl","size":"1"},{"class_name":"int_vector","name":"low","size":"16107937"},{"class_name":"bit_vector","name":"high","size":"32885152"},{"class_name":"select_support_mcl","name":"high_1_select","size":"3696846","children":[{"class_name":"int_vector","name":"superblock","size":"110129"},{"class_name":"bit_vector","name":"mini_or_long","size":"3944"},{"class_name":"int_vector","name":"longsuperblock","size":"14345"},{"class_name":"int_vector","name":"minisuperblock","size":"3568420"}]},{"class_name":"select_support_mcl","name":"high_0_select","size":"4009505","children":[{"class_name":"int_vector","name":"superblock","size":"114697"},{"class_name":"bit_vector","name":"mini_or_long","size":"4104"},{"class_name":"int_vector","name":"longsuperblock","size":"0"},{"class_name":"int_vector","name":"minisuperblock","size":"3890696"}]}]},{"class_name":"sd_vector","name":"bf","size":"56698169","children":[{"class_name":"unsigned long","name":"size","size":"8"},{"class_name":"unsigned char","name":"wl","size":"1"},{"class_name":"int_vector","name":"low","size":"16107937"},{"class_name":"bit_vector","name":"high","size":"32885152"},{"class_name":"select_support_mcl","name":"high_1_select","size":"3702582","children":[{"class_name":"int_vector","name":"superblock","size":"110129"},{"class_name":"bit_vector","name":"mini_or_long","size":"3944"},{"class_name":"int_vector","name":"longsuperblock","size":"14345"},{"class_name":"int_vector","name":"minisuperblock","size":"3574156"}]},{"class_name":"select_support_mcl","name":"high_0_select","size":"4002489","children":[{"class_name":"int_vector","name":"superblock","size":"114697"},{"class_name":"bit_vector","name":"mini_or_long","size":"4104"},{"class_name":"int_vector","name":"longsuperblock","size":"0"},{"class_name":"int_vector","name":"minisuperblock","size":"3883680"}]}]},{"class_name":"wt_huff","name":"wt","size":"52911426","children":[{"class_name":"unsigned long","name":"size","size":"8"},{"class_name":"unsigned long","name":"sigma","size":"8"},{"class_name":"bit_vector","name":"tree","size":"35600832"},{"class_name":"rank_support_v","name":"tree_rank","size":"8900216","children":[{"class_name":"int_vector","name":"cumulative_counts","size":"8900216"}]},{"class_name":"select_support_mcl","name":"tree_select_1","size":"4824685","children":[{"class_name":"int_vector","name":"superblock","size":"146857"},{"class_name":"bit_vector","name":"mini_or_long","size":"5072"},{"class_name":"int_vector","name":"longsuperblock","size":"14857"},{"class_name":"int_vector","name":"minisuperblock","size":"4657891"}]},{"class_name":"select_support_mcl","name":"tree_select_0","size":"3571875","children":[{"class_name":"int_vector","name":"superblock","size":"105233"},{"class_name":"bit_vector","name":"mini_or_long","size":"3640"},{"class_name":"int_vector","name":"longsuperblock","size":"44059"},{"class_name":"int_vector","name":"minisuperblock","size":"3418935"}]}]},{"class_name":"sd_rank_support","name":"bl_rank","size":"0"},{"class_name":"sd_rank_support","name":"bf_rank","size":"0"},{"class_name":"sd_select_support","name":"bl_select","size":"0"},{"class_name":"sd_select_support","name":"bf_select","size":"0"},{"class_name":"int_vector","name":"C","size":"2056"},{"class_name":"int_vector","name":"C_bf_rank","size":"2056"}]},{"class_name":"int_vector","name":"sa_samples","size":"11481"},{"class_name":"int_vector","name":"isa_samples","size":"33"},{"class_name":"int_vector","name":"char2comp","size":"264"},{"class_name":"int_vector","name":"comp2char","size":"264"},{"class_name":"int_vector","name":"C","size":"2064"},{"class_name":"unsigned short","name":"sigma","size":"2"}]}

The visualization was realized with Mike Bostock's superb D3.js JavaScript library (D3 = Data-Driven Documents). The graphic is a mirrored icicle-graph. You can read the example the following way: The object of class csa_wt has size 158.62 MiB. It has one member named wavelet_tree of type wt_rlmn and this member takes almost all space; namely 158.61 MiB (click on the entry to get this information). The wavelet_tree member itself is composed of three members called bl,bf, and wt. Now you can inspect each of these members by clicking on it. Lets choose bf. The figure will show at the upper part the size and fraction of the selected member. In this example bf takes 54.07 MiB which corresponds to 34.09% of the whole space. Experts will know that the sdsl class sd_vector (64bit implementation of the SD array can be further decomposed into the low and high bit part of the positions of the set one bits and select data structure for the high bit_vector. Explore it if you like ;) To go up the hierarchy again simply click on a element in a higher level and the figure will zoom out again.

And at last the best thing of this blog entry. You can use the form above to paste in your own output and visualize the it!

Published

Tags

• sdsl 3
• visualization 1