.. image:: https://static.pepy.tech/badge/datasketch/month :target: https://pepy.tech/project/datasketch

.. image:: https://zenodo.org/badge/DOI/10.5281/zenodo.598238.svg :target: https://zenodo.org/doi/10.5281/zenodo.598238

.. image:: https://codecov.io/gh/ekzhu/datasketch/branch/master/graph/badge.svg :target: https://codecov.io/gh/ekzhu/datasketch

datasketch gives you probabilistic data structures that can process and search very large amount of data super fast, with little loss of accuracy.

.. note:: Version 2.0.0 changes the default MinHash permutation scheme to "affine32", which fixes a similarity over-estimation bias on large sets (issue #212 <https://github.com/ekzhu/datasketch/issues/212>), halves sketch memory, and speeds up updates by roughly 4x. A 64-bit "affine64" scheme is available for billion-scale sets. Hash values differ from earlier versions: rebuild persisted sketches and LSH indexes, or pass MinHash(..., scheme="legacy") to interoperate with existing data. See the MinHash documentation <https://ekzhu.github.io/datasketch/minhash.html> for details.

This package contains the following data sketches:

+-------------------------+-----------------------------------------------+ | Data Sketch | Usage | +=========================+===============================================+ | MinHash_ | estimate Jaccard similarity and cardinality | +-------------------------+-----------------------------------------------+ | Weighted MinHash_ | estimate weighted Jaccard similarity | +-------------------------+-----------------------------------------------+ | HyperLogLog_ | estimate cardinality | +-------------------------+-----------------------------------------------+ | HyperLogLog++_ | estimate cardinality | +-------------------------+-----------------------------------------------+

The following indexes for data sketches are provided to support sub-linear query time:

+---------------------------+-----------------------------+------------------------+ | Index | For Data Sketch | Supported Query Type | +===========================+=============================+========================+ | MinHash LSH_ | MinHash, Weighted MinHash | Jaccard Threshold | +---------------------------+-----------------------------+------------------------+ | LSHBloom_ | MinHash, Weighted MinHash | Jaccard Threshold | +---------------------------+-----------------------------+------------------------+ | MinHash LSH Forest_ | MinHash, Weighted MinHash | Jaccard Top-K | +---------------------------+-----------------------------+------------------------+ | MinHash LSH Ensemble_ | MinHash | Containment Threshold | +---------------------------+-----------------------------+------------------------+ | HNSW_ | Any | Custom Metric Top-K | +---------------------------+-----------------------------+------------------------+

datasketch must be used with Python 3.9 or above, NumPy 1.11 or above, and Scipy.

Note that MinHash LSH_ and MinHash LSH Ensemble_ also support Redis and Cassandra storage layer (see MinHash LSH at Scale_).

To install datasketch using pip:

.. code-block:: bash

pip install datasketch

This will also install NumPy as dependency.

To install with Redis dependency:

.. code-block:: bash

pip install datasketch[redis]

To install with Cassandra dependency:

.. code-block:: bash

pip install datasketch[cassandra]

To install with Bloom filter dependency:

.. code-block:: bash

pip install datasketch[bloom]

.. _MinHash: https://ekzhu.github.io/datasketch/minhash.html .. _Weighted MinHash: https://ekzhu.github.io/datasketch/weightedminhash.html .. _HyperLogLog: https://ekzhu.github.io/datasketch/hyperloglog.html .. _HyperLogLog++: https://ekzhu.github.io/datasketch/hyperloglog.html#hyperloglog-plusplus .. _MinHash LSH: https://ekzhu.github.io/datasketch/lsh.html .. _MinHash LSH Forest: https://ekzhu.github.io/datasketch/lshforest.html .. _MinHash LSH Ensemble: https://ekzhu.github.io/datasketch/lshensemble.html .. _LSHBloom: https://ekzhu.github.io/datasketch/lshbloom.html .. _Minhash LSH at Scale: http://ekzhu.github.io/datasketch/lsh.html#minhash-lsh-at-scale .. _HNSW: https://ekzhu.github.io/datasketch/documentation.html#hnsw

We welcome contributions from everyone. Whether you're fixing bugs, adding features, improving documentation, or helping with tests, your contributions are valuable.

Development Setup ^^^^^^^^^^^^^^^^^

The project uses uv for fast and reliable Python package management. Follow these steps to set up your development environment:

1. Install uv: Follow the official installation guide at https://docs.astral.sh/uv/getting-started/installation/

2. Clone the repository:

   .. code-block:: bash

   git clone https://github.com/ekzhu/datasketch.git
   cd datasketch
   

3. Set up the environment:

   .. code-block:: bash

   # Create a virtual environment
   # (Optional: specify Python version with --python 3.x)
   uv venv
   # Activate the virtual environment (optional, uv run commands work without it)
   source .venv/bin/activate
   
   # Install all dependencies
   uv sync
   

4. Verify installation:

   .. code-block:: bash

   # Run tests to ensure everything works
   uv run pytest
   

5. Optional dependencies (for specific development needs):

   .. code-block:: bash

   # For testing
   uv sync --extra test
   
   # For Cassandra support
   uv sync --extra cassandra
   
   # For Redis support
   uv sync --extra redis
   
   # For all extras
   uv sync --all-extras
   

Learn more about uv at https://docs.astral.sh/uv/

Development Workflow ^^^^^^^^^^^^^^^^^^^^

1. Fork the repository on GitHub if you haven't already.

2. Create a feature branch for your changes:

   .. code-block:: bash

   git checkout -b feature/your-feature-name
   # Or for bug fixes:
   git checkout -b fix/issue-description
   

3. Make your changes following the project's coding standards.

4. Run the tests to ensure nothing is broken:

   .. code-block:: bash

   uv run pytest
   

5. Check code quality with ruff:

   .. code-block:: bash

   # Check for issues
   uvx ruff check .
   
   # Auto-fix formatting issues
   uvx ruff format .
   

6. Commit your changes with a clear, descriptive commit message:

   .. code-block:: bash

   git commit -m "Add feature: brief description of what was changed"
   

7. Push to your fork and create a pull request on GitHub:

   .. code-block:: bash

   git push origin your-branch-name
   

8. Respond to feedback from maintainers and iterate on your changes.

Guidelines ^^^^^^^^^^

• Follow PEP 8 style guidelines
• Write tests for new features
• Update documentation as needed
• Keep commits focused and atomic
• Be respectful in discussions

For more information, check the GitHub issues <https://github.com/ekzhu/datasketch/issues>_ for current priorities or areas needing help. You can also join the discussion on project roadmap and priorities <https://github.com/ekzhu/datasketch/discussions/252>_.