You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by jm...@apache.org on 2024/01/13 02:21:44 UTC
(datasketches-python) 02/04: add most helper classes
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch expand_docs
in repository https://gitbox.apache.org/repos/asf/datasketches-python.git
commit edcd1c4ce236abfed10f88285003731d931dc27b
Author: Jon Malkin <78...@users.noreply.github.com>
AuthorDate: Fri Jan 12 17:15:34 2024 -0800
add most helper classes
---
datasketches/KernelFunction.py | 6 ++++-
datasketches/PySerDe.py | 4 +--
datasketches/TuplePolicy.py | 13 +++++----
docs/source/density_sketch.rst | 11 ++++----
docs/source/ebpps.rst | 28 +++++++++++++++++++
docs/source/index.rst | 4 +++
docs/source/jaccard.rst | 23 ++++++++++++++++
docs/source/kernel.rst | 21 +++++++++++++++
docs/source/serde.rst | 34 +++++++++++++++++++++++
docs/source/theta.rst | 55 +++++++++++++++++++++++++++++++++++--
docs/source/tuple.rst | 61 +++++++++++++++++++++++++++++++++++-------
docs/source/tuple_policy.rst | 25 +++++++++++++++++
docs/source/varopt.rst | 37 +++++++++++++++++++++++++
src/density_wrapper.cpp | 9 ++++---
src/py_serde.cpp | 8 +++---
src/theta_wrapper.cpp | 6 ++---
src/tuple_wrapper.cpp | 17 +++++++++---
17 files changed, 324 insertions(+), 38 deletions(-)
diff --git a/datasketches/KernelFunction.py b/datasketches/KernelFunction.py
index a8f65a3..b78c0b3 100644
--- a/datasketches/KernelFunction.py
+++ b/datasketches/KernelFunction.py
@@ -24,8 +24,12 @@ from _datasketches import KernelFunction
# Each implementation must extend the KernelFunction class
# and define the __call__ method
-# Implements a basic Gaussian Kernel
class GaussianKernel(KernelFunction):
+ '''Implements a basic Gaussian kernel
+
+ :param bandwidth: The kernel bandwidth, default 1.0
+ :type bandwidth: float
+ '''
def __init__(self, bandwidth: float=1.0):
KernelFunction.__init__(self)
self._bw = bandwidth
diff --git a/datasketches/PySerDe.py b/datasketches/PySerDe.py
index 6c3a926..fcaddfe 100644
--- a/datasketches/PySerDe.py
+++ b/datasketches/PySerDe.py
@@ -34,10 +34,10 @@ import struct
class PyStringsSerDe(PyObjectSerDe):
'''Implements a simple string-encoding scheme where a string is
- written as <num_bytes> <string_contents>, with no null termination.
+ written as `<num_bytes> <string_contents>`, with no null termination.
This format allows pre-allocating each string, at the cost of
additional storage. Using this format, the serialized string consumes
- 4 + len(item) bytes.'''
+ ``4 + len(item)`` bytes.'''
def get_size(self, item):
return int(4 + len(item))
diff --git a/datasketches/TuplePolicy.py b/datasketches/TuplePolicy.py
index adc794a..760ebb7 100644
--- a/datasketches/TuplePolicy.py
+++ b/datasketches/TuplePolicy.py
@@ -22,16 +22,17 @@ from _datasketches import TuplePolicy
# This file provides an example Python Tuple Policy implementation.
#
# Each implementation must extend the PyTuplePolicy class and define
-# two methods:
+# the following methods:
# * create_summary() returns a new Summary object
# * update_summary(summary, update) applies the relevant policy to update the
# provided summary with the data in update.
# * __call__ may be similar to update_summary but allows a different
# implementation for set operations (union and intersection)
-# Implements an accumulator summary policy, where new values are
-# added to the existing value.
class AccumulatorPolicy(TuplePolicy):
+ '''Implements an accumulatory summary policy, where new values
+ are added to the existing value.'''
+
def __init__(self):
TuplePolicy.__init__(self)
@@ -47,8 +48,9 @@ class AccumulatorPolicy(TuplePolicy):
return summary
-# Implements a MAX rule, where the largest integer value is always kept
class MaxIntPolicy(TuplePolicy):
+ '''Implements a MAX rule, where the largest integer value is always kept.'''
+
def __init__(self):
TuplePolicy.__init__(self)
@@ -62,8 +64,9 @@ class MaxIntPolicy(TuplePolicy):
return max(summary, update)
-# Implements a MIN rule, where the smallest integer value is always kept
class MinIntPolicy(TuplePolicy):
+ '''Implements a MIN rule, where the smallest integer value is always kept.'''
+
def __init__(self):
TuplePolicy.__init__(self)
diff --git a/docs/source/density_sketch.rst b/docs/source/density_sketch.rst
index 529767d..07d8318 100644
--- a/docs/source/density_sketch.rst
+++ b/docs/source/density_sketch.rst
@@ -1,5 +1,8 @@
Density Sketch
--------------
+
+.. currentmodule:: datasketches
+
Builds a coreset from the given set of input points.
Provides density estimate at a given point.
@@ -9,13 +12,9 @@ https://proceedings.mlr.press/v99/karnin19a/karnin19a.pdf
Inspired by the following implementation: https://github.com/edoliberty/streaming-quantiles/blob/f688c8161a25582457b0a09deb4630a81406293b/gde.py
-Requires the use of a `KernelFunction` to compute the distance between two vectors.
-
-.. autoclass:: datasketches.KernelFunction
-
- .. automethod:: __call__
+Requires the use of a :class:`KernelFunction` to compute the distance between two vectors.
-.. autoclass:: datasketches.density_sketch
+.. autoclass:: density_sketch
:members:
:undoc-members:
:exclude-members: deserialize
diff --git a/docs/source/ebpps.rst b/docs/source/ebpps.rst
new file mode 100644
index 0000000..265fa02
--- /dev/null
+++ b/docs/source/ebpps.rst
@@ -0,0 +1,28 @@
+Exact and Bounded, Probabilitiy Proportional to Size (EBPPS) Sampling
+---------------------------------------------------------------------
+
+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,
+this sketch may return fewer than `k` items in order to keep the probability of including an item strictly
+proportional to its size.
+
+This sketch is based on: B. Hentschel, P. J. Haas, Y. Tian
+"Exact PPS Sampling with Bounded Sample Size",
+Information Processing Letters, 2023.
+
+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
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
diff --git a/docs/source/index.rst b/docs/source/index.rst
index a44e873..ab1dae5 100644
--- a/docs/source/index.rst
+++ b/docs/source/index.rst
@@ -73,6 +73,10 @@ Helper Classes
:maxdepth: 1
serde
+ kernel
+ jaccard
+ tuple_policy
+
These classes are required for certain sketches or specific functionality withing sketches.
Some of them are abstract base classes, but in those cases there is at least one reference example of a
diff --git a/docs/source/jaccard.rst b/docs/source/jaccard.rst
new file mode 100644
index 0000000..d3b9bfa
--- /dev/null
+++ b/docs/source/jaccard.rst
@@ -0,0 +1,23 @@
+Jaccard Similarity
+##################
+
+.. currentmodule:: datasketches
+
+These objects provide measures related to the `Jaccard similarity <https://en.wikipedia.org/wiki/Jaccard_similarity>`_
+of :class:`theta_sketch` and :class:`tuple_sketch` objects.
+
+Note that there are separate classes to be used for theta and tuple sketches.
+
+.. autoclass:: theta_jaccard_similarity
+
+ .. automethod:: jaccard
+ .. automethod:: exactly_equal
+ .. automethod:: similarity_test
+ .. automethod:: dissimilarity_test
+
+.. autoclass:: tuple_jaccard_similarity
+
+ .. automethod:: jaccard
+ .. automethod:: exactly_equal
+ .. automethod:: similarity_test
+ .. automethod:: dissimilarity_test
diff --git a/docs/source/kernel.rst b/docs/source/kernel.rst
new file mode 100644
index 0000000..bdc2c72
--- /dev/null
+++ b/docs/source/kernel.rst
@@ -0,0 +1,21 @@
+Kernel Function
+###############
+
+.. currentmodule:: datasketches
+
+A `kernel function <https://en.wikipedia.org/wiki/Positive-definite_kernel>`_ is a specific type of
+mathematical funciton that is particularly useful in certain machine learning and pattern recognition
+contexts. The :class:`density_sketch` performs approximate
+`kernel density estimation <https://en.wikipedia.org/wiki/Kernel_density_estimation>`_ which, unsurprisingly,
+relies on the use of such a kernel function.
+
+The library provides an abstract base class :class:`KernelFunction` and an example implementation of a
+Gaussian (also known as a Radial Basis Function) kernel. Custom classes must override the base class
+and provide a floating point value as a score indicating the similarity of two input vectors.
+
+.. autoclass:: KernelFunction
+
+ .. automethod:: __call__
+
+.. autoclass:: GaussianKernel
+ :show-inheritance:
\ No newline at end of file
diff --git a/docs/source/serde.rst b/docs/source/serde.rst
new file mode 100644
index 0000000..ccac1d8
--- /dev/null
+++ b/docs/source/serde.rst
@@ -0,0 +1,34 @@
+Serialize/Deserialize (SerDe)
+#############################
+
+.. currentmodule:: datasketches
+
+A SerDe is a class used to serialize items sketches to a :class:`bytes` object in binary.
+Several example SerDes are provided as references.
+
+The use of binary-compatible SerDes in different languages is critical for cross-language compatibility.
+
+Each implementation must extend the :class:`PyObjectSerDe` class and override all three of its methods.
+
+.. autoclass:: PyObjectSerDe
+
+ .. automethod:: get_size
+ .. automethod:: to_bytes
+ .. automethod:: from_bytes
+
+
+The provided SerDes are:
+
+.. autoclass:: PyStringsSerDe
+ :show-inheritance:
+
+.. autoclass:: PyIntsSerDe
+ :show-inheritance:
+
+.. autoclass:: PyLongsSerDe
+ :show-inheritance:
+
+.. autoclass:: PyFloatsSerDe
+ :show-inheritance:
+
+.. autoclass:: PyDoublesSerDe
diff --git a/docs/source/theta.rst b/docs/source/theta.rst
index 4593f37..94951f9 100644
--- a/docs/source/theta.rst
+++ b/docs/source/theta.rst
@@ -1,5 +1,10 @@
Theta Sketch
------------
+
+.. currentmodule:: datasketches
+
+Theta sketches are used for distinct counting.
+
The theta package contains the basic sketch classes that are members of the `Theta Sketch Framework <https://datasketches.apache.org/docs/Theta/ThetaSketchFramework.html>`_.
There is a separate Tuple package for many of the sketches that are derived from the same algorithms defined in the Theta Sketch Framework paper.
@@ -9,6 +14,52 @@ Theta sketch is a practical variant of the K-Minimum Values sketch which avoids
hash values on every insertion to the sketch.
It has better error properties than the HyperLogLog sketch for set operations beyond the simple union.
-.. autoclass:: _datasketches.theta_sketch
+Set operations (union, intersection, A-not-B) are performed through the use of dedicated objects.
+
+Several `Jaccard similarity <https://en.wikipedia.org/wiki/Jaccard_similarity>`_
+measures can be computed between theta sketches with the :class:`theta_jaccard_similarity` class.
+
+.. autoclass:: theta_sketch
+ :members:
+ :undoc-members:
+
+.. autoclass:: update_theta_sketch
:members:
- :undoc-members:
\ No newline at end of file
+ :undoc-members:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: compact_theta_sketch
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: theta_union
+ :members:
+ :undoc-members:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: theta_intersection
+ :members:
+ :undoc-members:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: theta_a_not_b
+ :members:
+ :undoc-members:
+
+ .. automethod:: __init__
diff --git a/docs/source/tuple.rst b/docs/source/tuple.rst
index 4bca37f..86ebdfa 100644
--- a/docs/source/tuple.rst
+++ b/docs/source/tuple.rst
@@ -1,18 +1,61 @@
Tuple Sketch
------------
-Tuple sketches are an extension of Theta sketch that allow the keeping of arbitrary summaries associated with each retained key
-(for example, a count for every key).
+.. currentmodule:: datasketches
-.. autoclass:: datasketches.tuple_sketch
+Tuple sketches are an extension of Theta sketches, meaning they provide estimate of distinct counts, that
+allow the keeping of arbitrary summaries associated with each retained key
+(for example, a count for every key). The use of a :class:`tuple_sketch` requires a :class:`TuplePolicy` which
+defines how summaries are created, updated, merged, or intersected. The library provides a few basic
+examples of :class:`TuplePolicy` implementations, but the right custom summary and policy can allow very
+complicated analysis to be performed quite easily.
+
+Set operations (union, intersection, A-not-B) are performed through the use of dedicated objects.
+
+Several `Jaccard similarity <https://en.wikipedia.org/wiki/Jaccard_similarity>`_
+measures can be computed between theta sketches with the :class:`tuple_jaccard_similarity` class.
+
+.. autoclass:: tuple_sketch
:members:
:undoc-members:
+
+.. autoclass:: update_tuple_sketch
+ :members:
+ :undoc-members:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: compact_tuple_sketch
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
-.. autoclass:: datasketches.AccumulatorPolicy
- :members:
-.. autoclass:: datasketches.MaxIntPolicy
- :members:
+.. autoclass:: tuple_union
+ :members:
+ :undoc-members:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: tuple_intersection
+ :members:
+ :undoc-members:
+
+ .. automethod:: __init__
+
+
+.. autoclass:: tuple_a_not_b
+ :members:
+ :undoc-members:
-.. autoclass:: datasketches.MinIntPolicy
- :members:
\ No newline at end of file
+ .. automethod:: __init__
diff --git a/docs/source/tuple_policy.rst b/docs/source/tuple_policy.rst
new file mode 100644
index 0000000..3f5781f
--- /dev/null
+++ b/docs/source/tuple_policy.rst
@@ -0,0 +1,25 @@
+Tuple Policy
+############
+
+.. currentmodule:: datasketches
+
+A Tuple Policy is needed when using a :class:`tuple_sketch` in order to specify how the
+summary values should be created, updated, combined, or intersected. A summary can consist of
+any python object.
+
+Each implementation must extend the abstract base class :class:`TuplePolicy`.
+
+.. autoclass:: TuplePolicy
+
+ .. automethod:: create_summary
+ .. automethod:: update_summary
+ .. automethod:: __call__
+
+.. autoclass:: AccumulatorPolicy
+ :show-inheritance:
+
+.. autoclass:: MinIntPolicy
+ :show-inheritance:
+
+.. autoclass:: MaxIntPolicy
+ :show-inheritance:
diff --git a/docs/source/varopt.rst b/docs/source/varopt.rst
new file mode 100644
index 0000000..5c5f728
--- /dev/null
+++ b/docs/source/varopt.rst
@@ -0,0 +1,37 @@
+Variance Optimal Sampling (VarOpt)
+----------------------------------
+
+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
+the probability of including an item roughly corresponding it the item's weight relative to the total
+weight of all items presented to the sketch.
+
+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
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
+
+.. autoclass:: datasketches.var_opt_union
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
diff --git a/src/density_wrapper.cpp b/src/density_wrapper.cpp
index 1a4ac6d..f77cf22 100644
--- a/src/density_wrapper.cpp
+++ b/src/density_wrapper.cpp
@@ -108,11 +108,14 @@ void init_density(nb::module_ &m) {
// generic kernel function
nb::class_<kernel_function, KernelFunction>(m, "KernelFunction",
- "KernelFunction provicdes a generic base class from which user-defined kernels must inherit. \
- The class contains only a __call__ method that must be overridden.")
+ "A generic base class from which user-defined kernels must inherit.")
.def(nb::init())
.def("__call__", &kernel_function::operator(), nb::arg("a"), nb::arg("b"),
- "A method to evaluate a kernel with given inputs a and b.")
+ "A method to evaluate a kernel with given inputs a and b.\n\n"
+ ":param a: An input vector\n:type a: numpy array\n"
+ ":param b: An input vector\n:type b: numpy array\n"
+ ":return: A vector similarity score\n:rtype: float"
+ )
;
// the old sketch names can almost be defined, but the kernel_function_holder won't work in init()
diff --git a/src/py_serde.cpp b/src/py_serde.cpp
index 3aa0f87..a1896a6 100644
--- a/src/py_serde.cpp
+++ b/src/py_serde.cpp
@@ -34,19 +34,19 @@ void init_serde(nb::module_& m) {
.def("get_size", &py_object_serde::get_size, nb::arg("item"),
"Returns the size in bytes of an item\n\n"
":param item: The specified object\n:type item: object\n"
- ":return: The size of the item, in bytes\n:rtype: int"
+ ":return: The size of the item in bytes\n:rtype: int"
)
.def("to_bytes", &py_object_serde::to_bytes, nb::arg("item"),
"Retuns a bytes object with a serialized version of an item\n\n"
":param item: The specified object\n:type item: object\n"
- ":return: A bytes object with the serialized object\n:rtype: bytes"
+ ":return: A :class:`bytes` object with the serialized object\n:rtype: bytes"
)
.def("from_bytes", &py_object_serde::from_bytes, nb::arg("data"), nb::arg("offset"),
"Reads a bytes object starting from the given offest and returns a tuple of the reconstructed "
"object and the number of additional bytes read\n\n"
- ":param data: A bytes object to deserialize\n:type data: bytes\n"
+ ":param data: A :class:`bytes` object from which to deserialize\n:type data: bytes\n"
":param offset: The offset, in bytes, at which to start reading\n:type offset: int\n"
- ":return: A tuple with the reconstructed object and the number of bytes read\n"
+ ":return: A :class:`tuple` with the reconstructed object and the number of bytes read\n"
":rtype: tuple(object, int)"
)
;
diff --git a/src/theta_wrapper.cpp b/src/theta_wrapper.cpp
index ff54116..e8329c6 100644
--- a/src/theta_wrapper.cpp
+++ b/src/theta_wrapper.cpp
@@ -128,7 +128,7 @@ void init_theta(nb::module_ &m) {
"Creates a theta_union using the provided parameters\n\n"
":param lg_k: base 2 logarithm of the maximum size of the union. Default 12.\n:type lg_k: int, optional\n"
":param p: an initial sampling rate to use. Default 1.0\n:type p: float, optional\n"
- ":param seed: the seed to use when hashing values. Must match any sketch seeds.\n:type seed: int, optional"
+ ":param seed: the seed to use when hashing values. Must match all sketch seeds.\n:type seed: int, optional"
)
.def("update", &theta_union::update<const theta_sketch&>, nb::arg("sketch"),
"Updates the union with the given sketch")
@@ -139,7 +139,7 @@ void init_theta(nb::module_ &m) {
nb::class_<theta_intersection>(m, "theta_intersection")
.def(nb::init<uint64_t>(), nb::arg("seed")=DEFAULT_SEED,
"Creates a theta_intersection using the provided parameters\n\n"
- ":param seed: the seed to use when hashing values. Must match any sketch seeds\n:type seed: int, optional"
+ ":param seed: the seed to use when hashing values. Must match all sketch seeds\n:type seed: int, optional"
)
.def("update", &theta_intersection::update<const theta_sketch&>, nb::arg("sketch"),
"Intersections the provided sketch with the current intersection state")
@@ -152,7 +152,7 @@ void init_theta(nb::module_ &m) {
nb::class_<theta_a_not_b>(m, "theta_a_not_b")
.def(nb::init<uint64_t>(), nb::arg("seed")=DEFAULT_SEED,
"Creates a tuple_a_not_b object\n\n"
- ":param seed: the seed to use when hashing values. Must match any sketch seeds.\n:type seed: int, optional"
+ ":param seed: the seed to use when hashing values. Must match all sketch seeds.\n:type seed: int, optional"
)
.def(
"compute",
diff --git a/src/tuple_wrapper.cpp b/src/tuple_wrapper.cpp
index 020e9d6..a2067f4 100644
--- a/src/tuple_wrapper.cpp
+++ b/src/tuple_wrapper.cpp
@@ -48,11 +48,22 @@ void init_tuple(nb::module_ &m) {
nb::class_<tuple_policy, TuplePolicy>(m, "TuplePolicy",
"An abstract base class for Tuple Policy objects. All custom policies must extend this class.")
.def(nb::init())
- .def("create_summary", &tuple_policy::create_summary, "Creates a new Summary object")
+ .def("create_summary", &tuple_policy::create_summary,
+ "Creates a new Summary object\n\n"
+ ":return: a Summary object\n:rtype: :class:`object`"
+ )
.def("update_summary", &tuple_policy::update_summary, nb::arg("summary"), nb::arg("update"),
- "applies the relevant policy to update the provided summary with the data in update.")
+ "Applies the relevant policy to update the provided summary with the data in update.\n\n"
+ ":param summary: An existing Summary\n:type summary: :class:`object`\n"
+ ":param update: An update to apply to the Summary\n:type update: :class:`object`\n"
+ ":return: The updated Summary\n:rtype: :class:`object`"
+ )
.def("__call__", &tuple_policy::operator(), nb::arg("summary"), nb::arg("update"),
- "Similar to update_summary but allows a different implementation for set operations (union and intersection)")
+ "Similar to update_summary but allows a different implementation for set operations (union and intersection)\n\n"
+ ":param summary: An existing Summary\n:type summary: :class:`object`\n"
+ ":param update: An update to apply to the Summary\n:type update: :class:`object`\n"
+ ":return: The updated Summary\n:rtype: :class:`object`"
+ )
;
// potentially useful for debugging but not needed as a permanent
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org