<p>In order for the KMV sketch to work, you need the k minimum values. If one of the branches of the union didn't have k values to begin with, you can still take the union and truncate to k. It's only if you truncate to k' that you have to truncate the combined sketch to k'.</p>

<p>In fact, you can use even more of the samples to improve accuracy. See <a href="https://arxiv.org/abs/0903.0625" rel="nofollow noreferrer">https://arxiv.org/abs/0903.0625</a> *, which shows that it suffices to discard only down to the min discarded sample (which may be nothing at all), resulting in slightly better accuracy.</p>

<p>* Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates. Edith Cohen, Haim Kaplan.</p>
Union of multiple K-minimum values sets of different sizes in the KMV algorithm
<p>While researching the K-minimum values (KVM) method I've found the following paragraph in the blog on KMV method:</p>

<blockquote>
  <p>Note that if the two KMV objects are of different size, due to K being
  different sizes, or because either one isn't completely filled with K minimum values, you should use the smaller value of K as your union set K size.</p>
</blockquote>

<p>and also</p>

<blockquote>
  <p>To perform union, you merely take 2 sketches and combine their values and keep the k smallest ones (if the 2 sketches are of different sizes, k and k', then you keep the min(k,k') values in order to keep the lowest resolution).</p>
</blockquote>

<p>Then it seems that if I am trying to use large K (for better accuracy, e.g. 2048) then if I look at the multiple KMV objects (e.g. tables in databases reporting unique users of the internet portal) and even one of them has less distinct values than K (i.e. K'), then I would have to use that smaller value of K' in the final union. Instead of large K, I may end up with very small K'. May I simply ignore the fact that K' &lt; K and use K minimum values each time I combine the minimum value data sets? Or better question would be: what is wrong with simply using K in all cases and why we need to use the smaller value?</p>