  How can we accurately estimate local triangles for all nodes in simple and
multigraph streams? Local triangle counting in a graph stream is one of the
most fundamental tasks in graph mining with important applications including
anomaly detection and social network analysis. Although there have been several
local triangle counting methods in a graph stream, their estimation has a large
variance which results in low accuracy, and they do not consider multigraph
streams which have duplicate edges. In this paper, we propose FURL, an accurate
local triangle counting method for simple and multigraph streams. FURL improves
the accuracy by reducing a variance through biased estimation and handles
duplicate edges for multigraph streams. Also, FURL handles a stream of any size
by using a fixed amount of memory. Experimental results show that FURL
outperforms the state-of-the-art method in accuracy and performs well in
multigraph streams. In addition, we report interesting patterns discovered from
real graphs by FURL, which include unusual local structures in a user
communication network and a core-periphery structure in the Web.
