A collection designed to efficiently compress sparsely-populated bit-matrices.
See the original proposal here.
Note: This library heavily relies upon bitvec to optimally store its data, which is very slow when compiled without optimisations!
Add k2_tree into your project dependencies:
none
[dependencies]
k2_tree = "0.4.2"
K2Trees are Useful:K2Trees are extremely efficient at representing data that can be encoded as a two-dimensional bit-matrix, especially if said matrix is sparsely populated.
Take a real-world example: representing Web-Graphs.
The connections between webpages can be easily encoded as a 2-d bit-matrix, where each column/row corresponds to a specific page and each bit denotes whether two pages are joined via a hyperlink; 1 if yes, 0 in not.
As it turns out, these matrices tend to be extremely sparse most of the time, which makes the K2Tree a perfect structure for encoding them!
Another example is representing Triple-Stores, which this repo demonstrates is effective.
``` 00|00||10|10
00|00||00|00
10|10||00|11
00|00||00|00 00|00||00|00 ```
[0111; 1101, 1100, 0100; 1000, 1011, 0010, 1010, 1000, 1100]
(Where ; separates layers and , separates blocks)
K2Tree:rust
K2Tree {
stem_k: 2,
leaf_k: 2,
max_slayers: 2,
stems: [0111110111000100],
leaves: [100010110010101010001100],
}
For a more in-depth explanation of the compression process, check this out.
K2Tree work over any value of K.k field into two distinct fields: stem_k, leaf_k.stem_to_leaf and slayer_starts field without compromising operation complexity.- GGabi