How to handle sets with less than $k$ elements when using a single hash function to minhash?

Question

A minhash implementation with multiple hash functions can easily handle comparisons between sets with a vastly different number of elements because the denominator of the unbiased estimator $k$ is based on the number of hash functions, which is always fixed.

However, when calculating a minhash using a single hash function, you need to choose a value $k$ which represents the minimum $k$ values when all the items in $S$ are run through a single hash function.

How can you process a set $S$ that has less than $k$ elements and get an unbiased estimate?

I see two possible approaches. The first is to simply void any sets that don't have more than $k$ elements for comparison. This is undesirable because even for sets with a small number of values, I'd still like to compare it to other sets (which I can do with the multiple hashing variant).

The second is to get the intersection of $h_k(S_1)$ and $h_{k}(S_2)$ where $|S_{1 and/or 2}| < k$ as you would normally. This seems like it would work, but for small sets that are very similar (if not outright duplicates of each other) it seems it would provide erroneous values; you'd possibly miss matches, but at least you won't get false positives for reasons other than your hash function not being a perfect hash.

Answer 1

I've outlined some of the approaches above, and giving it some thought, I've gone with what I'm choosing and why.

Sampling with (or without) replacement (suggested by Anony-Mousse)

I'm not a fan of this. This could very easily produce values that produce similarities that are higher than they actually are, which could (not always) lead to a flawed prediction/outcome. I'm personally trying to avoid false positives as much as possible, and while a bad hash function can certainly lead to false positives, I'd rather not introduce the possibility of more if I can avoid it.

Taking intersection of $h_k(S_1)$ and $h_{k}(S_2)$ where $min(|S_1|, |S_2|) < k$

While this was what I was leaning towards, I decided against this. The key was in looking at the error estimate, $1 \over \sqrt{k}$ (same as the multiple hash function version).

Assuming that $k_1 = min(|S_1|,|S_2|)$, the error estimate for that hash comparison would be different than if $k$ samples were taken.

While it would be accurate for that comparison, it would be like comparing apples and oranges, as the expected error for all the other sets with $k$ elements is different. This is unacceptable.

The other approach:

Void any sets that don't have more than $k$ elements for comparison.

I've chosen to produce an error when this happens. Given the reasons stated in the first option, I'd rather have an error than return an erroneous value that I presume is correct.

The error indicates to me that my selection of $k$ needs adjustment (or I need to take another look at the data) if I want to be able to process sets that small.

Whether it's an error or skipping the comparison of those sets, the point is the same don't produce an error that's assumed to be correct.