Research problem in Streaming

Observe a stream of tuples (i,j) where the same tuple may be seen many times over the stream. For each i, define d_i to be the number of distinct j's in tuples (i,j). Define M_2= sum_{i=1}{n} d_i^2. Problem: Estimate M_2 in space polylogarithmic in n.

This is the generalization of the second frequency moment F_2 studied in the classical Alon-Matias-Szegedy paper and elsewhere. The best known space bound for M_2 is O(1/\eps^4 \sqrt{n} \log n) for 1+\eps approximation, while that for F_2 is O(1/\eps^2 \log n). Any improvements to M_2 estimation will be great!