Comments (3)
Partial document overlap detection using MinHash is tricky. Effectively you are detecting containment rather than Jaccard similarity. Containment = |A \intersect B| / |A|
. What you can do is either
- use a larger minhash (e.g., num_perm > 256) to allow the overlap signal to show up in the Jaccard estimate, and then convert the estimated Jaccard similarity to containment using inclusion-exclusion principal.
- chunk the documents into smaller chunks and build MinHash for every chunk. By computing all pairs of MinHashes from the two documents, hopefully there will be a pair give you high Jaccard similarity signal. So, this is effectively looking for
max(Jaccard(m_i, m_j)) where i \in doc_1, j \in doc_2
.
from datasketch.
Thank you very much for your response. Your insights have been incredibly helpful. I had indeed considered the second point you mentioned, but segmenting the data doesn't always guarantee a perfect match between corresponding sections in the two documents. How do you view this aspect? However, performing pairwise comparisons is relatively straightforward. There are some alternative methods for achieving pairwise comparisons as well. Unfortunately, with my dataset reaching up to a hundred thousand entries or even more, the O(n^2) complexity leads to significant time wastage. I'm feeling a bit stuck on this issue and would greatly appreciate your guidance and suggestions.
from datasketch.
LSH exists to avoid the O(n^2) pair-wise comparison. I think you can use MinHash LSH to index all segments' minhash, and then self-query using every segment's minhash as query. This helps to approximate the pair-wise comparison you mentioned.
You can have some overlap between adjacent segments. Have you tried that?
from datasketch.
Related Issues (20)
- Advice for compression of a big graph HOT 3
- Distributed MinHashLSH HOT 3
- Poor default args in MinHashLSH? HOT 1
- Is is possible to rename already created index? HOT 1
- Add C-minHash variant HOT 11
- Synchronous Mongodb Storage HOT 3
- Merging (Identically Specified) MinHashLSH objects HOT 11
- Impact of MinHashLSH threshold on memory usage HOT 2
- Too large minhashLSH index HOT 10
- Is the bumber of bands correct? HOT 3
- Choice of np.uint64? HOT 11
- def jaccard 's denominator is self not [self union other] . HOT 2
- Forever growing index HOT 4
- HNSW: `HNSW.add` will not set the entry point of new levels HOT 2
- Process-safe, no mem bloat, implementation of LSH HOT 1
- Implementing MinHash retrieval from keys for MinHashLSHForest HOT 2
- Cassandra storage not compatible with Python 3.12 HOT 5
- Question: Effects of Bit Truncation on MinhashLSH? HOT 16
- uint64 overflow risk
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from datasketch.