pub fn dictionary_groups(
sketches: &[Sketch],
threshold: f64,
) -> Result<Vec<Vec<usize>>>Expand description
Which columns should be considered for a shared dictionary, from one sketch per column.
Two columns are put in the same group when their estimated Jaccard similarity is at least
threshold, and grouping is transitive: if A overlaps B and B overlaps C then all three end up
together, even if A and C do not overlap each other. That is deliberate. A dictionary is a set
union, so a chain of overlapping columns still stores fewer values once than separately, and
insisting that every pair in a group overlaps would turn this into a clique problem for no
benefit.
Every column appears in exactly one group, and a column that overlaps nothing is a group of one. The groups come back in the order of their lowest column index, and the columns inside a group in index order, so the result does not depend on the order the pairs were tested in.
This is a pruning step and not a decision. Two columns can overlap heavily and still be better
off apart, which is why what comes out of here goes to strategy_sizes rather than straight
into a writer.
ยงErrors
If the sketches were not all built at the same k, since then no estimate over a pair means anything.