krowkee::sketch module reference.

krowkee::sketch::Sketch is the basic interface for specifiying sketch data structures in krowkee. However, the behavior of krowkee::sketch::Sketch is heavily modified by its template arguments. The ContainerType template determines the underlying memory management behavior of the register set. krowkee::sketch::Dense yields the simplest behavior, and stores the registers as an std::vector. krowkee::sketch::Sparse is more sophisticated, and stores the registers as a krowkee::container::compacting_map under the hood. krowkee::sketch::Promotable marries the two, and allows a sketch to begin life as with a Sparse container that is promoted to Dense if it becomes sufficiently full. krowkee::sketch::Matrix represents sketches of matrices, where both the column- and row-spaces are transformed. The underlying matrix sketch is stored as an Eigen::Matrix.

Register Container Types:

• Dense
  • krowkee::sketch::Dense
• Sparse
  • krowkee::sketch::Sparse
• Promotable
  • krowkee::sketch::Promotable
• Matrix
  • krowkee::sketch::Matrix

A sketch is also defined by the transform that it supports. This transform defines the way in which updates affect the set of registers, and is fundamental to the statistical guarantees of the associated sketch.

Transform Types:

• SparseJLT
  • krowkee::transform::SparseJLT
• DoubleSparseJLT
  • krowkee::transform::DoubleSparseJLT
• FWHT
  • krowkee::transform::FWHT

template<typename SketchFunc, typename ContainerType, template<typename> class PtrType>
class Sketch

General Sketch Chassis.

Implements the container handling infrastructure of a linear sketch defined by a given sketch functor projecting into a fixed-size set of registers supporting an (element-wise) merge operator. The registers might be Dense, Sparse, or variable, depending on the templated ContainerType.

Template Parameters:

• SketchFunc – A sketch functor such as krowkee::transform::CountSketchFunctor whose first template parameter is set by RegType.

• ContainerType – A container class such as krowkee::sketch::Dense.

• PtrType – The type of shared pointer used to wrap the sketch functor. Should be std::shared_ptrin shared memory and ygm::ygm_ptr in distributed memory.

• Args – Additional template parameters for SketchFunc, such as a hash functor.

Public Types

using transform_type = SketchFunc

Alias for fully-templated sketch functor type

using transform_ptr_type = PtrType<transform_type>

Alias for fully-templated sketch functor pointer type

using register_type = typename transform_type::register_type

Alias for Register type

using container_type = ContainerType

Alias for fully-templated container type

using registers_type = typename container_type::dense_registers_type

Alias for fully-templated raw container type

using self_type = Sketch<transform_type, ContainerType, PtrType>

Alias for fully-templated self type

Public Functions

inline Sketch(const transform_ptr_type &sf_ptr)

Construct a new Sketch object.

Parameters:

sf_ptr – pointer desired linear sketch functor.

inline Sketch(const self_type &rhs)

Copy constructor.

Parameters:

rhs – krowkee::sketch::Sketch to be copied

inline Sketch()

default constructor

Note

Only used for move constructor.

inline const container_type &container()

Return a reference to the underlying container data structure.

Note

For testing purposes. Might want to get rid of this.

Returns:

const container_type& A reference to the internal register container object.

template<typename ...ItemArgs>
inline constexpr void insert(const ItemArgs&... args)

Insert item into registers using sketch functor.

Example could involve (x, multiplicity) where x is the object to insert and multiplicity is the number of insert repetitions to perform.

Template Parameters:

ItemArgs – types of parameters of the stream object to be inserted. Will be used to construct an krowkee::stream::Element object.

Parameters:

args – Arguments describing the stream object.

template<typename ...ItemArgs>
inline constexpr void insert(const std::pair<std::uint64_t, std::uint64_t> &indices, const ItemArgs&... args)

Insert item into registers using sketch functor, assuming a tuple of indices as the first argument.

Example could involve ({i, j}, multiplicity) where i and j are the row and columnn indices of the matrix insertion, respectively, and multiplicity is the number of insert repetitions to perform.

Template Parameters:

ItemArgs – types of parameters of the stream object to be inserted. Will be used to construct an krowkee::stream::Element object.

Parameters:

• indices – Describes data structure indices to be inserted.

• args – Addtional arguments describing the stream object.

inline void compactify()

Signal sketch container to compactify, if it supports such functionality.

inline void clear()

Signal sketch container to remove all information.

inline bool empty() const

Check if container is holding any state.

inline self_type &operator+=(const self_type &rhs)

Merge other Sketch registers into this.

Parameters:

rhs – the other Sketch embedding. Must use the same random seed.

Throws:

std::invalid_argument – if the SketchFuncs do not agree.

Returns:

self_type& The merge of the two sketches.

inline constexpr auto begin()

Mutable begin iterator.

inline constexpr auto begin() const

Const begin iterator.

inline constexpr auto cbegin() const

Const begin iterator.

inline constexpr auto end()

Mutable end iterator.

inline constexpr auto end() const

Const end iterator.

inline constexpr auto cend()

Const end iterator.

inline constexpr bool is_sparse() const

Check for sparsity of container.

Returns:

true The container is sparse.

Returns:

false The container is not sparse.

inline constexpr std::size_t size() const

Get the number of registers, real or notional, in the container.

Returns:

constexpr std::size_t The size of the container.

inline constexpr std::size_t reg_size() const

The number of bytes used by each register.

inline constexpr std::size_t compaction_threshold() const

Get the compaction threshold of the container.

Returns:

constexpr std::size_t The compaction threshold.

inline constexpr bool same_functors(const self_type &rhs) const

Checks whether another sketch is using the same functor.

Parameters:

rhs – The other sketch.

Returns:

true The functors agree.

Returns:

false The functors disagree.

inline self_type &operator=(self_type rhs)

Copy-and-swap assignment operator.

Note

https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

Parameters:

rhs – The right-hand sketch.

Returns:

self_type& The new value of this sketch, swapped with rhs.

Public Static Functions

static inline constexpr std::string name()

Return a description of the type of container and transform that this sketch implements.

Returns:

std::string Sketch description, e.g. “Dense CountSketch”

static inline constexpr std::string full_name()

Return a description of the fully-qualified type of container and transform that this sketch implements.

Returns:

std::string Sketch

description, e.g. “Promotable using

std::map<unsigned int, int, std::less<unsigned int>,

std::allocator<std::pair<unsigned int const, int> > > CountSketch using

MulAddShift hashes and 4 byte registers”

static inline constexpr std::size_t range_size()

Get the number of possible range elements returned by the sketch functor.

Returns:

constexpr std::size_t The size of the sketch functor range.

Friends

inline friend constexpr friend self_type operator+ (const self_type &lhs, const self_type &rhs)

Merge two sketches.

Parameters:

• lhs – The left-hand sketch object.

• rhs – The right-hand sketch object.

Returns:

self_type The merge of the two sketch objects.

inline friend constexpr bool operator==(const self_type &lhs, const self_type &rhs)

Checks equality between sketch objects.

Two sketches are equivalent if they are using the same sketch functor and their registers hold the same values.

Parameters:

• lhs – The left-hand sketch.

• rhs – The right-hand sketch.

Returns:

true The sketches are equivalent.

Returns:

false The sketches disagree.

inline friend constexpr bool operator!=(const self_type &lhs, const self_type &rhs)

Check inequality between two sketch objects.

Parameters:

• lhs – The left-hand sketch.

• rhs – The right-hand sketch.

Returns:

true The sketches disagree.

Returns:

false The sketches are equivalent.

inline friend void swap(self_type &lhs, self_type &rhs)

Swap two Sketch objects.

Note

For some reason, calling std::swap on the container here causes a “no

matching function compiler error”. Peculiar.

Parameters:

• lhs – The left-hand sketch.

• rhs – The right-hand sketch.

inline friend std::ostream &operator<<(std::ostream &os, const self_type &sk)

Serialize a sketch to human-readable output stream.

Note

Intended for debugging only.

Parameters:

• os – The output stream.

• sk – The sketch object.

Returns:

std::ostream& The new stream state.

template<typename RetType>
inline friend RetType accumulate(const self_type &sk, const RetType init)

Accumulate sum of register values.

Template Parameters:

RetType – The value type to return.

Parameters:

• sk – The sketch to accumulate.

• init – Initial value of return.

Returns:

RetType The sum over all register values + init.