[−][src]Crate k2_tree
A collection designed to efficiently compress sparselypopulated bitmatrices.
See the original proposal here.
Note: This library heavily relies upon bitvec to optimally store its data.
If you have k2_tree
as a dependancy, always try to compile with optimisations!
bit_vec
is
very slow without them!
What's new in version 0.5:
K2Tree
now implements serde's Serialize and Deserialize traits.
When K2Tree
s are Useful:
K2Tree
s are useful when you need to store twodimensional data efficiently, especially when
the data is sparsely populated.
A real world example would be representing WebGraphs. In this scenario, each column and row of a bitmatrix would represent a specific webpage, and all bits represent the whether two pages are joined by a hyperlink; 1 if yes and 0 if no. As it turns out, these types of WebGraphs tend to produce sparsely populated bitmatrices.
Another example would be representing TripleStores, which this repo demonstrates is effective.
How it Works:
Original BitMatrix:
00001010 00000011  00000000 00000010 ============ 10100011 10000000  00000000 00000000
As shown above, the 8x8 bitmatrix is subdivided into submatrices where:
 The smallest is width k
 All others are k * children_width
Modified Matrix
Then, all submatrices containing only zeroes are substituted by a single zero, like so:
0 1010 0011  0 00  10 ============ 10100 11 1000 00  0 0 0 0   
K2Tree
Representation of Modified Matrix
And then the K2Tree
is built from this modified matrix:
0111 ______________    1101 1100 0100    1000 1011 0010 1010 1000 1100
From lefttoright in the first layer of the tree, each bit refers to one of the 4 largest quadrants in the modified matrix:
0111
=> Upperleft empty, upperright not empty, lowerleft not empty, lowerright not empty.
Each block in the second layer refers to the submatrices of each parent:
 The upperright quadrant (
1101
) contains the following subquadrants: Lowerleft is empty.
 Upperleft, upperright and lowerright are not empty.
 And so on.
The final, or leaf, layer of the tree contains the actual data in the matrix.
For example, the upperleft subquadrant of the upperright quadrant contains the bits: 1000
.
Bit Representation of K2Tree
Finally, the above K2Tree
is stored as a series of bits:
[0111; 1101, 1100, 0100; 1000, 1011, 0010, 1010, 1000, 1100]
(Where ;
separates layers and ,
separates blocks)
Final K2Tree
:
K2Tree { stem_k: 2, // usize leaf_k: 2, // usize max_slayers: 2, // usize stems: [0111110111000100], // BitVec leaves: [100010110010101010001100], // BitVec }
 groels
Modules
error  Library error types. These are all the custom errors that this library could return. 
matrix 

tree 

Structs
K2Tree  A collection designed to efficiently compress sparselypopulated bitmatrices. 