ekzhu/datasketch

MinHash, LSH, LSH Forest, Weighted MinHash, HyperLogLog, HyperLogLog++, LSH Ensemble and HNSW

What it solves

It provides a way to process and search through massive datasets extremely quickly while maintaining a high level of accuracy. It solves the problem of calculating similarity and cardinality (the number of unique elements) across very large amounts of data without needing to store or process the full dataset in memory.

How it works

The library uses probabilistic data structures known as "sketches" to create compact representations of data. It implements several algorithms to estimate properties of the data:

  • MinHash and Weighted MinHash: Used to estimate Jaccard similarity and cardinality.
  • HyperLogLog and HyperLogLog++: Used to estimate the number of unique elements (cardinality).

To make searching these sketches efficient, it provides various indexes that allow for sub-linear query times, including Locality Sensitive Hashing (LSH) for threshold-based similarity searches and HNSW for custom metric top-K queries.

Who it’s for

Data engineers and software developers working with big data who need to perform fast similarity searches or count unique items across billion-scale datasets.

Highlights

  • Probabilistic efficiency: Processes large data with minimal memory loss and high speed.
  • Scalable storage: Supports Redis and Cassandra as storage layers for LSH indexes.
  • Diverse indexing: Includes LSH, LSHBloom, LSH Forest, and HNSW for different query types (e.g., Jaccard threshold, Top-K).
  • Flexible schemes: Offers multiple permutation schemes (like affine32 and affine64) to optimize memory and speed based on the dataset size.

Related

  • Project
    beowolx/rensa

    A high-performance MinHash library written in Rust with Python bindings for fast similarity estimation and near-duplicate detection in large datasets.

  • Project
    facebookresearch/faiss

    A library for efficient similarity search and clustering of dense vectors, capable of handling billion-scale datasets using CPU and GPU acceleration.

  • Project
    boyter/cs

    A CLI code search engine that uses structural awareness and cyclomatic complexity to rank results by relevance without requiring an index.

  • Project
    tensorflow/probability

    A library for probabilistic reasoning and statistical analysis that integrates probabilistic methods with deep networks using TensorFlow or JAX.

  • Project
    moj-analytical-services/splink

    A Python package for probabilistic record linkage and deduplication that identifies and links records without unique identifiers using the Fellegi-Sunter model.