Summary

We have been using datasketch extensively in data-driven applications (primarily the MinHashLSH class). The existing implementation requires all data to be stored in memory, which is a severe limitation for very large datasets. We add support for a Redis backend. Default behavior remains in-memory storage.

Changes

• Redis backend for MinHashLSH
• Insertion session for bulk insertion (reduces network calls when inserting with a Redis backend)
• Functionality to view LSH bucket sizes (useful for diagnosis/debugging)
• Accompanying docs and tests

Examples

For examples, see the additions to the documentation.

This is a storage layer that uses Cassandra as a backend. It is optimized to take into account Cassandra internals and its (intrinsic) limitations (see for example how all the keys are retrieved and how the list abstraction is implemented). I have also added a new batch of tests to both TestMinHashLSH and TestWeightedMinHashLSH. Since Cassandra is required (Cassandra is not mocked) they can be enabled by flipping the DO_TEST_CASSANDRA variable.

I have also updated the documentation a bit.

The purpose of the function AsyncIOMotorClient.get_default_database is to allow for the Mongo URL to define a database. If the URL contains a database, that database in the URL will be used, otherwise, the calculated database name is used. As for get_collection, I changed it for consistency only.

I wanted to update the unit tests, but they were skipped… and when I tried to un-skip them everything failed spetacularly. I'm not sure what to do about that.

Cheers!

Thanks for this library!

One question: Is there an easy way to get all pairs from a LSH? In other words, instead of a query for a single minhash, I need all pairs of records inside a same bucket.

I tried to dive into the code, but I didn't understand very well how hashranges/hashtables work. What I need is similar to candidate_duplicates of this other implementation: https://mattilyra.github.io/2017/05/23/document-deduplication-with-lsh.html

I've made some performance improvements in the MinHash class and added a helper method for bulk computation.

1. Precasting _mersenne_prime and _max_hash, they don't need to be cast multiple times.
2. I've modified the update method to accept a list of bytes so hash values can be computed in batches. This avoids using for loops in python space and packs all those operations into the numpy calls once. Only caveat here is that the matrix operations use more memory and you should do chunking if you're dealing with huge sets.
3. The bulk helper removes unnecessary initialization overhead of the permutations and initial hashvalues. They are computed once then passed on to new MinHash objects as they are produced.

These changes give some pretty nice performance improvements, up to 3X for updates, and anywhere from 5-25X for bulk computing. See my benchmark gist here

We'd struggled with AsyncMinhashLSH's query performance, eventually finding out it wasn't using the default collection index key ('_id'), and instead querying by it's 'key' field. (see: here )

This can either be fixed by inserting into the collections with primary key '_id', or else creating indices on the 'key' field for all collections in the database.

For anyone looking for the quickfix solution, simply run:

db.lsh_...._bucket_#.createIndex( { key: -1 } )

on each of the buckets and key collections in the database. We found performance went from 11 seconds/ query to >1ms/ query pretty much instantly.

I believe this should be added to the documentation somewhere, or fixed in the code (although it'd break existing databases). I'd volunteer to do either!

If you are connecting to a redis database and you lose the reference to the connection, you will lose reference to all data in your hash and you also lose the ability to remove it. By having the ability to set the base name, you can alway reference the same keys no matter if you create a new connection or use the old one.

I what to find duplicates,so I need pop a hash then compare left hashes.

or should I make a copy of original data to redis? or just not use the redis storge wait the dataset feed up then use MinHashLSH

Hi guys,

Question, I'd like to store a MinHashLSH on a Mongo-db instance. I've seen you have Redis & Cassandra as storage-types in the code; is there an easy way for me to store in on mongo as well?

Greets Tb

Hi,

First of all thanks for this amazing package. I have two LSH, one optimized with a threshold of 0.65 and the other with a threshold of 0.55. I found the results from both these LSH are relevant to me, and I would finally take a union of the results of both of these, and get my duplicate contents.

In order to store both LSH, I'm using Redis caching mechanism, but later I will have to call both the LSH, run individually and take the union of the results.

Is there any way I could optimize so that I could do the same with only one LSH if possible or some method to create a special type of indexes in Redis such that I don't have to call the LSH's Individually. This would help me save Memory and Computational Time.

Hi,

First of all thanks for this great library :)

I wanted to know if there is any way to set an expiry time for entries being added into an LSH connected to Redis? Or any way to keep a default expiry time for all keys?

Should I instead set a maxmemory policy for my Redis with an allkeys-lru or allkeys-random eviction policy? Is this recommended or will it cause issues with the LSH?

Regards, Spandan

numpy.int was only ever an alias for the built-in, and is now deprecated from version 1.20.0

See: https://numpy.org/doc/stable/release/1.20.0-notes.html#using-the-aliases-of-builtin-types-like-np-int-is-deprecated

In API document , we can learn how to find approximate neighbours with Jaccard similarity more than threshold . On the other hand, how to find most unsimilar instance. Further, given a minHash LSH which initialized by thousands of plain text - set A, and given other thousands of plain text - set B, how to discover most unsimilar text of set B with set A , or how to discover text of set B which jaccard similarity less than threshold . Is there as possible as fast solution to deal with this problem ? Thanks !

I have a use case where i have to store min hash of (n) different categories of file and the query them. For example if i have documents of category A and I want to store all of them in one db and then query at later point.

I am initializing this in a microservice as (fastapi) as follows

@app.on_event("startup")
async def startup_event():
    LSHService.lsh_js, LSHService.lsh_css, LSHService.lsh_html, = await asyncio.gather(
        *[
            await AsyncMinHashLSH(
                storage_config={
                    **_storage,
                    "basename": "category-a".encode(),
                },
                threshold=0.9,
                num_perm=256,
            ),
            await AsyncMinHashLSH(
                storage_config={
                    **_storage,
                    "basename": "category-b".encode(),
                },
                threshold=0.9,
                num_perm=256,
            ),
            await AsyncMinHashLSH(
                storage_config={
                    **_storage,
                    "basename": "category-b".encode(),
                },
                threshold=0.9,
                num_perm=256,
            ),
        ]
    )

If i initialize like this i get
Getting pymongo.errors.ExecutionTimeout Error

However If i just maintain 1 object then I dont get any error.

What can I do mitigate this? Thanks in advance

Say if we have three documents A, B and C. Each document might contains different words.

According to the document of data sketch.MinHash, we can get a min-hash for A with

minxish = Minhash(num_perm=128) minhash.update(A.encode('utf-8')) vector = minhash.digest()

But isn't that we need to create a vocabulary consisting of all words from A, B and C before getting the vector?