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

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

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

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

IntersectionCountEstimate = A.CountEstimate() + B.CountEstimate() - Union.CountEstimate()

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

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

hyperloglog
person Alan Wolfe    schedule 08.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Причина в том, что взаимосвязь между двумя экземплярами статистики 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] был «полным», поэтому пересечение НАМНОГО МЕНЬШЕ, чем мощность B[i].

person OronNavon    schedule 16.08.2016