Проблема с подсчетом - Википедия - 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 п = | влево {{а, б, с, г} вправо } | = 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

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

Чтобы справиться с ограниченным объемом памяти, алгоритмы потоковой передачи использовать рандомизацию для получения неточной оценки отличного числа элементов, ${ 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 / (п + 1)}$ . Хеш-функция гарантирует, что ${ displaystyle h (e_ {j})}$ идентичен для всех видов ${ displaystyle e_ {j}}$ . Таким образом, наличие дубликатов не влияет на значение статистики крайнего порядка.

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

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

Нижний-м эскизы^[9] являются обобщением минимальных эскизов, которые поддерживают ${ displaystyle m}$ минимальные значения, где ${ Displaystyle м 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 Алгоритм предлагает лучшую производительность с точки зрения статистической точности и использования памяти среди всех других известных алгоритмов для взвешенной задачи.

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

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

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

[1] Ульман, Джефф; Раджараман, Ананд; Лесковец, Юре. «Майнинг потоков данных» (PDF). Цитировать журнал требует | журнал = (помощь)

[cosma2011-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.

[edithCohen-5] а ^б Коэн, Эдит (1997). «Структура оценки размера с приложениями к транзитивному замыканию и достижимости». J. Comput. Syst. Наука. 55 (3): 441–453. Дои:10.1006 / jcss.1997.1534.

[hyperloglog-6] а ^б Флажоле, Филипп; Фуси, Эрик; Гандуэ, Оливье; Менье, Фредерик (2007). «HyperLoglog: анализ алгоритма оценки мощности, близкого к оптимальному» (PDF). Анализ алгоритмов.

[7] Флажоле, Филипп; Мартин, Дж. Найджел (1985). «Вероятностные алгоритмы подсчета для приложений баз данных» (PDF). J. Comput. Syst. Наука. 31 (2): 182–209. Дои:10.1016/0022-0000(85)90041-8.

[optimalf0-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]