Пересечение HyperLogLog: почему бы не использовать min?

Question

При объединении двух совместимых объектов HyperLogLog вы можете просто взять максимальный ковш для объединения без потерь, который не вводит никаких новых ошибок:

Union.Bucket [i] = Max (A.Bucket [ я], B.Bucket [я])

При выполнении перекрестка, хотя, вы должны использовать принцип включения-исключения:

IntersectionCountEstimate = A.CountEstimate() + B.CountEstimate() - Союз. CountEstimate()

Почему это так, что использование минимального значения ведра не работает как эффект е пересечение?

Intersection.Bucket [I] = Min (A.Bucket [I], B.Bucket [I])

Answer 1

Причина в том, что отношения между двумя экземплярами статистики HyperLogLog не очень интуитивно:

Рассмотрите два соответствующих ковши A [i] и B [i] из отдельных структур HyperLogLog A и B (которые имеют одинаковое количество ковшей и используют одну и ту же функцию хэша), и для простоты возьмите данные в A и в B независимо от одного и того же распределения. Предположим, мы сначала нарисуем все элементы для A и только затем нарисуем элементы для B.

Для каждого элемента мы наблюдаем достижение B [i], какова вероятность того, что он находится на пересечении A и B, т. Е. какова вероятность того, что она уже находится в A [i]? Ну, это зависит от того, насколько «полным» является A [i]? Если A [i] полностью «полно» (т. Е. A [i] »содержит« ВСЕ элементы из распределения, которые могут достигать A [i]), то вероятность равна 1. В этом случае мощность пересечения из A [i] и B [i] действительно будет мощью B [i]. Тем не менее, почти никогда нет, что A [i] является «полным», поэтому пересечение MUCH SMALLER, чем мощность B [i].