两种模式
对于图在内存中的存储，Euler提供了两种模式，分别为Fast和Compact。两种实现对于上层算法是透明的，在使用时可以根据配置进行设置。
Fast模式
顾名思义，Fast模式下，相关操作能获得更快的速度，但是消耗的内存也相对较多。
Compact模式
与Fast模式相对，Compact模式下，消耗的内存相对较少，但是性能也相对差一些。
两种模式在具体实现上的差异主要有两部分：
1. Feature的存储：
在Fast模式下，每个Feature被保存为一个独立的List，因而每一种类型的Feature均为二维List；
在Compact模式下，同一类型的Feature被合并成一个List进行存储，同时为每个Feature保存该Feature的结束位置用于区分读取。
图 1
2. 节点采样的实现：
在Fast模式下，以Alias method对节点邻居进行采样。基于Alias method的采样在构建完成后，一次采样的时间复杂度为O(2)；
在Compact模式下，则通过随机生成一个采样区间内的随机数，根据随机数对应的CDF来获得样本。由于在采样时需要对候选邻居进行二分，其时间复杂度最大可达O(log2n)。
网友评论