@Override
    public ObjectInspector init(Mode m, ObjectInspector[] parameters) throws HiveException {
      super.init(m, parameters);

      // init input object inspectors
      if (m == Mode.PARTIAL1 || m == Mode.COMPLETE) {
        assert(parameters.length == 2);
        inputOI = (PrimitiveObjectInspector) parameters[0];
        nbinsOI = (PrimitiveObjectInspector) parameters[1];
      } else {
        loi = (ListObjectInspector) parameters[0];
      }

      // init output object inspectors
      if (m == Mode.PARTIAL1 || m == Mode.PARTIAL2) {
        // The output of a partial aggregation is a list of doubles representing the
        // histogram being constructed. The first element in the list is the user-specified
        // number of bins in the histogram, and the histogram itself is represented as (x,y)
        // pairs following the first element, so the list length should *always* be odd.
        return ObjectInspectorFactory.getStandardListObjectInspector(
                 PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);
      } else {
        // The output of FINAL and COMPLETE is a full aggregation, which is a
        // list of DoubleWritable structs that represent the final histogram as
        // (x,y) pairs of bin centers and heights.
        ArrayList<ObjectInspector> foi = new ArrayList<ObjectInspector>();
        foi.add(PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);
        foi.add(PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);
        ArrayList<String> fname = new ArrayList<String>();
        fname.add("x");
        fname.add("y");

        return ObjectInspectorFactory.getStandardListObjectInspector(
                 ObjectInspectorFactory.getStandardStructObjectInspector(fname, foi) );
      }
    }
Construct a histogram using an algorithm described by Ben-Haim and Tom-Tov.

The algorithm is a heuristic adapted from the following paper:
Yael Ben-Haim and Elad Tom-Tov, "A streaming parallel decision tree algorithm",
J. Machine Learning Research 11 (2010), pp. 849--872. Although there are no approximation
guarantees, it appears to work well with adequate data and a large (e.g., 20-80) number
of histogram bins.
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFHistogramNumeric.java