В вычислении , то отсчет мин эскиз ( СМ эскиз ) является вероятностной структурой данных , которая служит в качестве таблицы частот событий в потоке данных . Он использует хеш-функции для сопоставления событий с частотами, но в отличие от хеш-таблицы использует только сублинейное пространство за счет перерасчета некоторых событий из-за коллизий . Скетч count-min был изобретен в 2003 году Грэмом Кормодом и С. Мутху Мутукришнаном [1] и описан ими в статье 2005 года. [2]
Скетч-минимумы по сути представляют собой ту же структуру данных, что и счетные фильтры Блума, введенные в 1998 г. Фаном и др. [3] Однако они используются по-разному и, следовательно, по-разному размер: скетч count-min обычно имеет сублинейное количество ячеек, связанных с желаемым качеством приближения эскиза, в то время как счетный фильтр Блума обычно имеет размер, чтобы соответствовать количеству элементов в наборе.
Структура данных
Цель базовой версии скетча count – min - потреблять поток событий по одному и подсчитывать частоту различных типов событий в потоке. В любое время у эскиза можно запросить частоту определенного типа события i из вселенной типов событий., и вернет оценку этой частоты, которая находится на определенном расстоянии от истинной частоты с определенной вероятностью. [а]
Фактическая структура данных эскиза представляет собой двумерный массив из w столбцов и d строк. Параметры w и d фиксируются при создании эскиза и определяют потребности во времени и пространстве, а также вероятность ошибки при запросе эскиза для частоты или внутреннего продукта . С каждой из d строк связана отдельная хеш-функция; хеш-функции должны быть попарно независимыми . Параметры w и d можно выбрать, задав w = ⌈ e / ε ⌉ и d = ⌈ln 1 / δ ⌉ , где ошибка при ответе на запрос находится в пределах аддитивного коэффициента ε с вероятностью 1 - δ (см. Ниже). , e - число Эйлера .
Когда приходит новое событие типа i, мы обновляем следующим образом: для каждой строки j таблицы применяем соответствующую хеш-функцию, чтобы получить индекс столбца k = h j ( i ) . Затем увеличьте значение в строке j , столбце k на единицу.
В потоке возможны несколько типов запросов.
- Самым простым является точечный запрос , который запрашивает количество событий типа i . Расчетное количество дается наименьшим значением в таблице для i , а именно, где это таблица.
Очевидно, для каждого i имеется, где - истинная частота, с которой я появлялся в потоке.
Кроме того, эта оценка гарантирует, что с вероятностью , где - это размер потока, то есть общее количество элементов, видимых скетчем.
- Внутренний запрос продукта запрашивает скалярное произведение между гистограммами представлены два колом-минутными эскизами, а также .
Небольшие изменения в структуре данных можно использовать для наброска другой другой статистики потока.
Как и эскиз графа, эскиз графа-мин представляет собой линейный эскиз. То есть для двух потоков построение эскиза для каждого потока и суммирование эскизов дает тот же результат, что и объединение потоков и построение эскиза на объединенных потоках. Это делает скетч объединяемым и подходящим для использования в распределенных настройках в дополнение к потоковым.
Снижение предвзятости и ошибок
Одна потенциальная проблема с обычной оценкой min для набросков count-min заключается в том, что они являются предвзятыми оценками истинной частоты событий: они могут переоценивать, но никогда не недооценивать истинное количество в точечном запросе. Кроме того, хотя оценка минимума хорошо работает, когда распределение сильно искажено, другие наброски, такие как эскиз подсчета на основе средних, более точны, когда распределение недостаточно искажено. Было предложено несколько вариантов эскиза для уменьшения ошибки и уменьшения или устранения систематической ошибки. [4]
Для того, чтобы удалить смещение, то hCount * оценка [5] многократно случайным образом выбирает d случайных записей в эскизе и занимает минимум , чтобы получить объективную оценку смещения и вычитает его.
Оценка максимального правдоподобия (MLE) была получена в Ting. [6] Используя MLE, оценщик всегда может соответствовать или лучше минимального оценщика и работает хорошо, даже если распределение не искажено. В этой статье также показано, что операция устранения смещения hCount * представляет собой процедуру начальной загрузки, которая может быть эффективно вычислена без случайной выборки и может быть обобщена для любого средства оценки.
Поскольку ошибки возникают из-за хэш-столкновений с неизвестными объектами вселенной, несколько подходов корректируют столкновения, когда несколько элементов вселенной известны или запрашиваются одновременно [7] [8] [6] . Для каждого из них должна быть известна значительная часть Вселенной, чтобы получить значительные преимущества.
Консервативное обновление изменяет обновление, но не алгоритмы запроса. Чтобы подсчитать c экземпляров события типа i , сначала вычисляется оценка, затем обновления для каждой строки j . Хотя эта процедура обновления делает эскиз не линейным, его можно объединить.
Смотрите также
Заметки
- ^ Следующее обсуждение предполагает, что происходят только «положительные» события, т. Е. Частота различных типов не может уменьшаться со временем. Существуют модификации следующих алгоритмов для более общего случая, когда допускается уменьшение частот.
Рекомендации
- ^ Cormode, Graham (2009). «Счетчик-минутка» (PDF) . Энциклопедия систем баз данных . Springer. С. 511–516.
- ^ Кормод, Грэм; С. Мутукришнан (2005). «Улучшенное резюме потока данных: эскиз Count-Min и его приложения» (PDF) . J. Алгоритмы . 55 : 29–38. DOI : 10.1016 / j.jalgor.2003.12.001 .
- ^ Фан, Ли; Цао, Пей; Алмейда, Джусара; Бродер, Андрей (2000), «Сводный кэш: масштабируемый протокол общего доступа к веб-кэшу», транзакции IEEE / ACM в сети , 8 (3): 281–293, CiteSeerX 10.1.1.41.1487 , doi : 10.1109 / 90.851975 , S2CID 4779754. Предварительная версия появилась на SIGCOMM '98.
- ^ Гоял, Амит; Доме, Хэл III; Кормод, Грэм (2012). Эскизные алгоритмы для оценки точечных запросов в НЛП . Proc. EMNLP / CoNLL.
- ^ Jin, C .; Qian, W .; Сюй, X .; Чжоу, А. (2003), Динамическое поддержание частых элементов в потоке данных , CiteSeerX 10.1.1.151.5909
- ^ а б Тинг, Дэниел (2018). «Счет-Мин» : 2319–2328. DOI : 10.1145 / 3219819.3219975 . Цитировать журнал требует
|journal=
( помощь ) - ^ Дэн, Фань; Рафией, Давуд (2007), Новые алгоритмы оценки для потоковой передачи данных: Count-min может делать больше , CiteSeerX 10.1.1.552.1283
- ^ Лу, Йи; Монтанари, Андреа; Прабхакар, Баладжи; Дхармапурикар, Саранг; Каббани, Абдул (2008). «Контр косы». Обзор оценки эффективности ACM SIGMETRICS . 36 (1): 121–132. DOI : 10.1145 / 1384529.1375472 . ISSN 0163-5999 .
дальнейшее чтение
- Дворк, Синтия; Наор, Мони; Питасси, Тониан; Rothblum, Guy N .; Еханин, Сергей (2010). Пан-частные алгоритмы потоковой передачи . Proc. ICS. CiteSeerX 10.1.1.165.5923 .
- Шехтер, Стюарт; Херли, Кормак; Митценмахер, Майкл (2010). Популярность - это все: новый подход к защите паролей от атак по подбору статистических данных . Семинар USENIX по актуальным вопросам безопасности. CiteSeerX 10.1.1.170.9356 .
Внешние ссылки
- Count – min FAQ