Source file owl_countmin_sketch_sig.ml

# 1 "src/base/misc/owl_countmin_sketch_sig.ml"
(* An implementation of the Count-Min sketch introduced by
 * Cormode and Muthukrishnan. The Count-Min sketch provides an approximate
 * frequency table whose space and time complexity are independent of the
 * number of elements inserted.  It provides the following guarantee:
 * - Estimated frequency >= True frequency
 * - With probability at least 1 - delta:
 *      Estimated frequency - True frequency < epsilon * L
 * where L is the L1 norm of the data entered, equal to the total number of
 * times `incr` has been called.
 * Space usage will be O((1/epsilon) log (1/delta)) and the time to complete
 * `incr` or `count` will be O(log(1/delta)).
 * Refer to http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
 * for more details. *)

module type Sig = sig
  (** {5 Type definition} *)

  type 'a sketch
  (** The type of Count-Min sketches *)

  (** {5 Core functions} *)

  val init : epsilon:float -> delta:float -> 'a sketch
  (**
``init epsilon delta`` initializes a sketch with approximation ratio
``(1 + epsilon)`` and failure probability ``delta``.
  *)

  val incr : 'a sketch -> 'a -> unit
  (** ``incr s x`` increments the frequency count of ``x`` in sketch ``s`` in-place. *)

  val count : 'a sketch -> 'a -> int
  (** ``count s x`` returns the estimated frequency of element ``x`` in ``s``. *)

  val init_from : 'a sketch -> 'a sketch
  (** 
  ``init_from s`` initializes a new empty sketch with the same parameters as ``s``, which
  can later be merged with ``s``.
  *)

  val merge : 'a sketch -> 'a sketch -> 'a sketch
  (** 
  ``merge s1 s2`` returns a new sketch whose counts are the sum of those in ``s1`` and ``s2``.
  Raises ``INVALID_ARGUMENT`` if the parameters of ``s1`` and ``s2`` do not match.
  *)
end