tdigest.h

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

// approximate quantiles from arbitrary length dataset with O(1) space
// based on 'Computing Extremely Accurate Quantiles Using t-Digests' from Dunning & Ertl
// - https://arxiv.org/abs/1902.04023
// - https://github.com/tdunning/t-digest

#pragma once

#include <cmath>
#include <memory>
#include <vector>

#include "arrow/util/logging.h"
#include "arrow/util/macros.h"
#include "arrow/util/visibility.h"

namespace arrow {

class Status;

namespace internal {

class ARROW_EXPORT TDigest {
 public:
  explicit TDigest(uint32_t delta = 100, uint32_t buffer_size = 500);
  ~TDigest();
  TDigest(TDigest&&);
  TDigest& operator=(TDigest&&);

  // reset and re-use this tdigest
  void Reset();

  // validate data integrity
  Status Validate() const;

  // dump internal data, only for debug
  void Dump() const;

  // buffer a single data point, consume internal buffer if full
  // this function is intensively called and performance critical
  // call it only if you are sure no NAN exists in input data
  void Add(double value) {
    ARROW_DCHECK(!std::isnan(value)) << "cannot add NAN";
    if (ARROW_PREDICT_FALSE(input_.size() == input_.capacity())) {
      MergeInput();
    }
    input_.push_back(value);
  }

  // skip NAN on adding
  template <typename T>
  typename std::enable_if<std::is_floating_point<T>::value>::type NanAdd(T value) {
    if (!std::isnan(value)) Add(value);
  }

  template <typename T>
  typename std::enable_if<std::is_integral<T>::value>::type NanAdd(T value) {
    Add(static_cast<double>(value));
  }

  // merge with other t-digests, called infrequently
  void Merge(const std::vector<TDigest>& others);
  void Merge(const TDigest& other);

  // calculate quantile
  double Quantile(double q) const;

  double Min() const { return Quantile(0); }
  double Max() const { return Quantile(1); }
  double Mean() const;

  // check if this tdigest contains no valid data points
  bool is_empty() const;

 private:
  // merge input data with current tdigest
  void MergeInput() const;

  // input buffer, size = buffer_size * sizeof(double)
  mutable std::vector<double> input_;

  // hide other members with pimpl
  class TDigestImpl;
  std::unique_ptr<TDigestImpl> impl_;
};

}  // namespace internal
}  // namespace arrow