Maintaining a container of objects sorted by the difference between that object's member and its neighbor's member

Question

I'm working on implementing a histogram, and one of the key points is the quick merging of histogram bins. Because I don't have a priori knowledge of the data set being approximated by the histogram, I need to come up with a way that quickly merges neighboring bins, after I've exceeded the maximum number of bins.

So, as an example, if you're approximating a data stream 23, 19, 10, 16, 36, 2, 9, 32, 30, 45 with five histogram bins, you'd read in the first five elements, obtaining:

(23, 1), (19,1), (10,1), (16,1), (36,1)

Adding the bin (2,1) causes an issue, since we've exceeded the maximum number of bins. So, we add (2,1) and merge the two closest bins -- (16,1) and (19,1) -- to get a new bin (17.5,2) that replaces those two.

Repeating this method for the rest of the histogram gives us the final output:

(2,1), (9.5,2), (19.33,3), (32.67,3), (45,1).

Implementing this without respect for complexity issues is trivial. However, I'm really concerned about optimizing this for large data sets, because my "trivial" implementation ends up taking 15 seconds to run on a stream of 100,000 gaussian distributed values.

My current thought is to use boost::multi_index to keep track of my HistogramBin struct, which is defined as:

struct HistogramBin
{
    double bin;
    unsigned long count;
    bool isNull;

    HistogramBin(double x, bool n = false)
    : bin(x), count(1), isNull(n) {}

    bool operator<(const HistogramBin &other) const
    { return (bin < other.bin); }

    // Merges other with this histogram bin
    // E.g., if you have (2.0,1) and (3.0,2), you'd merge them into (2.67,3)
    void merge(const HistogramBin &other)
    {
        unsigned long old_count = count;
        count += other.count;
        bin = (bin*old_count + other.bin*other.count)/count;
    }

    // Gets the difference between two histogram bins
    const double getDifference(const HistogramBin &other) const
    { return (double)abs(bin - other.bin); }
};

So, the multi_index would use ordered_unique<> to sort on HistogramBin::bin.

Now, this doesn't resolve the issue of sorting the bins by the differences between neighboring bins. Indexing by HistogramBin::bin gives us an ordered list of HistogramBin objects, but then the next step is to calculate the difference between the current bin and the next one, and then to sort on those values as well.

Is there any way to sort on those values, while maintaining the integrity of the list, and without introducing a new container (such as a multimap of difference/iterator key/value pairs)?

Maintaining this list is my current idea on a near-optimal solution to the complexity problem, because it only needs to be changed when there's a merge, and a merge only happens when a new value is added.

Any thoughts or insight would be appreciated.

Answer 1

The main problem I see, is that you have created a system where you are constantly recalculating the histogram, in worst case for every new element.

What about something like this:

1. For N bins, Bin_min to Bin_max, assign them to the initial value of your input
2. For each new number X, if X is < Bin_min set Bin_min = X else if X > Bin_max set Bin_max = X
3. If you changed the boundaries in 2, set each bin's value such that Bin_L = (Bin_max - Bin_min) / N * L, where L is the bin ordinal
4. Add X to bin with closest value to X.

This is back of the napkin, so I'm sure there is a mistake somewhere. The idea is to only 'refactor' the histogram when a value falls outside of it, so your normal case all you need to do is add X to the bin that most closely matches it. I believe this should result in a very similar histogram if not equivalent. Step 1 is your initialization, steps 2-4 are a loop, if it's not clear.