Is there a goodness of fit metric that can be computed online with $O(1)$ memory? Say I have two random streams of two dimensional data. I want to measure how closely their underlying PDF's match. My current method is to estimate the PDF's by accumulating the samples online in a 256x256 histogram. After this, I measure the deviation between the two. I am using sum of absolute differences here, but I believe other metrics will work fine as well. 
Some other possibly relevant details: I will be ranking the streams based on their goodness of fit; I don't actually need to perform any hypothesis testing— just find which has highest rank. Also, the distributions are complex, and I don't believe they can be estimated to sufficient accuracy by any well-known analytic distributions.
The problem is, the memory accesses on $t*2^{16}$ bins with $t$ threads, is a significant bottleneck. I was wondering if there were a way to compute the goodness of fit metric without having to accumulate $O(k)$ data about the distributions. Maybe something similar to how there are online calculations of mean/variance that just accumulate one or two variables along the way.
I have looked at Komogorov-Smirnov, Cramer-von Mises, and Shapiro-Wilk tests. They appear to require either 1) an estimation of the sample's CDF, which would still need $O(k)$ variables or 2) ordered data, which isn't possible with an unordered, random stream of data.
Maybe there's some fundamental limitation that prevents a computation comparing PDF's with just $O(1)$ variables?
 A: Consider updating a chi-squared statistic.
$X^2 = \sum_{i=1}^k \frac{(O_i-np_i)^2}{np_i}$
First let us simplify:
$= \sum_{i=1}^k \frac{O_i^2-2np_iO_i+(np_i)^2}{np_i}$
$= \sum_{i=1}^k \frac{O_i^2}{np_i}-2\sum_{i=1}^k O_i+n\sum_{i=1}^k p_i$
$= \sum_{i=1}^k \frac{O_i^2}{np_i}\,-n$
$= [\frac{1}{n}\sum_{i=1}^k \frac{O_i^2}{p_i}]\,-n$
$= S/n - n$
If we can update $S=\sum_{i=1}^k \frac{O_i^2}{p_i}$ quickly it looks like there's a fast algorithm.
So now let us focus on updating $ S$
Note that $O_i$ is just the count in the $i$th bin. When you add a new observation to bin $i$, you add $(2O_i+1)/p_i$ to the sum - all the contributions from other bins are unchanged, and then you can recompute $S/n-n$ at the new value of $n$, this is $O(1)$ in both $n$ and $k$.
Stability
This may potentially be an issue; as $n$ grows you're subtracting two relatively equal quantities (the expected value of the first term $S/n$ should be about $n+k$(*) if the null is true but will tend to be larger otherwise). As $n$ grows very large relative to $k$ this may become an issue; specifically, computing something akin to $(1+k/n) - 1$ may be inaccurate if $k/n$ is very small. 
At the same time if $n$ is really large, $S$ may be large relative to the increment in $S$. Ideally we avoid both issues by adjusting the S-calculation.
I believe the same sort of idea used in online variance update calculations could be adapted to this computation in that case, it would slightly complicate the update of $S$ - in a way that it's already reduced by $n^2$ (or something close to it).
Actually I think we just add something like $(2O_i+1)/p_i - 2n-1$ to $S$ instead and don't subtract $n$ at the final step (or it may be $-2n+1$ depending on when we update $n$).
(However if $n$ is only a few million it's probably not worth it; if you have several figures of accuracy on your statistic - and you should have plenty to spare - it will probably be sufficient to your purposes. If $n$ is many billions, you should do it but you will want to consider efficiency of the update pretty carefully then)
* actually, n+k-1 but that matters not in the least to the issue.
