Add notes about which classes require a serde and which use python built-in object methods
diff --git a/docs/source/ebpps.rst b/docs/source/ebpps.rst index 265fa02..b225320 100644 --- a/docs/source/ebpps.rst +++ b/docs/source/ebpps.rst
@@ -1,6 +1,8 @@ Exact and Bounded, Probabilitiy Proportional to Size (EBPPS) Sampling --------------------------------------------------------------------- +.. currentmodule:: datasketches + An EBPPS sketch produces a randome sample of data from a stream of items, ensuring that the probability of including an item is always exactly equal to the item's size. The size of an item is defined as its weight relative to the total weight of all items seen so far by the sketch. In contrast to VarOpt sampling, @@ -14,7 +16,10 @@ EBPPS sampling is related to reservoir sampling, but handles unequal item weights. Feeding the sketch items with a uniform weight value will produce a sample equivalent to reservoir sampling. -.. autoclass:: datasketches.ebpps_sketch +.. note:: + Serializing and deserializing this sketch requires the use of a :class:`PyObjectSerDe`. + +.. autoclass:: ebpps_sketch :members: :undoc-members: :exclude-members: deserialize
diff --git a/docs/source/frequent_items.rst b/docs/source/frequent_items.rst index 6fef7ae..a8f5a29 100644 --- a/docs/source/frequent_items.rst +++ b/docs/source/frequent_items.rst
@@ -1,6 +1,8 @@ Frequent Items -------------- +.. currentmodule:: dataskethches + This sketch is useful for tracking approximate frequencies of items of type `<T>` with optional associated counts `(<T> item, int count)` that are members of a multiset of such items. The true frequency of an item is defined to be the sum of associated counts. @@ -16,21 +18,21 @@ **Space Usage** -The sketch is initialized with a maximum map size, `maxMapSize`, that specifies the maximum physical length of the internal hash map of the form `(<T> item, int count)`. -The maximum map size is always a power of 2, defined through the variables `lg_max_map_size`. +The sketch is initialized with a maximum map size, ``maxMapSize``, that specifies the maximum physical length of the internal hash map of the form ``(object item, int count)``. +The maximum map size is always a power of 2, defined through the variables ``lg_max_map_size``. The hash map starts at a very small size (8 entries) and grows as needed up to the specified maximum map size. -Excluding external space required for the item objects, the internal memory space usage of this sketch is `18 * mapSize bytes` (assuming 8 bytes for each reference), +Excluding external space required for the item objects, the internal memory space usage of this sketch is `18 * ``mapSize`` bytes` (assuming 8 bytes for each reference), plus a small constant number of additional bytes. -The internal memory space usage of this sketch will never exceed `18 * maxMapSize` bytes, plus a small constant number of additional bytes. +The internal memory space usage of this sketch will never exceed `18 * ``maxMapSize`` ` bytes, plus a small constant number of additional bytes. **Maximum Capacity of the Sketch** -The `LOAD_FACTOR` for the hash map is internally set at :math:`75\%`, which means at any time the map capacity of `(item, count)` pairs is `mapCap = 0.75 * mapSize`. -The maximum capacity of `(item, count)`` pairs of the sketch is `maxMapCap = 0.75 * maxMapSize`. +The ``LOAD_FACTOR`` for the hash map is internally set at :math:`75\%`, which means at any time the map capacity of ``(item, count)`` pairs is ``mapCap = 0.75 * mapSize``. +The maximum capacity of ``(item, count)`` pairs of the sketch is `maxMapCap = 0.75 * maxMapSize`. -**Updating the sketch with `(item, count)` pairs** +**Updating the sketch with ``(item, count)`` pairs** If the item is found in the hash map, the mapped count field (the "counter") is incremented by the incoming count; otherwise, a new counter `"(item, count) pair"` is created. If the number of tracked counters reaches the maximum capacity of the hash map, the sketch decrements all of the counters (by an approximately computed median) @@ -38,16 +40,16 @@ **Accuracy** -If fewer than `0.75 * maxMapSize` different items are inserted into the sketch, the estimated frequencies returned by the sketch will be exact. +If fewer than ``0.75 * maxMapSize`` different items are inserted into the sketch, the estimated frequencies returned by the sketch will be exact. The logic of the frequent items sketch is such that the stored counts and true counts are never too different. More specifically, for any item, the sketch can return an estimate of the true frequency of item, along with upper and lower bounds on the frequency (that hold deterministically). For this implementation and for a specific active item, it is guaranteed that the true frequency will be between the Upper Bound (UB) and the Lower Bound (LB) computed for that item. -Specifically, `(UB- LB) ≤ W * epsilon`, where :math:`W` denotes the sum of all item counts, and :math:`epsilon = 3.5/M`, where :math:`epsilon = M` is the maxMapSize. +Specifically, ``(UB- LB) ≤ W * epsilon``, where :math:`W` denotes the sum of all item counts, and :math:`epsilon = 3.5/M`, where :math:`epsilon = M` is the maxMapSize. This is a worst-case guarantee that applies to arbitrary inputs. -For inputs typically seen in practice, `(UB-LB)` is usually much smaller. +For inputs typically seen in practice, ``(UB-LB)`` is usually much smaller. **Background** @@ -63,14 +65,19 @@ For speed, we do employ some randomization that introduces a small probability that our proof of the worst-case bound might not apply to a given run. However, we have ensured that this probability is extremely small. For example, if the stream causes one table purge (rebuild), our proof of the worst-case bound applies with a probability of at least `1 - 1E-14`. -If the stream causes `1E9` purges, our proof applies with a probability of at least `1 - 1E-5`. +If the stream causes ``1E9`` purges, our proof applies with a probability of at least ``1 - 1E-5``. There are two flavors of Frequent Items Sketches, one with generic items (objects) and another specific to strings. The string version is a legacy name from before the library supported generic objects and is retained only for backwards compatibility. +.. note:: + The :class:`frequent_items_sketch` uses an input object's ``__hash__`` and ``__eq__`` methods. -.. autoclass:: _datasketches.frequent_items_error_type +.. note:: + Serializing and deserializing the :class:`frequent_items_sketch` requires the use of a :class:`PyObjectSerDe`. + +.. autoclass:: frequent_items_error_type .. autoattribute:: NO_FALSE_POSITIVES :annotation: : Returns only true positives but may miss some heavy hitters. @@ -79,7 +86,7 @@ :annotation: : Does not miss any heavy hitters but may return false positives. -.. autoclass:: _datasketches.frequent_items_sketch +.. autoclass:: frequent_items_sketch :members: :undoc-members: :exclude-members: deserialize, get_epsilon_for_lg_size, get_apriori_error @@ -96,7 +103,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.frequent_strings_sketch +.. autoclass:: frequent_strings_sketch :members: :undoc-members: :exclude-members: deserialize, get_epsilon_for_lg_size, get_apriori_error
diff --git a/docs/source/kll.rst b/docs/source/kll.rst index 492598a..0e54b44 100644 --- a/docs/source/kll.rst +++ b/docs/source/kll.rst
@@ -1,5 +1,8 @@ KLL Sketch ---------- + +.. currentmodule:: datasketches + Implementation of a very compact quantiles sketch with lazy compaction scheme and nearly optimal accuracy per retained item. See `Optimal Quantile Approximation in Streams`. @@ -106,7 +109,11 @@ .. note:: For the :class:`kll_items_sketch`, objects must be comparable with ``__lt__``. -.. autoclass:: _datasketches.kll_ints_sketch +.. note:: + Serializing and deserializing a :class:`kll_items_sketch` requires the use of a :class:`PyObjectSerDe`. + + +.. autoclass:: kll_ints_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error @@ -120,7 +127,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.kll_floats_sketch +.. autoclass:: kll_floats_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error @@ -134,7 +141,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.kll_doubles_sketch +.. autoclass:: kll_doubles_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error @@ -148,7 +155,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.kll_items_sketch +.. autoclass:: kll_items_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error
diff --git a/docs/source/quantiles_depr.rst b/docs/source/quantiles_depr.rst index c54598e..18dd5df 100644 --- a/docs/source/quantiles_depr.rst +++ b/docs/source/quantiles_depr.rst
@@ -1,7 +1,11 @@ Quantiles Sketch (Deprecated) ----------------------------- + +.. currentmodule:: datasketches + This is a deprecated quantiles sketch that is included for cross-language compatibility. -Most new projects will favor the KLL sketch over this one. +Most new projects will favor the KLL sketch over this one, or the REQ sketch for higher accuracy +at the very edge of a distribution. This is a stochastic streaming sketch that enables near-real time analysis of the approximate distribution from a very large stream in a single pass. @@ -42,7 +46,10 @@ .. note:: For the :class:`quantiles_items_sketch`, objects must be comparable with ``__lt__``. -.. autoclass:: _datasketches.quantiles_ints_sketch +.. note:: + Serializing and deserializing a :class:`quantiles_items_sketch` requires the use of a :class:`PyObjectSerDe`. + +.. autoclass:: quantiles_ints_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error @@ -56,7 +63,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.quantiles_floats_sketch +.. autoclass:: quantiles_floats_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error @@ -70,7 +77,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.quantiles_doubles_sketch +.. autoclass:: quantiles_doubles_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error @@ -84,7 +91,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.quantiles_items_sketch +.. autoclass:: quantiles_items_sketch :members: :undoc-members: :exclude-members: deserialize, get_normalized_rank_error
diff --git a/docs/source/req.rst b/docs/source/req.rst index 68fc6be..3f63e01 100644 --- a/docs/source/req.rst +++ b/docs/source/req.rst
@@ -1,5 +1,8 @@ Relative Error Quantiles (REQ) Sketch ------------------------------------- + +.. currentmodule:: datasketches + This is an implementation based on the `paper <https://arxiv.org/abs/2004.01668>`_ "Relative Error Streaming Quantiles" by Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý, and loosely derived from a Python prototype written by Pavel Veselý. This implementation differs from the algorithm described in the paper in the following: @@ -30,7 +33,10 @@ .. note:: For the :class:`req_items_sketch`, objects must be comparable with ``__lt__``. -.. autoclass:: _datasketches.req_ints_sketch +.. note:: + Serializing and deserializing a :class:`req_items_sketch` requires the use of a :class:`PyObjectSerDe`. + +.. autoclass:: req_ints_sketch :members: :undoc-members: :exclude-members: deserialize, get_RSE @@ -44,7 +50,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.req_floats_sketch +.. autoclass:: req_floats_sketch :members: :undoc-members: :exclude-members: deserialize, get_RSE @@ -58,7 +64,7 @@ .. automethod:: __init__ -.. autoclass:: _datasketches.req_items_sketch +.. autoclass:: req_items_sketch :members: :undoc-members: :exclude-members: deserialize, get_RSE
diff --git a/docs/source/tuple.rst b/docs/source/tuple.rst index 86ebdfa..e4a369f 100644 --- a/docs/source/tuple.rst +++ b/docs/source/tuple.rst
@@ -15,6 +15,9 @@ Several `Jaccard similarity <https://en.wikipedia.org/wiki/Jaccard_similarity>`_ measures can be computed between theta sketches with the :class:`tuple_jaccard_similarity` class. +.. note:: + Serializing and deserializing this sketch requires the use of a :class:`PyObjectSerDe`. + .. autoclass:: tuple_sketch :members: :undoc-members:
diff --git a/docs/source/varopt.rst b/docs/source/varopt.rst index 5c5f728..d837835 100644 --- a/docs/source/varopt.rst +++ b/docs/source/varopt.rst
@@ -1,6 +1,8 @@ Variance Optimal Sampling (VarOpt) ---------------------------------- +.. currentmodule:: datasketches + A VarOpt sketch samples data from a stream of items. The sketch is desinged for optimal (minimum) variance when querying the sketch to estimate subset sums of items matching a provided predicate. The sketch will produce a sample of size `k` (or smaller if fewer items have been presented), with @@ -10,7 +12,10 @@ VarOpt sampling is related to reservoir sampling, with improved error bounds for subset sum estimation. Feeding the sketch items with a uniform weight value will produce a sample equivalent to reservoir sampling. -.. autoclass:: datasketches.var_opt_sketch +.. note:: + Serializing and deserializing this sketch requires the use of a :class:`PyObjectSerDe`. + +.. autoclass:: var_opt_sketch :members: :undoc-members: :exclude-members: deserialize @@ -23,7 +28,7 @@ .. automethod:: __init__ -.. autoclass:: datasketches.var_opt_union +.. autoclass:: var_opt_union :members: :undoc-members: :exclude-members: deserialize