Abstract:In recent years, graph stream analysis has gained increasing importance in both research and industry. A graph stream is a continuous sequence of edges received from a data source at a high speed. Those edges form a dynamic graph that is continuously changing. Various analyses can be performed on graph streams. Among them, triangle counting is one of the most basic operations. However, the large volume and high update speed of graph streams make it inefficient to count triangles accurately on them. It is also unnecessary, as most applications for triangle counting can tolerate small errors. Therefore, approximate triangle counting in graph streams has been a hot research topic. This study focuses on sample-based approximate triangle counting in graph streams with a sliding window model. Sliding window models focus on the most recent edges in a graph stream and consider older edges as expired. They are widely applied in various industrial scenarios and research. This study combines a count-before-sample strategy with the state-of-the-art approximate triangle counting algorithm and designs a set of novel strategies to deal with the difficulty brought by edge expiration. Extensive experiments are conducted on real-world datasets to evaluate the proposed algorithm. Results prove that the algorithm decreases the estimation error of the state-of-the-art method by more than 70%.