Cost-Aware Triangle Counting Over Geo-Distributed Datacenters

Counting triangles is an important topic in many practical applications, such as anomaly detection, community search, and recommendation systems. For triangle counting in large and dynamic graphs, recent work has focused on distributed streaming algorithms. These works assume that the graph is processed in the same location, while in reality, the graph stream may be generated and processed in datacenters that are geographically distributed. This raises new challenges to existing triangle counting algorithms, due to the multi-level heterogeneities in network bandwidth and communication prices in geo-distributed datacenters. In this article, we propose a cost-aware framework named <inline-formula><tex-math notation="LaTeX">${\sf GeoTri}$</tex-math></inline-formula> based on the Master-Worker-Aggregator architecture, which takes both the cost and performance objectives into consideration for triangle counting in geo-distributed datacenters. The two core parts of this framework are the cost-aware nodes assignment strategy in master, which is critical to obtain node's position and distribute edges reasonably to reduce the cost (i.e., time cost and monetary cost), and cost-aware neighbor transfer strategy among workers, which further eliminates redundancy in data transfers. Additionally, we conduct extensive experiments on seven real-world graphs, and the results demonstrate that <inline-formula><tex-math notation="LaTeX">${\sf GeoTri}$</tex-math></inline-formula> significantly lowers both runtime and monetary cost while exhibiting nice accuracy and scalability.