现有的分布式三角计数算法假设所有计算节点位于同一地理位置,然而现实中它们可能位于跨洲际的多个数据中心中。跨域分布的数据中心使用广域网连接,具有网络带宽异质、通信费用高昂、分布不均等特点,而现有分布式算法无法适用于跨域环...现有的分布式三角计数算法假设所有计算节点位于同一地理位置,然而现实中它们可能位于跨洲际的多个数据中心中。跨域分布的数据中心使用广域网连接,具有网络带宽异质、通信费用高昂、分布不均等特点,而现有分布式算法无法适用于跨域环境。同时,现有研究较多采用随机采样、淘汰边等策略,忽略了三角形的形成具有时间局部性的特点。因此,研究了跨域环境中真实图流的三角计数问题并提出跨域三角计数(GTC)算法。首先针对现有边分发策略导致数据传输量过高的问题,提出一种跨域边分发策略,以结合通信的时间收益和数据收益建立收益公式,并使用点对点通信代替广播边;然后对于点对点通信在跨域环境中导致的三角形重复计数问题,提出终边计算规则,以确保无重复计数;最后基于时间加权采样算法提出时间加权三角计数算法,以利用三角形的时间局部性特点采样。在5个图流上把GTC与CoCoS(Conditional Counting and Sampling)、Tri-Fly进行对比的结果表明:GTC在通信数据量上比CoCoS减少了17%,比Tri-Fly减少了44%;在误差率上GTC比Tri-Fly减小了53%,略低于CoCoS;在算法运行时间上GTC比Tri-Fly减少了34%,略高于CoCoS。可见,GTC在保证较高准确率与较短算法运行时间的情况下,能有效减少通信数据量。展开更多
文摘现有的分布式三角计数算法假设所有计算节点位于同一地理位置,然而现实中它们可能位于跨洲际的多个数据中心中。跨域分布的数据中心使用广域网连接,具有网络带宽异质、通信费用高昂、分布不均等特点,而现有分布式算法无法适用于跨域环境。同时,现有研究较多采用随机采样、淘汰边等策略,忽略了三角形的形成具有时间局部性的特点。因此,研究了跨域环境中真实图流的三角计数问题并提出跨域三角计数(GTC)算法。首先针对现有边分发策略导致数据传输量过高的问题,提出一种跨域边分发策略,以结合通信的时间收益和数据收益建立收益公式,并使用点对点通信代替广播边;然后对于点对点通信在跨域环境中导致的三角形重复计数问题,提出终边计算规则,以确保无重复计数;最后基于时间加权采样算法提出时间加权三角计数算法,以利用三角形的时间局部性特点采样。在5个图流上把GTC与CoCoS(Conditional Counting and Sampling)、Tri-Fly进行对比的结果表明:GTC在通信数据量上比CoCoS减少了17%,比Tri-Fly减少了44%;在误差率上GTC比Tri-Fly减小了53%,略低于CoCoS;在算法运行时间上GTC比Tri-Fly减少了34%,略高于CoCoS。可见,GTC在保证较高准确率与较短算法运行时间的情况下,能有效减少通信数据量。
