Проблема с подсчетом - Count-distinct problem

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

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

Алгоритм HyperLogLog

Основная статья: HyperLogLog

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

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

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

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

Интуиция, лежащая в основе таких оценщиков, заключается в том, что каждый эскиз несет информацию о желаемом количестве. Например, когда каждый элемент ${\displaystyle e_{j}}$ связана с униформой RV, ${\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 и другие. ^[7] описывает набросок битового массива. В этом случае элементы хешируются в битовый вектор, и эскиз содержит логическое ИЛИ всех хешированных значений. Первый асимптотически оптимальный по пространству и времени алгоритм для этой задачи был дан Дэниел М. Кейн, Джелани Нельсон и Дэвид П. Вудрафф.^[8]

Нижний-м эскизы

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

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

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

Пример: Поток взвешенных элементов ${\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}$.

В качестве примера приложения ${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ может быть IP пакеты, полученные сервером. Каждый пакет принадлежит одному из ${\displaystyle n}$ IP-потоки ${\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 Алгоритм предлагает лучшую производительность с точки зрения статистической точности и использования памяти среди всех других известных алгоритмов для взвешенной задачи.

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

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

Рекомендации

1. Ульман, Джефф; Раджараман, Ананд; Лесковец, Юре. «Майнинг потоков данных» (PDF).
2. Cosma, Ioana A .; Клиффорд, Питер (2011). «Статистический анализ вероятностных алгоритмов подсчета». Скандинавский статистический журнал. arXiv:0801.3552.
3. Жируар, Фредерик; Фуси, Эрик (2007). 2007 Труды Четвертого семинара по аналитической алгоритмике и комбинаторике (ANALCO). С. 223–231. CiteSeerX  10.1.1.214.270. Дои:10.1137/1.9781611972979.9. ISBN  978-1-61197-297-9.
4. Чассен, Филипп; Герин, Лукас (2006). «Эффективная оценка количества больших наборов данных». Материалы 4-го коллоквиума по математике и информатике.. arXiv:математика / 0701347. Bibcode:2007 математика ...... 1347C.
5. Коэн, Эдит (1997). «Структура оценки размера с приложениями к транзитивному замыканию и достижимости». J. Comput. Syst. Наука. 55 (3): 441–453. Дои:10.1006 / jcss.1997.1534.
6. Флажоле, Филипп; Фуси, Эрик; Гандуэ, Оливье; Менье, Фредерик (2007). «HyperLoglog: анализ алгоритма оценки мощности, близкого к оптимальному» (PDF). Анализ алгоритмов.
7. Флажоле, Филипп; Мартин, Дж. Найджел (1985). «Вероятностные алгоритмы подсчета для приложений баз данных» (PDF). J. Comput. Syst. Наука. 31 (2): 182–209. Дои:10.1016/0022-0000(85)90041-8.
8. Кейн, Дэниел М.; Нельсон, Джелани; Вудрафф, Дэвид П. (2010). «Оптимальный алгоритм для задачи об отдельных элементах». Материалы 29-го ежегодного симпозиума ACM по принципам систем баз данных (PODS).
9. Коэн, Эдит; Каплан, Хаим (2008). «Более точная оценка с использованием нижних k эскизов» (PDF). PVLDB.
10. Метвалли, Ахмед; Агравал, Дивьякант; Аббади, Амр Эль (2008), Зачем идти логарифмически, если мы можем идти линейно?: К эффективному точному подсчету поискового трафика, Материалы 11-й международной конференции по расширению технологии баз данных: достижения в технологии баз данных, CiteSeerX  10.1.1.377.4771
11. Коэн, Реувен; Кацир, Лиран; Ехезкель, Авив (2014). «Единая схема для обобщения оценок мощности для суммирования». Письма об обработке информации. 115 (2): 336–342. Дои:10.1016 / j.ipl.2014.10.009.