dnbaker/sketch

C++ Implementations of sketch data structures with SIMD Parallelism, including Python bindings

sketch

sketch is a generic, header-only library providing implementations of a variety of sketch data structures for scalable and streaming applications. All have been accelerated with SIMD parallelism where possible, most are composable, and many are threadsafe unless -DNOT_THREADSAFE is passed as a compilation flag.

Python documentation

Documentation for the Python interface is available here.

Dependencies

We directly include blaze-lib, libpopcnt, compact_vector, ska::flat_hash_map, and xxHash for various utilities. We also have two submodules:

• pybind11, only used for python bindings.
• SLEEF for vectorized math, incorporated with vec.h. It's optionally used (disabled by defining -DNO_SLEEF=1/#define NO_SLEEF 1) and only applicable to using rnla.h through blaze-lib.

You can ignore both for most use cases.

Contents

1. HyperLogLog Implementation [hll.h]
   1. hll_t/hllbase_t<HashStruct>
   2. Estimates the cardinality of a set using log(log(cardinality)) bits.
   3. Threadsafe unless -DNOT_THREADSAFE is passed.
   4. Currently, hll is the only structure for which python bindings are available, but we intend to extend this in the future.
2. HyperBitBit [hbb.h]
   1. Better per-bit accuracy than HyperLogLogs, but, at least currently, limited to 128 bits/16 bytes in sketch size.
3. Bloom Filter [bf.h]
   1. bf_t/bfbase_t<HashStruct>
   2. Naive bloom filter
   3. Currently not threadsafe.
4. Count-Min and Count Sketches
   1. ccm.h (ccmbase_t<UpdatePolicy=Increment>/ccm_t (use pccm_t for Approximate Counting or cs_t for a count sketch).
   2. The Count sketch is threadsafe if -DNOT_THREADSAFE is not passed or if an atomic container is used. Count-Min sketches are currently not threadsafe due to the use of minimal updates.
   3. Count-min sketches can support concept drift if realccm_t from mult.h is used.
5. MinHash sketches
   1. mh.h (RangeMinHash is the currently verified implementation.) We recommend you build the sketch and then convert to a linear container (e.g., a std::vector) using to_container<ContainerType>() or .finalize() for faster comparisons.
      1. BottomKHasher is an alternate that uses more space to reduce runtime, which finalizes() into the same structure.
   2. CountingRangeMinHash performs the same operations as RangeMinHash, but provides multiplicities, which facilitates histogram_similarity, a generalization of Jaccard with multiplicities.
   3. Both CountingRangeMinHash and RangeMinHash can be finalized into containers for fast comparisons with .finalize().
   4. A draft HyperMinHash implementation is available as well, but it has not been thoroughly vetted.
   5. Range MinHash implementationsare not threadsafe.
   6. HyperMinHash implementation is threa
6. B-Bit MinHash
   1. bbmh.h
   2. One-permutation (partition) bbit minhash
      1. Threadsafe, bit-packed and fully SIMD-accelerated
      2. Power of two partitions are supported in BBitMinHasher, which is finalized into a FinalBBitMinHash sketch. This is faster than the alternative.
      3. We also support arbitrary divisions using fastmod64 with DivBBitMinHasher and its corresponding final sketch, FinalDivBBitMinHash.
   3. One-permutation counting bbit minhash
      1. Not threadsafe.
7. ModHash sketches
   1. mod.h
   2. Estimates both containment and jaccard index, but takes a (potentially) unbounded space.
   3. This returns a FinalRMinHash sketch, reusing the infrastructure for minhash sketches, but which calculates Jaccard index and containment knowing that it was generated via mod, not min.
8. HeavyKeeper
   1. hk.h
   2. Reference: https://www.usenix.org/conference/atc18/presentation/gong
   3. A seemingly unilateral improvement over count-min sketches.
      1. One drawback is the inability to delete items, which makes it unsuitable for sliding windows.
      2. It shares this characteristic with the Count-Min sketch with conservative update and the Count-Min Mean sketch.
9. ntcard
   1. mult.h
   2. Threadsafe
   3. Reference: https://www.ncbi.nlm.nih.gov/pubmed/28453674
   4. Not SIMD-accelerated, but also general, supporting any arbitrary coverage level
10. PCSA
    1. pc.h
    2. The HLL is more performant and better-optimized, but this is included for completeness.
    3. Not threadsafe.
    4. Reference: https://dl.acm.org/doi/10.1016/0022-0000%2885%2990041-8 Journal of Computer and System Sciences. September 1985 https://doi.org/10.1016/0022-0000(85)90041-8
11. SetSketch
    1. See setsketch.h for continuous and discretized versions of the SetSketch.
    2. This also includes parameter-setting code.

Test case

To build and run the hll test case:

make test && ./test

Example

To use as a header-only library:

using namespace sketch;
hll::hll_t hll(14); // Use 2**14 bytes for this structure
// Add hashed values for each element to the structure.
for(uint64_t i(0); i < 10000000ull; ++i) hll.addh(i);
fprintf(stderr, "Elements estimated: %lf. Error bounds: %lf.\n", hll.report(), hll.est_err());

The other structures work with a similar interface. See the type constructors for more information or view 10xdash for examples on using the same interface for a variety of data structures.

Simply #include sketch/<header_name>, or, for one include #include <sketch/sketch.h>, which allows you to write sketch::bf_t and sketch::hll_t without the subnamespaces.

We use inline namespaces for individual types of sketches, e.g., sketch::minhash or sketch::hll can be used for clarity, or sketch::hll_t can be used, omitting the hll namespace.

OSX Installation

Clang on OSX may fail to compile in AVX512 mode. We recommend using homebrew's gcc:

homebrew upgrade gcc || homebrew install gcc

and either setting the environmental variables for CXX and CC to the most recent g++/gcc or providing them as Makefile arguments. At the time of writing, this is g++-10 and gcc-10.

Multithreading

By default, updates to the hyperloglog structure to occur using atomic operations, though threading should be handled by the calling code. Otherwise, the flag -DNOT_THREADSAFE should be passed. The cost of this is relatively minor, but in single-threaded situations, this would be preferred.

Python bindings

Python bindings are available via pybind11. Simply cd python && python setup.py install.

The package has been renamed to sketch_ds as of v0.19

Utilities include: 1. Sketching/serialization for sketch data structures 1. Supported: sketch_ds.bbmh.BBitMinHasher, sketch_ds.bf.bf, sketch_ds.hmh.hmh, sketch_ds.hll.hll 2. shs_isz, which computes the intersection size of sorted hash sets. 1. Supported: {uint,int}{32,64}, float32, float64 3. fastmod/fastdiv, which uses the fast modulo reduction to do faster division/mod than numpy. 1. Supportd: {uint,int}{32,64} 4. matrix generation functions - taking a list of sketches and creating the similarity function matrix. 1. Supported: sketch_ds.bbmh.BBitMinHasher, sketch_ds.bf.bf, sketch_ds.hmh.hmh, sketch_ds.hll.hll 2. Types: "jaccard_matrix", "intersection_matrix", "containment_matrix", "union_size_matrix", "symmetric_containment_matrix" 3. Returns a compressed distance matrix. 5. ccount_eq, pcount_eq compute the number of identical registers between integral registers. 1. Inspired by cdist and pdist from scipy.spatial.distance 2. ccount_eq computes the number of identical registers between all pairs of rows between two matrices A and B. 1. Size of returned matrix: (A.shape[0], A.shape[1]) 3. pcount_eq computes the number of identical registers between all pairs of rows in a single matrix A. 1. Size of returned matrix: (A.shape[0] * (A.shape[0]) - 1) / 2 4. pcount_eq output can be transformed from similarities to distances via -np.log(distmat / A.shape[1]).

sketch's Issues

SetSketches saved from different processes have jaccard estimation of 0

Hi! I'm using CSetSketch from python. I noticed that when I create, fill and then save this structure on disk for 2 sets in the same process, then loading it from disk and calculating jaccard estimation works well. But when 2 sets are processed in different processes, then the estimate is 0. For cardinality estimation everything works well in both cases.
Here is a minimal example showing this:

import os
import sketch

m = 2**18
hll, hll2 = sketch.setsketch.CSetSketch(m), sketch.setsketch.CSetSketch(m)

step1, step2, maxval1, maxval2 = 2, 5, 1000, 1000
for i in range(step1, maxval1+1, step1):
    hll.addh(str(i))

for i in range(step2, maxval2+1, step2):
    hll2.addh(str(i))
    
hll.write(f'tmp1_{os.getpid()}')
hll2.write(f'tmp2_{os.getpid()}')

Run this code twice in 2 different process. Then run:

from pathlib import Path
for ss1 in Path('./').glob('tmp1_*'):
    for ss2 in Path('./').glob('tmp2_*'):
        hll, hll2 = sketch.setsketch.CSetSketch(str(ss1)), sketch.setsketch.CSetSketch(str(ss2))
        jaccard_est = sketch.setsketch.jaccard_index(hll, hll2)
        print(ss1, ss2, jaccard_est)

It will print this in my case:
tmp1_736949 tmp2_736949 0.16761398315429688
tmp1_736949 tmp2_736999 0.0
tmp1_736999 tmp2_736949 0.0
tmp1_736999 tmp2_736999 0.166900634765625

bad versioning code in setup.py

setup.py contains the following line:

__version__ = subprocess.check_output( ["git", "describe", "--abbrev=4"]).decode().strip().split('-')[0]

which fails if the package is installed from tarball and not from git.

Fixing this is one of the messes of python packaging. One popular way is to use the package setuptools-scm, but that has some pitfalls too. With my own code, I find the simplest is the best. Put a version string into its own .py file, where it can be imported into setup. I haven't seen where your version info is stored, but have your Makefile stuff it into the version.py file as part of release.

error: use of undeclared identifier '_mm512_cmpeq_epi64_mask'

Hey @dnbaker, neat library! I'm trying to compile it on macOS 11.1 (x86-64) but am running into the following error:

make
cc -c -O3 -funroll-loops -pipe -march=native -Iinclude/sketch -I. -Ivec/blaze -Ivec -Ipybind11/include -Iinclude -fpic -Wall -Wall -Wextra -Wno-char-subscripts -Wpointer-arith -Wwrite-strings -Wdisabled-optimization -Wformat -Wcast-align -Wno-unused-function -Wno-unused-parameter -pedantic -Wunused-variable  -Wpedantic  -fno-strict-aliasing -DXXH_INLINE_ALL 	kthread.c -o kthread.o
c++ -O3 -funroll-loops -pipe -march=native -Iinclude/sketch -I. -Ivec/blaze -Ivec -Ipybind11/include -Iinclude -fpic -Wall -Wall -Wextra -Wno-char-subscripts -Wpointer-arith -Wwrite-strings -Wdisabled-optimization -Wformat -Wcast-align -Wno-unused-function -Wno-unused-parameter -pedantic -Wunused-variable  -Wpedantic  -fno-strict-aliasing -DXXH_INLINE_ALL  -Wreorder  	-std=c++14 -Wno-unused-parameter -pthread kthread.o testsrc/bbmhtest.cpp -o bbmhtest -lz # -fsanitize=undefined -fsanitize=address
In file included from testsrc/bbmhtest.cpp:1:
In file included from include/sketch/bbmh.h:3:
In file included from include/sketch/common.h:26:
./libpopcnt/libpopcnt.h:464:10: warning: cast from 'const uint8_t *' (aka 'const unsigned char *') to 'const uint64_t *'
      (aka 'const unsigned long long *') increases required alignment from 1 to 8 [-Wcast-align]
        *(const uint64_t*) *p);
         ^~~~~~~~~~~~~~~~~~~~
./libpopcnt/libpopcnt.h:576:10: warning: cast from 'const uint8_t *' (aka 'const unsigned char *') to 'const uint64_t *'
      (aka 'const unsigned long long *') increases required alignment from 1 to 8 [-Wcast-align]
        *(const uint64_t*) *p);
         ^~~~~~~~~~~~~~~~~~~~
./libpopcnt/libpopcnt.h:654:26: warning: cast from 'const uint8_t *' (aka 'const unsigned char *') to 'const __m512i *' increases required alignment
      from 1 to 64 [-Wcast-align]
    cnt += popcnt_avx512((const __m512i*) ptr, size / 64);
                         ^~~~~~~~~~~~~~~~~~~~
./libpopcnt/libpopcnt.h:668:24: warning: cast from 'const uint8_t *' (aka 'const unsigned char *') to 'const __m256i *' increases required alignment
      from 1 to 32 [-Wcast-align]
    cnt += popcnt_avx2((const __m256i*) ptr, size / 32);
                       ^~~~~~~~~~~~~~~~~~~~
./libpopcnt/libpopcnt.h:679:30: warning: cast from 'const uint8_t *' (aka 'const unsigned char *') to 'const uint64_t *'
      (aka 'const unsigned long long *') increases required alignment from 1 to 8 [-Wcast-align]
    cnt += popcnt64_unrolled((const uint64_t*) ptr, size / 8);
                             ^~~~~~~~~~~~~~~~~~~~~
./libpopcnt/libpopcnt.h:694:32: warning: cast from 'const uint8_t *' (aka 'const unsigned char *') to 'const uint64_t *'
      (aka 'const unsigned long long *') increases required alignment from 1 to 8 [-Wcast-align]
    cnt += popcount64_unrolled((const uint64_t*) ptr, size / 8);
                               ^~~~~~~~~~~~~~~~~~~~~
In file included from testsrc/bbmhtest.cpp:1:
In file included from include/sketch/bbmh.h:3:
In file included from include/sketch/common.h:60:
In file included from include/sketch/./hash.h:17:
././vec/vec.h:603:5: error: use of undeclared identifier '_mm512_cmpeq_epi64_mask'
    declare_all_int512(epi64, 512)
    ^
././vec/vec.h:376:5: note: expanded from macro 'declare_all_int512'
    declare_int_epi64_512(sz) \
    ^
././vec/vec.h:351:5: note: expanded from macro 'declare_int_epi64_512'
    declare_avx512_cmpeq_mask(64)
    ^
././vec/vec.h:168:32: note: expanded from macro 'declare_avx512_cmpeq_mask'
    static constexpr decltype(&_mm512_cmpeq_epi##sz##_mask) cmpeq_mask = &_mm512_cmpeq_epi##sz##_mask; \
                               ^
<scratch space>:193:1: note: expanded from here
_mm512_cmpeq_epi64_mask
^

It looks like it may be related to AVX512. Here are the AVX macros on my machine:

c++ -march=native -dM -E - < /dev/null | egrep "AVX" | sort
#define __AVX2__ 1
#define __AVX512BITALG__ 1
#define __AVX512BW__ 1
#define __AVX512CD__ 1
#define __AVX512DQ__ 1
#define __AVX512F__ 1
#define __AVX512IFMA__ 1
#define __AVX512VBMI2__ 1
#define __AVX512VBMI__ 1
#define __AVX512VL__ 1
#define __AVX512VNNI__ 1
#define __AVX512VPOPCNTDQ__ 1
#define __AVX__ 1

Any ideas?

Trouble including the library

I have trouble understanding what is the intended way to include the library. The README says
#include <sketch/sketch.h> but this file is in include/sketch/sketch.h. If I attempt to do #include "sketch/include/sketch/sketch.h", I get fatal error: aesctr/wy.h: No such file or directory (I did clone with submodules). Should I manually move all the directories like aesctr, vec next to sketch.h?

Are all submodules required? Blaze seems huge... I want to try out the count-min sketch, do I need the whole library for that?

Thanks!

won't compile under gcc > 11 or clang 16

compiles under gcc 11, but fails under gcc 12 & 13 with the following (similar under clang-16):

x86_64-pc-linux-gnu-g++ -std=c++17 -O3 -funroll-loops -pipe -march=native -Iinclude/sketch -I. -Iinclude/blaze -Ivec -Ipybind11/include -Iinclude -fpic -Wall -Wall -Wextra -Wno-char-subscripts -Wpointer-arith -Wwrite-strings -Wdisabled-optimization -Wformat -Wcast-align -Wno-unused-function -Wno-unused-parameter -pedantic -Wunused-variable -Wno-cast-align -fno-strict-aliasing -Wreorder -Wno-unused-parameter -pthread kthread.o testsrc/lpcqf_approx.cpp -o lpcqf_approx -lz # -fsanitize=undefined -fsanitize=address
In file included from testsrc/lpcqf_approx.cpp:1:
include/sketch/lpcqf.h: In instantiation of ‘constexpr const std::array<long double, 64> sketch::POWERS<25, 26, 64>’:
include/sketch/lpcqf.h:160:56: required from ‘static long double sketch::LPCQF<BaseT, sigbits, flags, argnum, argdenom, ModT, NCACHED_POWERS>::ainc_estimate_count(long long int) [with BaseT = short unsigned int; long unsigned int sigbits = 2; int flags = 11; long unsigned int argnum = 52; long unsigned int argdenom = 50; ModT = unsigned int; long long int NCACHED_POWERS = 64]’
include/sketch/lpcqf.h:360:47: required from ‘std::conditional_t<sketch::LPCQF<BaseT, sigbits, flags, argnum, argdenom, ModT, NCACHED_POWERS>::approx_inc, long double, BaseT> sketch::LPCQF<BaseT, sigbits, flags, argnum, argdenom, ModT, NCACHED_POWERS>::count_estimate(uint64_t) const [with BaseT = short unsigned int; long unsigned int sigbits = 2; int flags = 11; long unsigned int argnum = 52; long unsigned int argdenom = 50; ModT = unsigned int; long long int NCACHED_POWERS = 64; std::conditional_t<approx_inc, long double, BaseT> = long double; uint64_t = long unsigned int]’
testsrc/lpcqf_approx.cpp:16:121: required from here
include/sketch/lpcqf.h:113:73: error: invalid use of incomplete type ‘struct std::array<long double, 64>’
113 | constexpr std::array<long double, N> POWERS = get_ipowers<num, denom, N>();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
In file included from /usr/lib/gcc/x86_64-pc-linux-gnu/12/include/g++-v12/bits/unique_ptr.h:36,
from /usr/lib/gcc/x86_64-pc-linux-gnu/12/include/g++-v12/memory:75,
from include/sketch/lpcqf.h:11:
/usr/lib/gcc/x86_64-pc-linux-gnu/12/include/g++-v12/tuple:1595:45: note: declaration of ‘struct std::array<long double, 64>’
1595 | template<typename _Tp, size_t _Nm> struct array;
| ^~~~~
include/sketch/lpcqf.h:113:38: error: ‘constexpr const std::array<long double, 64> sketch::POWERS<25, 26, 64>’ has incomplete type
113 | constexpr std::array<long double, N> POWERS = get_ipowers<num, denom, N>();
| ^~~~~~

Error Compilation

Hello ,

I get the following error while compiling the codes:

rc/mhtest.cpp: In function ‘int main(int, char**)’:
src/mhtest.cpp:101:9: error: ‘aes’ has not been declared
aes::AesCtr<uint64_t> gen1(13), gen2(1337);

I tried including #include "aesctr.h" in the code, but it produces a large number of errors.

Can someone help?

please choose a unique name and create a python package

Both "sketch" and "hll" are taken in PYPI with packages that are far more popular than yours, creating a namespace collision waiting to happen. Please choose a new name and reserve that name in PYPI. Very little work would be needed to make a python package once this barrier is overcome.

SetSketch implementations

Hi! Thank you for this wonderful library. I am working on estimation of the overlap between different web crawls, this basically requires estimating the number of unique URLs in lists of 10-100 billion URLs and the cardinalities of their intersections. After some literature search it seems that SetSketch is the right method for this case as it allows both cardinality and Jaccard index estimation.
I found several implementations of SetSketch in your library (ByteSetSketch, CSetSketch, FSetSketch, ShortSetSketch). Could you please give an advice how to select the appropriate one? Also I could not find how I can change the hyperparameters a,b from Python. Is it possible and reasonable to try selecting them, or better rely on the default values?
The final question is about the calculation of the confidence intervals for the estimates. In the implementation of HLL there is the method relative_error() to get those, is there a way to get similar estimates for SetSketch?

Relationship to mindis/hll

https://github.com/mindis/hll

Is this the same project continued?

ss.cpp:4:15: error: ‘sketch::EByteSetS’ has not been declared

when I was downloading the package according to the command in the document, the above error occurred. I tried to update pybind11 to the latest version, but there is still a problem, maybe there are some dependencies?

test script and several tests fail

Make 4.4.1 puts all the names of tests in a single line, which makes the test script fail.
When this problem is fixed (see revised script below), I get 6 failed tests (bftest, cmtest, divtest, testcontain, testmhmerge, vactest) for various reasons.

#!/bin/bash make setup_tests -j8 1>/dev/null tests=$(cat tmpfiles.txt | tr " " "\n") n_failed=0 n_successes=0 rm -f failed.txt echo "running tests" start_time="$(date -u +%s)" for test_exe in $tests; do echo -n " ${test_exe}..." $(./$test_exe 2>/dev/null) if [ $? -eq 0 ]; then echo "OK" ((n_successes=n_successes+1)) else echo -e "\e[31m\e[1mfailed\e[0m" echo "${test_exe}" >> failed.txt ((n_failed=n_failed+1)) fi done end_time="$(date -u +%s)" elapsed="$(($end_time-$start_time))" echo "Results: ${n_successes} successes, ${n_failed} failures in ${elapsed} s" if [ $n_successes -gt 0 ]; then echo "Failed tests:" cat failed.txt fi rm -f tmpfiles.txt failed.txt

Compile error

Hi,

I cloned the repo recursively on a centos 7.9 machine. When I try to make the repo, I get the following error:

`make

g++ -std=c++17 -O3 -funroll-loops -pipe -march=native -I/usr/include/ -Iinclude/sketch -I. -Iinclude/blaze -Ivec -Ipybind11/include -Iinclude -fpic -Wall -Wall -Wextra -Wno-char-subscripts -Wpointer-arith -Wwrite-strings -Wdisabled-optimization -Wformat -Wcast-align -Wno-unused-function -Wno-unused-parameter -pedantic -Wunused-variable -Wno-cast-align -fno-strict-aliasing -Wreorder -Wno-unused-parameter -pthread kthread.o testsrc/swtest.cpp -o swtest -lz # -fsanitize=undefined -fsanitize=address
In file included from include/sketch/ccm.h:5,
from testsrc/swtest.cpp:1:
include/sketch/hash.h:25:24: error: 'vec' has not been declared
25 | using Type = typename vec::SIMDTypes<uint64_t>::Type;
| ^~~`

I will appreciate any help to fix it.