Variations of V-optimal Histograms
The idea behind V-optimal histograms is to minimize the variance inside each bucket. In considering this, a thought occurs that the variance of any set with one member is 0. This is the idea behind "End-Biased" V-optimal Histograms. The value with the highest frequency is always placed in its own bucket. This ensures that the estimate for that value (which is likely to be the most frequently requested estimate, since it's the most frequent value) will always be accurate and also removes the value most likely to cause a high variance from the data set.
Another thought that might occur is that variance would be reduced if one were to sort by frequency, instead of value. This would naturally tend to place like values next to each other. Such a histogram can be constructed by using a Sort Value of Frequency and a Source Value of Frequency. At this point, however, the buckets must carry additional information indicating what data values are present in the bucket. These histograms have been shown to be less accurate, due to the additional layer of estimation required.
Read more about this topic: V-optimal Histograms
Famous quotes containing the word variations:
“I may be able to spot arrowheads on the desert but a refrigerator is a jungle in which I am easily lost. My wife, however, will unerringly point out that the cheese or the leftover roast is hiding right in front of my eyes. Hundreds of such experiences convince me that men and women often inhabit quite different visual worlds. These are differences which cannot be attributed to variations in visual acuity. Man and women simply have learned to use their eyes in very different ways.”
—Edward T. Hall (b. 1914)