  Triangle counting and sampling are two fundamental problems for streaming
algorithms. Arguably, designing sampling algorithms is more challenging than
their counting variants. It may be noted that triangle counting has received
far greater attention in the literature than the sampling variant. In this
work, we consider the problem of approximately sampling triangles in different
models of streaming with the focus being on the adjacency list model.
  In this problem, the edges of a graph $G$ will arrive over a data stream. The
goal is to design efficient streaming algorithms that can sample and output a
triangle from a distribution, over the triangles in $G$, that is close to the
uniform distribution over the triangles in $G$. The distance between
distributions is measured in terms of $\ell_1$-distance. The main technical
contribution of this paper is to design algorithms for this triangle sampling
problem in the adjacency list model with the space complexities matching their
counting variants. For the sake of completeness, we also show results on the
vertex and edge arrival models.
