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

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

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

Пример: Поток элементов с повторениями и целое число . Позволять быть количеством различных элементов, а именно , и пусть эти элементы будут .
Цель: Найдите оценку из используя только единицы хранения, где .

Примером экземпляра для задачи оценки мощности является поток: . В этом случае .

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

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

 Инициализировать счетчик, c, до нуля, . Инициализировать эффективную структуру данных словаря, D, например хеш-таблица или дерево поиска, в которые можно быстро выполнить вставку и членство. Для каждого элемента , выдается запрос о членстве. Если  не является членом D ()         Добавлять  к D         Увеличивать c одним,      Иначе () ничего не делать. Выход .

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

Алгоритм HyperLogLog

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

Чтобы справиться с ограниченным объемом памяти, алгоритмы потоковой передачи использовать рандомизацию для получения неточной оценки отличного числа элементов, .Современные оценщики хэш каждый элемент в низкоразмерный эскиз данных с помощью хэш-функции, . Различные методы можно классифицировать по наброскам данных, которые они хранят.

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

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

Интуиция, лежащая в основе таких оценщиков, заключается в том, что каждый эскиз несет информацию о желаемом количестве. Например, когда каждый элемент связана с униформой RV, , ожидаемое минимальное значение является . Хеш-функция гарантирует, что идентичен для всех видов . Таким образом, наличие дубликатов не влияет на значение статистики крайнего порядка.

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

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

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

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

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

Пример: Поток взвешенных элементов с повторениями и целое число . Позволять быть количеством различных элементов, а именно , и пусть эти элементы будут . Наконец, пусть быть весом .
Цель: Найдите оценку из используя только единицы хранения, где .

Пример экземпляра для взвешенной задачи: . В этом случае , веса и .

В качестве примера приложения может быть IP пакеты, полученные сервером. Каждый пакет принадлежит одному из IP-потоки . Вес может быть нагрузка, создаваемая потоком на сервере. Таким образом, представляет собой общую нагрузку на сервер всеми потоками, в которые пакеты принадлежать.

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

Любую статистическую оценку экстремального порядка (минимальные / максимальные эскизы) для невзвешенной проблемы можно обобщить до оценки для взвешенной задачи.[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.