Проблема с подсчетом

В информатике проблема подсчета различных ^[1] (также известная в прикладной математике как проблема оценки мощности ) - это проблема нахождения количества различных элементов в потоке данных с повторяющимися элементами. Это хорошо известная проблема для множества приложений. Элементы могут представлять IP-адреса пакетов, проходящих через маршрутизатор , уникальных посетителей веб-сайта, элементы в большой базе данных, мотивы в последовательности ДНК или элементы сетей RFID / датчиков .

Формальное определение

Экземпляр : поток элементов с повторениями и целое число . Позвольте быть количество различных элементов, а именно , и пусть эти элементы будут .${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {s}}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle n = | \ left \ {{x_ {1}, x_ {2}, \ ldots, x_ {s}} \ right \} |}$${\ displaystyle \ left \ {{e_ {1}, e_ {2}, \ ldots, e_ {n}} \ right \}}$

Цель : Найти оценку от использования только единицы хранения, где .${\ displaystyle {\ widehat {n}}}$${\ displaystyle n}$${\ displaystyle m}$${\displaystyle m\ll n}$

Пример экземпляра для задачи оценки мощности представляет собой поток: . В этом случае .${\displaystyle a,b,a,c,d,b,d}$${\displaystyle n=|\left\{{a,b,c,d}\right\}|=4}$

Наивное решение

Наивное решение проблемы таково:

Инициализировать счетчик c нулевым значением .  Инициализируйте эффективную структуру данных словаря, D , такую ​​как хеш-таблица или дерево поиска, в которые можно быстро выполнить вставку и членство. Для каждого элемента выдается запрос о членстве. Если не является членом D ( ) Добавить в D Увеличить c на единицу, В противном случае ( ) ничего не делает. Выход .${\displaystyle c\leftarrow 0}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$ ${\displaystyle x_{i}\notin D}$ ${\displaystyle x_{i}}$${\displaystyle c\leftarrow c+1}$${\displaystyle x_{i}\in D}$${\displaystyle n=c}$

Пока количество отдельных элементов не слишком велико, D умещается в основной памяти, и можно получить точный ответ. Однако этот подход не масштабируется для ограниченного хранилища, или если вычисления, выполняемые для каждого элемента, должны быть минимизированы. В таком случае было предложено несколько алгоритмов потоковой передачи , которые используют фиксированное количество единиц хранения.${\displaystyle x_{i}}$

Алгоритм HyperLogLog

Алгоритмы потоковой передачи

Для того, чтобы обрабатывать ограниченное ограничение хранения, потоковые алгоритмы используют рандомизации , чтобы произвести без точной оценки отчетливого числа элементов, . Современные оценщики хэшируют каждый элемент в низкоразмерный эскиз данных с помощью хэш-функции . Различные методы можно классифицировать по наброскам данных, которые они хранят.${\displaystyle n}$${\displaystyle e_{j}}$${\displaystyle h(e_{j})}$

Эскизы мин / макс

В эскизах мин. / Макс. ^{[2] [3]} хранятся только минимальные / максимальные хешированные значения. Примеры известных минимальных / максимальных оценок эскизов: Chassaing et al. ^{В [4]} представлен эскиз максимума, который представляет собой несмещенную оценку с минимальной дисперсией для задачи. Оценщик непрерывных максимальных скетчей ^[5] является оценщиком максимального правдоподобия . На практике предпочтительным оценщиком является алгоритм HyperLogLog . ^[6]

Интуиция, лежащая в основе таких оценщиков, заключается в том, что каждый эскиз несет информацию о желаемом количестве. Например, когда каждый элемент связан с однородным RV , ожидаемое минимальное значение составляет . Хеш-функция гарантирует, что она идентична для всех видов . Таким образом, наличие дубликатов не влияет на значение статистики крайнего порядка.${\displaystyle e_{j}}$${\displaystyle h(e_{j})\sim U(0,1)}$${\displaystyle h(e_{1}),h(e_{2}),\ldots ,h(e_{n})}$${\displaystyle 1/(n+1)}$${\displaystyle h(e_{j})}$${\displaystyle e_{j}}$

Существуют и другие методы оценки, кроме эскизов минимума / максимума. Первая статья Flajolet et al. ^[7] описывает набросок битового массива. В этом случае элементы хешируются в битовый вектор, и скетч содержит логическое ИЛИ всех хешированных значений. Первый асимптотически оптимальный по пространству и времени алгоритм для этой задачи был предложен Дэниелом М. Кейном , Джелани Нельсон и Дэвидом П. Вудраффом. ^[8]

Внизу- м эскизы

Нижние m скетчи ^[9] являются обобщением min скетчей, которые поддерживают минимальные значения, где . См. Cosma et al. ^[2] для теоретического обзора алгоритмов оценки с раздельным подсчетом и Metwally ^[10] для практического обзора со сравнительными результатами моделирования.${\displaystyle m}$${\displaystyle m\geq 1}$

Взвешенная проблема с подсчетом различий

В его взвешенной версии каждый элемент связан с весом, и цель состоит в том, чтобы оценить общую сумму весов. Формально,

Экземпляр : поток взвешенных элементов с повторениями и целое число . Позвольте быть количество различных элементов, а именно , и пусть эти элементы будут . Наконец, пусть будет вес .${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|}$${\displaystyle \left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}}$${\displaystyle w_{j}}$${\displaystyle e_{j}}$

Цель : Найти оценку от использования только единицы хранения, где .${\displaystyle {\widehat {w}}}$${\displaystyle w=\sum _{j=1}^{n}w_{j}}$${\displaystyle m}$${\displaystyle m\ll n}$

Пример экземпляра для взвешенной задачи: . В этом случае веса равны и .${\displaystyle a(3),b(4),a(3),c(2),d(3),b(4),d(3)}$${\displaystyle e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d}$${\displaystyle w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3}$${\displaystyle \sum {w_{j}}=12}$

В качестве примера приложения могут быть IP- пакеты, полученные сервером. Каждый пакет принадлежит одному из IP-потоков . Вес может быть нагрузкой, накладываемой потоком на сервер. Таким образом, представляет собой общую нагрузку на сервер всеми потоками, которым принадлежат пакеты .${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$${\displaystyle n}$${\displaystyle e_{1},e_{2},\ldots ,e_{n}}$${\displaystyle w_{j}}$${\displaystyle e_{j}}$${\displaystyle \sum _{j=1}^{n}{w_{j}}}$${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$

Решение взвешенной задачи, связанной с подсчетом различий

Любую статистическую оценку экстремального порядка (минимальные / максимальные эскизы) для невзвешенной задачи можно обобщить до оценки для взвешенной задачи. ^[11] Например, взвешенная оценка, предложенная Коэном и др. ^[5] может быть получено, когда оценщик непрерывных максимальных скетчей расширен для решения взвешенной задачи. В частности, алгоритм HyperLogLog ^[6] может быть расширен для решения взвешенной задачи. Расширенный алгоритм HyperLogLog предлагает лучшую производительность с точки зрения статистической точности и использования памяти среди всех других известных алгоритмов для взвешенной задачи.

Смотрите также

• Счетчик мин. Эскиз
• Алгоритм потоковой передачи
• Максимальная вероятность
• Несмещенная оценка минимальной дисперсии

использованная литература