In this paper we study data stream algorithms for approximating the number of triangles under the assumption that the algorithm has access to an oracle that answers certain queries about the input graph. Specifically we present algorithms that process the input graph given as a sequence of edges (or vertices) and output an estimate of the number of triangles in the given graph. We consider algorithms that, while processing the input stream, have access to a degree oracle (given a vertex, the oracle provides the degree of the queried vertex) or an edge-triangle oracle where the oracle answers whether an edge $(u,v)$ participates in a triangle or not. We implement two single-pass algorithms and the associated oracles in both the edge-arrival and the vertex-arrival models, and evaluate their performance on real-world datasets. Despite the inaccuracies of the oracles used in our experiments, our study shows that they can improve the performance of state-of-the-art triangle counting algorithms on some real-world graphs.
Jowhari, H. and Rahmati, A. (2025). Space-Efficient Algorithms for Counting Triangles in Data Streams Using Trained Oracles. Computational Methods for Differential Equations, (), -. doi: 10.22034/cmde.2025.65909.3060
MLA
Jowhari, H. , and Rahmati, A. . "Space-Efficient Algorithms for Counting Triangles in Data Streams Using Trained Oracles", Computational Methods for Differential Equations, , , 2025, -. doi: 10.22034/cmde.2025.65909.3060
HARVARD
Jowhari, H., Rahmati, A. (2025). 'Space-Efficient Algorithms for Counting Triangles in Data Streams Using Trained Oracles', Computational Methods for Differential Equations, (), pp. -. doi: 10.22034/cmde.2025.65909.3060
CHICAGO
H. Jowhari and A. Rahmati, "Space-Efficient Algorithms for Counting Triangles in Data Streams Using Trained Oracles," Computational Methods for Differential Equations, (2025): -, doi: 10.22034/cmde.2025.65909.3060
VANCOUVER
Jowhari, H., Rahmati, A. Space-Efficient Algorithms for Counting Triangles in Data Streams Using Trained Oracles. Computational Methods for Differential Equations, 2025; (): -. doi: 10.22034/cmde.2025.65909.3060
)