Почему Hyperloglog работает и какие реальные проблемы?

("Приложения для оценки количества элементов", слишком широко? Я хотел бы добавить это просто как комментарий, но это не подходит).

Я бы посоветовал вам обратиться к многочисленным академическим исследованиям по этому вопросу; обычно научные статьи содержат некоторую информацию о "предыдущем исследовании предмета", а также "приложениях, для которых предмет использовался". Вы можете начать с просмотра интересующих ссылок, как указано в следующей статье:

• HyperLogLog: анализ почти оптимального алгоритма оценки кардинальности, П. Флажоле и другие.

... Эта проблема привлекла большое внимание за последние два десятилетия, находя постоянно растущее число приложений в сети и мониторинге трафика, таких как обнаружение распространения червей, сетевых атак (например, путем отказа в обслуживании) и спама на основе ссылок в Интернете [3]. Например, поток данных по сети состоит из последовательности пакетов, каждый пакет имеет заголовок, который содержит пару адресов (источник-назначение), за которыми следует основная часть конкретных данных; количество отдельных пар заголовков (мощность мультимножества) в различных временных интервалах является важным показателем для обнаружения атак и мониторинга трафика, поскольку оно регистрирует количество отдельных активных потоков. В самом деле, черви и вирусы обычно распространяются, открывая большое количество различных соединений, и хотя они вполне могут оставаться незамеченными среди огромного трафика, их активность выявляется после измерения мощностей (см. наглядное изложение Эстана и Варгезе в [11]). . Другие приложения оценки мощности включают интеллектуальный анализ массивных наборов данных — текстов на естественном языке [4, 5], биологических данных [17, 18], очень больших структурированных баз данных или интернет-графа, где авторы [22] сообщают вычислительный выигрыш в 500+ раз, достигнутый вероятностными оценщиками мощности.

В моей работе HyperLogLog используется для оценки количества уникальных пользователей или уникальных устройств, использующих разные пути кода в онлайн-сервисах. Например, сколько пользователей затронуты каждым типом ошибки службы? Сколько пользователей используют каждую функцию? Есть МНОГО интересных вопросов, на которые HyperLogLog позволяет нам ответить.