Closed jasperzhong closed 2 years ago
挺有意思. 也是采用blocked adjacency list这样的结构,但是block的大小必须是2^m, 然后有很多block array,block array内有很多same size blocks. 不同block array的block size (abbr. bsize) 不同. 有趣. 就像有不同大小的框一样.
为了找到一个合适的"框",可以使用B+ tree来维护一个相同大小的框的free list.
另外还有一个vectorized bit tree,0代表used,1代表empty. 这个本来也可以用来找empty blocks. 但是他们还是用B+ tree来找empty block. 所以这个vectorized bit tree是干啥的?
更新算法. 如果某个vertex的new degree超过了当前的"框"容量,就会让memory manager去找一个更大的"框",同时让memory manager回收旧"框". 有趣.
但这有个问题是单个vertex的degree不能超过block array的容量. 不是很灵活. 不过空间大小最多是2|E|.
实验. 2^16, 2^18, 2^22指的是block array size. 这个越大,空间利用效率越低.
update rate
计算效率和CSR居然差不多.
https://iris.univr.it/retrieve/handle/11562/984826/186609/hornet.pdf
299 后续力作!
code: https://github.com/hornet-gt/hornet