In the field of web analytics, how can one calculate the statistical significance of a metric (for instance Repeat Visitor's). Imagine that we have millions of visitors daily and we are registering each visit, through cookies maybe. We store data per visit/visitor in a relational database and want to show a number for interesting metrics on demand in a report. Performance is an issue here, so we need fast queries and computations. Also we don't want to make any assumptions, about the data distribution (definitely not binomial for all metrics). What are the best relevant techniques to solve this problem?
Could you elaborate on why you're worried about the performance of the analysis code? I completely understand why you'd need a highly tuned database for collecting the data if you're getting millions of hits every day. On the other hand, if you're doing the usual sorts of traffic analysis, you probably don't want to re-run the entire analysis for each visitor. In addition to being overkill, that might set you up for some nasty multiple comparisons issues if, for example, you keep rerunning an A-B test until you get a significant result.
Instead, you might want to analyze snapshots of your data. That shouldn't require a ton of computing power. Just to put some numbers on it, I ran some basic analyses on 10 million data points using matlab on my (somewhat older) computer. Linear regression, T tests and sign-rank tests took about a second each; ANOVAs were a little longer (~10 seconds). Permutation tests took a while, but most of that was generating the permutations (and could probably be sped up).
Furthermore, you probably don't even need to keep all the data around. For example, the classic binomial tests just need the proportions and counts. Similarly, a t-test just requires means and variances, which are easy enough to compute online. In fact, you could have triggers on your database update the means/proportions/variances/etc on insert, which would make those analyses pretty much instantaneous.