Эскиз счета-минуты

В вычислительной технике скетч «счет-минут» ( CM-скетч ) представляет собой вероятностную структуру данных , которая служит таблицей частот событий в потоке данных . Он использует хэш-функции для сопоставления событий с частотами, но в отличие от хеш-таблицы использует только сублинейное пространство за счет пересчета некоторых событий из-за коллизий . Эскиз счета-минут был изобретен в 2003 году Грэмом Кормодом и С. Мутху Мутхукришнаном. ^{[ 1 ]} и описано ими в статье 2005 года. ^{[ 2 ]}

Эскиз подсчета минут является альтернативой эскизу подсчета и эскизу AMS и может рассматриваться как реализация подсчетного фильтра Блума (Fan et al., 1998). ^{[ 3 ]}) или многоступенчатый фильтр . ^{[ 1 ]} Однако они используются по-разному и, следовательно, имеют разные размеры: скетч с количеством ячеек обычно имеет сублинейное количество ячеек, что связано с желаемым качеством аппроксимации скетча, в то время как счетный фильтр Блума обычно имеет размер, соответствующий количеству элементов в скетче. набор.

Структура данных

Целью базовой версии скетча count-min является получение потока событий по одному за раз и подсчет частоты различных типов событий в потоке. В любой момент к скетчу можно запросить частоту определенного типа события $i$ из совокупности типов событий. ${\mathcal {U}}$ , и вернет оценку этой частоты, которая с определенной вероятностью находится в пределах определенного расстояния от истинной частоты. ^{[ а ]}

Фактическая структура данных эскиза представляет собой двумерный массив из $w$ столбцов и $d$ строк. Параметры $w$ и $d$ фиксируются при создании эскиза и определяют потребности во времени и пространстве, а также вероятность ошибки, когда в эскизе запрашивается частота или внутренний продукт . С каждой $строкой d$ связана отдельная хеш-функция; хэш-функции должны быть попарно независимыми . Параметры $w$ и $d$ можно выбрать, установив $w = ⌈ e / ε ⌉$ и $d = ⌈ln 1/ δ ⌉$ , где ошибка ответа на запрос находится в пределах аддитивного коэффициента $ε$ с вероятностью $1 - δ$ (см. ниже). , а $e$ — число Эйлера .

Когда поступает новое событие типа $i,$ мы обновляем его следующим образом: для каждой строки $j$ таблицы применяем соответствующую хеш-функцию, чтобы получить индекс столбца $k = h j (i)$ . Затем увеличьте значение в строке $j$ и столбце $k$ на единицу.

В потоке возможны несколько типов запросов.

Самым простым является точечный запрос , который запрашивает количество событий типа $i$ . Предполагаемое количество определяется наименьшим значением в таблице для $i$ , а именно ${\hat {a}}_{i}=\min _{j}\mathrm {count} [j,h_{j}(i)]$ , где $\mathrm {count}$ это стол.

Очевидно, что для каждого $i$ имеется $a_{i}\leq {\hat {a}}_{i}$ , где $a_{i}$ — это истинная частота, с которой $я$ появлялся в потоке.

Кроме того, эта оценка имеет гарантию того, что ${\hat {a}}_{i}\leq a_{i}+\varepsilon N$ с вероятностью $1-\delta$ , где $N=\sum _{i\in {\mathcal {U}}}a_{i}$ — размер потока, т. е. общее количество элементов, видимых эскизом.

Запрос внутреннего продукта запрашивает внутренний продукт между гистограммами, представленными двумя эскизами с количеством минут: $\mathrm {count} _{a}$ и $\mathrm {count} _{b}$ .

Небольшие изменения в структуре данных можно использовать для создания эскизов другой статистики потока.

Как и эскиз подсчета , эскиз Count-min представляет собой линейный эскиз. То есть, учитывая два потока, построение эскиза для каждого потока и суммирование эскизов дает тот же результат, что и объединение потоков и построение эскиза на основе объединенных потоков. Это делает скетч объединяемым и пригодным для использования в распределенных настройках в дополнение к потоковым.

Снижение предвзятости и ошибок

Одна из потенциальных проблем с обычными оценщиками min для эскизов count-min заключается в том, что они являются предвзятыми оценками истинной частоты событий: они могут переоценивать, но никогда не недооценивать истинное количество в точечном запросе. Более того, хотя мини-оценщик хорошо работает, когда распределение сильно искажено, другие эскизы, такие как эскиз подсчета, основанный на средних, более точны, когда распределение недостаточно искажено. Было предложено несколько вариантов эскиза, чтобы уменьшить ошибку и уменьшить или устранить предвзятость. ^{[ 4 ]}

Чтобы устранить предвзятость, hCount* оценщик ^{[ 5 ]} неоднократно случайным образом выбирает d случайных записей в эскизе, берет минимум, чтобы получить несмещенную оценку смещения, и вычитает его.

Оценка максимального правдоподобия (MLE) была получена в Ting. ^{[ 6 ]} Используя MLE, оценщик всегда может соответствовать минимальному оценщику или превосходить его и работает хорошо, даже если распределение не искажено. В этой статье также показано, что операция устранения смещения hCount* представляет собой процедуру начальной загрузки, которую можно эффективно вычислить без случайной выборки и можно обобщить на любой оценщик.

Поскольку ошибки возникают в результате коллизий хеша с неизвестными элементами юниверса, несколько подходов корректируют коллизии, когда несколько элементов юниверса известны или запрашиваются одновременно. ^{[ 7 ]} ^{[ 8 ]} ^{[ 6 ]}. Для каждого из них необходимо знать большую часть Вселенной, чтобы наблюдать значительную выгоду.

Консервативное обновление меняет само обновление, но не алгоритмы запроса. Чтобы подсчитать $c$ экземпляров события типа $i$ , сначала вычисляется оценка ${\hat {a}}_{i}=\min _{j}\mathrm {count} [j,h_{j}(i)]$ , затем обновления $\mathrm {count} [j,h_{j}(i)]\leftarrow \max\{\mathrm {count} [j,h_{j}(i)],{\hat {a_{i}}}+c\}$ для каждой строки $j$ . Хотя эта процедура обновления делает эскиз не линейным, его по-прежнему можно объединять.

См. также

Примечания

^ Следующее обсуждение предполагает, что происходят только «положительные» события, т. е. частота различных типов не может уменьшаться с течением времени. Существуют модификации следующих алгоритмов для более общего случая, когда частотам разрешено уменьшаться.

Ссылки

^ Перейти обратно: ^а ^б Кормод, Грэм (2009). «Счет-минутный эскиз» (PDF) . Энциклопедия систем баз данных . Спрингер. стр. 511–516.
^ Кормод, Грэм; С. Мутукришнан (2005). «Улучшенная сводка потока данных: эскиз Count-Min и его приложения» (PDF) . Дж. Алгоритмы . 55 : 29–38. дои : 10.1016/j.jalgor.2003.12.001 . Архивировано из оригинала (PDF) 25 мая 2023 г.
^ Фан, Ли; Цао, Пей; Алмейда, Хуссара ; Бродер, Андрей (2000), «Сводный кэш: масштабируемый протокол совместного использования глобального веб-кеша», Транзакции IEEE/ACM в сети , 8 (3): 281–293, CiteSeerX 10.1.1.41.1487 , doi : 10.1109/90.851975 , S2CID 4779754 . Предварительная версия появилась на SIGCOMM '98.
^ Гоял, Амит; Доме, Хэл III; Кормод, Грэм (2012). Набросайте алгоритмы оценки точечных запросов в НЛП . Учеб. EMNLP/CoNLL.
^ Джин, К.; Цянь, В.; Сюй, Х.; Чжоу, А. (2003), Динамическое сохранение часто встречающихся элементов в потоке данных , CiteSeerX 10.1.1.151.5909.
^ Перейти обратно: ^а ^б Тинг, Дэниел (2018). «Граф-Мин». Материалы 24-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 2319–2328. дои : 10.1145/3219819.3219975 . ISBN 9781450355520 .
^ Дэн, Фань; Рафии, Давуд (2007), Новые алгоритмы оценки для потоковых данных: Count-min может сделать больше , CiteSeerX 10.1.1.552.1283
^ Лу, Йи; Монтанари, Андреа; Прабхакар, Баладжи; Дхармапурикар, Саранг; Каббани, Абдул (2008). «Встречные косы». Обзор оценки производительности ACM SIGMETRICS . 36 (1): 121–132. дои : 10.1145/1384529.1375472 . ISSN 0163-5999 .

Дальнейшее чтение

Дворк, Синтия; Наор, Деньги; Петерси, Тоньянн; Ротблюм, Гай Н.; Еханин, Сергей (2010). Алгоритмы общечастной потоковой передачи . Учеб. ИКС. CiteSeerX 10.1.1.165.5923 .
Шехтер, Стюарт; Херли, Кормак; Митценмахер, Майкл (2010). Популярность решает все: новый подход к защите паролей от атак с подбором статистических данных . Семинар USENIX по актуальным темам безопасности. CiteSeerX 10.1.1.170.9356 .

Внешние ссылки

Часто задаваемые вопросы по счету и минуте

[4] Следующее обсуждение предполагает, что происходят только «положительные» события, т. е. частота различных типов не может уменьшаться с течением времени. Существуют модификации следующих алгоритмов для более общего случая, когда частотам разрешено уменьшаться.

[ency-1] Перейти обратно: ^а ^б Кормод, Грэм (2009). «Счет-минутный эскиз» (PDF) . Энциклопедия систем баз данных . Спрингер. стр. 511–516.

[2] Кормод, Грэм; С. Мутукришнан (2005). «Улучшенная сводка потока данных: эскиз Count-Min и его приложения» (PDF) . Дж. Алгоритмы . 55 : 29–38. дои : 10.1016/j.jalgor.2003.12.001 . Архивировано из оригинала (PDF) 25 мая 2023 г.

[3] Фан, Ли; Цао, Пей; Алмейда, Хуссара ; Бродер, Андрей (2000), «Сводный кэш: масштабируемый протокол совместного использования глобального веб-кеша», Транзакции IEEE/ACM в сети , 8 (3): 281–293, CiteSeerX 10.1.1.41.1487 , doi : 10.1109/90.851975 , S2CID 4779754 . Предварительная версия появилась на SIGCOMM '98.

[goyal-5] Гоял, Амит; Доме, Хэл III; Кормод, Грэм (2012). Набросайте алгоритмы оценки точечных запросов в НЛП . Учеб. EMNLP/CoNLL.

[6] Джин, К.; Цянь, В.; Сюй, Х.; Чжоу, А. (2003), Динамическое сохранение часто встречающихся элементов в потоке данных , CiteSeerX 10.1.1.151.5909.

[Ting2018-7] Перейти обратно: ^а ^б Тинг, Дэниел (2018). «Граф-Мин». Материалы 24-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 2319–2328. дои : 10.1145/3219819.3219975 . ISBN 9781450355520 .

[8] Дэн, Фань; Рафии, Давуд (2007), Новые алгоритмы оценки для потоковых данных: Count-min может сделать больше , CiteSeerX 10.1.1.552.1283

[LuMontanari2008-9] Лу, Йи; Монтанари, Андреа; Прабхакар, Баладжи; Дхармапурикар, Саранг; Каббани, Абдул (2008). «Встречные косы». Обзор оценки производительности ACM SIGMETRICS . 36 (1): 121–132. дои : 10.1145/1384529.1375472 . ISSN 0163-5999 .

[ 1 ]

[ 2 ]

[ 3 ]

[ а ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]