Construction Issues
The above example is a simple one. There are only 7 choices of bucket boundaries. One could compute the cumulative variance for all 7 options easily and choose the absolute best placement. However, as the range of values gets larger and the number of buckets gets larger, the set of possible histograms grows exponentially and it becomes a dauntingly complex problem to find the set of boundaries that provide the absolute minimum variance. A solution is to give up on finding the absolute best solution and attempt to find a good solution instead. By creating random solutions, using those as a starting point and improving upon them, one can find a solution that is a fair approximation of the "best" solution. One construction method used to get around this problem is the Iterative Improvement algorithm. Another is Simulated Annealing. The two may be combined in Two Phase Optimization, or 2PO. These algorithms are put forth in "Randomized Algorithms..." (cited below) as a method to optimize queries, but the general idea may be applied to construction of V-optimal Histograms.
Read more about this topic: V-optimal Histograms
Famous quotes containing the words construction and/or issues:
“There’s no art
To find the mind’s construction in the face:
He was a gentleman on whom I built
An absolute trust.”
—William Shakespeare (1564–1616)
“The current flows fast and furious. It issues in a spate of words from the loudspeakers and the politicians. Every day they tell us that we are a free people fighting to defend freedom. That is the current that has whirled the young airman up into the sky and keeps him circulating there among the clouds. Down here, with a roof to cover us and a gasmask handy, it is our business to puncture gasbags and discover the seeds of truth.”
—Virginia Woolf (1882–1941)