current clustering use > 60 hours to run on 80,000 sequenes.
What clustering does in SBOLExplorer — and can a hash replace it?
Role of clustering
The clusters map (which parts are similar to which) is produced by cluster.update_clusters() (the slow vsearch cluster_fast step) and used in two places:
- Rank de-duplication — search.py create_bindings:
if subject in cluster_duplicates:
_score /= 2.0 # near-duplicate of an already-seen part -> halve its score
elif subject in clusters:
cluster_duplicates.update(clusters[subject])
Purpose: when you search "GFP", stop 50 near-identical GFP variants from flooding the top results — demote the near-duplicates so results are more diverse.
- "Find similar parts" (SIMILAR) — lets a user ask "show me parts similar to this one," served from the precomputed clusters.
Correcting one assumption
It's not excluding identical sequences — it demotes sequences that are 80% similar (--id 0.8), i.e. near-duplicates / variants, not just exact copies. This distinction is what decides whether a hash can replace it.
So:
If you only need exact de-duplication → a plain hash wins; clustering can be dropped.
If you need to collapse variants (the current 0.8 behavior) → a plain hash can't do it.
Your instinct points at a real technique: similarity hashing
There are hash-based methods for near-duplicate grouping:
MinHash / LSH (Locality-Sensitive Hashing) approximate sequence similarity using hashes, grouping near-duplicates at near-hash speed — orders of magnitude faster than vsearch's all-vs-all cluster_fast, and naturally incremental (a new sequence just gets hashed into buckets).
Recommendation
The multi-hour clustering bottleneck can very likely be removed:
Decide the requirement — does rank de-dup need "exactly identical" or "near-identical variants"?
Exact only → plain hash, drop cluster_fast from indexing (hours → milliseconds).
Near-identical → MinHash/LSH, keeps variant-grouping but fast and incremental.
The "find similar" (SIMILAR) feature can instead be served on-demand at query time with vsearch --usearch_global (one-vs-all, seconds), rather than precomputing an all-vs-all clustering of the whole corpus offline.
One line
Clustering currently does two things: demote near-duplicates (80% similar) in ranking, and power "find similar parts." Exact duplicates are handled instantly by a plain hash; near-duplicate grouping can be done at near-hash speed and incrementally with MinHash/LSH instead of the multi-hour cluster_fast. Your hours-long bottleneck is very likely removable with hashing — it depends on whether you need "exact" or "approximate."
current clustering use > 60 hours to run on 80,000 sequenes.
What clustering does in SBOLExplorer — and can a hash replace it?
Role of clustering
The clusters map (which parts are similar to which) is produced by cluster.update_clusters() (the slow vsearch cluster_fast step) and used in two places:
Purpose: when you search "GFP", stop 50 near-identical GFP variants from flooding the top results — demote the near-duplicates so results are more diverse.
Correcting one assumption
It's not excluding identical sequences — it demotes sequences that are 80% similar (--id 0.8), i.e. near-duplicates / variants, not just exact copies. This distinction is what decides whether a hash can replace it.
So:
If you only need exact de-duplication → a plain hash wins; clustering can be dropped.
If you need to collapse variants (the current 0.8 behavior) → a plain hash can't do it.
Your instinct points at a real technique: similarity hashing
There are hash-based methods for near-duplicate grouping:
MinHash / LSH (Locality-Sensitive Hashing) approximate sequence similarity using hashes, grouping near-duplicates at near-hash speed — orders of magnitude faster than vsearch's all-vs-all cluster_fast, and naturally incremental (a new sequence just gets hashed into buckets).
Recommendation
The multi-hour clustering bottleneck can very likely be removed:
Decide the requirement — does rank de-dup need "exactly identical" or "near-identical variants"?
Exact only → plain hash, drop cluster_fast from indexing (hours → milliseconds).
Near-identical → MinHash/LSH, keeps variant-grouping but fast and incremental.
The "find similar" (SIMILAR) feature can instead be served on-demand at query time with vsearch --usearch_global (one-vs-all, seconds), rather than precomputing an all-vs-all clustering of the whole corpus offline.
One line
Clustering currently does two things: demote near-duplicates (80% similar) in ranking, and power "find similar parts." Exact duplicates are handled instantly by a plain hash; near-duplicate grouping can be done at near-hash speed and incrementally with MinHash/LSH instead of the multi-hour cluster_fast. Your hours-long bottleneck is very likely removable with hashing — it depends on whether you need "exact" or "approximate."