Adapt the kSpider's algorithm in pairwise comparisons #219
Comments
|
The kSpider algorithm is particularly good in comparing large sparse hash-sets. |
|
A few hot takes:
|
|
hey @mr-eyes -- I already had this draft in progress based on our discussions in January, just hadn't committed/ pushed up my changes yet. Would love to have your contributions/insight/clustering expertise/etc! I haven't had a chance to verify clusters are created correctly yet, just wanted to get this up here to avoid you re-doing any of the work I already put in. |
|
Hi @bluegenes , I would absolutely love to contribute to this as needed. I want to clarify that #234 is not what I mean by the kSpider's algorithm. The kSpider algorithm utilizes the index to generate a sparse pairwise matrix rather than the brute-force comparisons done in #181. This is expected to work well when comparing highly diverse/sparse data. |
|
Whoops - completely misread that somehow. @ctb's comments make a lot more sense now 😂. Sparse pairwise would be great too! In any case, would love to have your input on the cluster PR :). I 'll tag your for review when I think it's ready. |
This PR adds a new command, `cluster`, that can be used to cluster the output from `pairwise` and `multisearch`. `cluster`uses `rustworkx-core` (which internally uses `petgraph`) to build a graph, adding edges between nodes when the similarity exceeds the user-defined threshold. It can work on any of the similarity columns output by `pairwise` or `multisearch`, and will add all nodes to the graph to preserve singleton 'clusters' in the output. `cluster` outputs two files: 1. cluster identities file: `Component_X, name1;name2;name3...` 2. cluster size histogram `cluster_size, count` context for some things I tried: - try using petgraph directly and removing rustworkx dependency > nope,`rustworkx-core` adds `connected_components` that returns the connected components, rather than just the number of connected components. Could reimplement if `rustworkx-core` brings in a lot of deps - try using 'extend_with_edges' instead of add_edge logic. > nope, only in `petgraph` **Punted Issues:** - develop clustering visualizations (ref @mr-eyes kSpider/dbretina work). Optionally output dot file of graph? (#248) - enable updating clusters, rather than always regenerating from scratch (#249) - benchmark `cluster` (#247) > `pairwise` files can be millions of lines long. Would it be faster to parallel read them, store them in an `edges` vector, and then add nodes/edges sequentially? Note that we would probably need to either 1. store all edges, including those that do not pass threshold) or 2. After building the graph from edges, add nodes from `names_to_node` that are not already in the graph to preserve singletons. Related issues: * #219 * sourmash-bio/sourmash#2271 * sourmash-bio/sourmash#700 * sourmash-bio/sourmash#225 * sourmash-bio/sourmash#274 --------- Co-authored-by: C. Titus Brown <[email protected]>
I plan to implement the kSpider's algorithm in Rust, utilizing the inverted index of RocksDB. I wanted to ask if that should be another sub-command in the
branchwater pairwiseor if it should be a separate command. Or maybe a different repo (i.e., the original kSpider project).The text was updated successfully, but these errors were encountered: