It was published, in the Elsevier journal 'Information Sciences' in 1999.
It appears to be the first, and the first large, collection of statistical hypothesis tests that are both multi-dimensional and distribution-free.
I try to be anonymous here at HN, but I'm willing enough to send a PDF of the paper to anyone who wants a copy. E.g., ask for a copy and leave your e-mail address on your HN profile, at least temporarily.
The main point of the paper is that we do get an hypothesis test. In particular, we get to select false alarm rate and then get that rate essentially exactly in practice.
It's behavioral monitoring -- it assumes that the past and future of healthy performance are, to be simple, statistically the same. So, right, its for a server farm or network that is statistically relatively stable, that is statistically unchanging, in what it is doing. The site can be wild and crazy, but it has to continue to be wild and crazy in statistically the same way.
In particular, the work is for detecting zero day problems, that is, problems never seen before. Maybe the philosophy here is that when we get a new problem and detect it, then we fix the cause of the problem and never see it again and, then, again are left looking for zero day problems.
Then the work uses past data -- hypothesis tests have done that since Karl Pearson 100+ years ago, and now parts of computer science do something similar and call it training data in unsupervised learning or some such. The approaches of just statistical hypothesis testing make more sense to me.
The key, core mathematical argument is a finite algebraic group of measure preserving transformations on the data. I believe that there are connections with U-statistics, e.g., as in an advanced statistics book by Serflng.
This stuff with groups and measure preserving is a little like some classic arguments in ergodic theory. On the page, the math looks awful, but actually it is conceptually quite simple.
But, you don't need to dig into the math too much.
For the actual calculations, those are based on nearest neighbors (although other options also work with the basic math). At least since the paper, others have thought of using nearest neighbors, but they didn't have an hypothesis test because they didn't know how to calculate and adjust false alarm rate. So, they have an heuristic instead of an hypothesis test. So, again, the main contribution of the paper is that it really is an hypothesis test, that is, know and get to adjust false alarm rate (conditioned on the old data and also true in long run expectation over the conditioned work -- standard result in conditional expectation from the Radon-Nikodym theorem in measure theory).
For detection rate, there is some good news, not as good as from the classic Neyman-Pearson result (in practice in the context we don't have enough data to do much with Neyman-Person), but nice: In a useful sense, for the selected false alarm rate, the work gives the highest possible detection rate. Really the mathematical key here is just Fubini's theorem (the measure theory version of interchange of order of integration). Intuitively, the technique has the largest area where alarms are raised consistent with the selected false alarm rate.
For the practical application, do need some help with some computational geometry. For that, I dreamed up some work. Soon I found that part of what I dreamed up was k-D trees, e.g., as in Sedgewick's book on algorithms. But there is more -- need some cutting planes. I programmed most of it 20+ years ago in PL/I but finally dropped it due to lack of interest.
I have some ideas for more results of interest and more papers, but after 20+ years of no interest I just gave up.
More can be said, but I stopped the research when I discovered, about 20 years ago, that no one was interested. The paper was published in 1999, and since then interest has been quieter than the tombs of ancient Egypt. So, I'm doing a startup that is quite different.
I dreamed up the work when I saw the need, or at least as I regarded the need, way back in about 1990 when I was in an AI group at the IBM Watson lab doing work on monitoring and management of large server farms and networks. The AI work was trying to build on essentially just threshold detectors. There was no attention to false alarm rate or a best detector -- highest detection rate for given false alarm rate. The classic Neyman-Pearson result was ignored. I was our guy with GM Research, and we gave a paper at the Stanford AAAI IAAI conference. But I was outraged by the lack of concern for false alarm rate, ignoring hypothesis tests and distribution free hypothesis tests (long common in the social sciences), and with no attention at all to multi-dimensional data.
The real world context is just awash in multi-dimensional data. Treating the data components separately in effect says that the geometrical region of healthy behavior is just a box. Bummer. Box too small -- get false alarm rate too large. Box too big, get too many missed detections. Problem: A box is a poor fit to reality. Simple stuff.
How to see this? Monitor CPU busy and page faults per second and look for anomalies, e.g., thrashing, a program allocating infinite memory, etc. Then the normal behavior is just a 2-D box? I don't think so! But, sure, need to automate picking the shape of the region of healthy behavior.
For the distribution-free stuff, that is where we make no assumptions about probability distributions. I got a kick in the back side on that sitting one day in the office of Ulf Grenander, one of the world's best ever statisticians, at Brown (I got accepted to grad school there; was considering going; went elsewhere instead). Grenander had been looking at computer performance data and was shocked at how different it was from the data, e.g., biomedical, he had been used to. So, right, Gaussian assumptions and more go out the window!
So, really, just want to make no assumptions about distributions, want to be distribution-free (a.k.a., non-parametric although I believe distribution-free is more appropriate terminology).
For multi-dimensional, at IBM I got a slap in the face: There was a cluster of computers doing transaction processing. There was some front end load leveling that sent the next transaction to the least busy computer in the cluster. Okay. But one day one of the computers got sick, just a little sick in the head, and was doing a very silly thing -- it was throwing all its incoming transaction work into the bit bucket! Thus, this computer looked to the load leveling as not very busy and, thus, was getting nearly all the transactions. Thus, nearly all the transactions for the whole cluster were going into the bit bucket. Bummer.
So, I thought, to detect this anomaly, want somehow to look at all of the computers in the cluster at the same time and compare them with each other, that is, have all the data in some appropriate region in some space of several dimensions, a region that works whether the cluster is busy or not. So, want to be multi-dimensional, that is, don't want just threshold detectors on variables one at a time.
There are more war stories where the importance of being multi-dimensional is crucial. Really, commonly separating multi-dimensional data into its components and treating the components separately can be throwing away a lot of crucial information which stands to give a poor combination of false alarm rate and detection rate.
Heck, in principle the region of healthy performance can be a fractal, say, like the Mandelbrot set, and, so, somehow we need to approximate that. Can we do that? Basically with nearest neighbor, or k-nearest neighbors (which also works), yes.
There is now a good opportunity for my work: My work can use a LOT of training data, and in the near real-time detection work can want to do a lot with that data. So, could use fast access to a lot of data which doesn't change very fast. So, sure, use some big solid state disks (SSDs)! A few of the Samsung 14 TB drives should do wonders for my paper!
My view is, anyone doing monitoring of a large server farm or network and not using what is in my paper is not being fully serious. And, since get to adjust false alarm rate, say, to one a month, can't say that can't afford the extra false alarms.
Uh, I left out: For each alarm, get told the lowest false alarm rate at which the real-time input data is still an alarm -- so get an indication of alarm seriousness.
More is possible, but at least have to be using what I cooked up in 1990, wrote prototype software for in the early 1990s, and published in 1999.
I did the work a long time ago, guys! And since then, there have been various serious consequences from anomalies, intrusions, etc. Maybe in some of those cases, my work would have done good, early detection. My work looks a heck of a lot better than anything else!