| Часть серии по |
| Вероятностные структуры данных |
|---|
| Случайные деревья |
| Связанный |
В вычислении , то отсчет мин эскиз ( СМ эскиз ) является вероятностной структурой данных , которая служит в качестве таблицы частот событий в потоке данных . Он использует хэш-функции для сопоставления событий с частотами, но в отличие от хеш-таблицы использует только сублинейное пространство за счет перерасчета некоторых событий из-за коллизий . Скетч count-min был изобретен в 2003 году Грэмом Кормодом и С. Мутху Мутукришнаном [1] и описан ими в статье 2005 года. [2]
Скетчи Count-min по существу имеют ту же структуру данных, что и счетные фильтры Блума, введенные в 1998 г. Fan et al. [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 , а именно , где - таблица.
![{\ hat a} _ {i} = \ min _ {j} {\ mathrm {count}} [j, h_ {j} (i)]](https://wikimedia.org/api/rest_v1/media/math/render/svg/12f24e88e904481b525a7a814a131ae51d838d80)
Очевидно, что для каждого i есть , где - истинная частота, с которой i появлялся в потоке.
Кроме того, эта оценка гарантирует, что с вероятностью , где - размер потока, т. Е. Общее количество элементов, видимых эскизом.
- В запросе внутреннего продукта запрашивается внутренний продукт между гистограммами, представленными двумя эскизами count-min, и .
Небольшие изменения в структуре данных можно использовать для наброска другой другой статистики потока.
Как и эскиз графа, эскиз графа мин представляет собой линейный эскиз. То есть для двух потоков построение эскиза в каждом потоке и суммирование эскизов дает тот же результат, что и объединение потоков и построение эскиза на объединенных потоках. Это делает скетч объединяемым и подходящим для использования в распределенных настройках в дополнение к потоковым.
Снижение предвзятости и ошибок [ править ]
Одна потенциальная проблема с обычной оценкой минимума для набросков count-min заключается в том, что они являются предвзятыми оценками истинной частоты событий: они могут переоценивать, но никогда не недооценивать истинное количество в точечном запросе. Кроме того, хотя оценка минимума работает хорошо, когда распределение сильно искажено, другие эскизы, такие как эскиз подсчета на основе средних, более точны, когда распределение недостаточно искажено. Было предложено несколько вариантов эскиза для уменьшения ошибки и уменьшения или устранения систематической ошибки. [4]
Для того, чтобы удалить смещение, то hCount * оценка [5] многократно случайным образом выбирает d случайных записей в эскизе и занимает минимум , чтобы получить объективную оценку смещения и вычитает его.
Оценка максимального правдоподобия (MLE) была получена в Ting. [6] Используя MLE, оценщик всегда может соответствовать или лучше минимального оценщика и работает хорошо, даже если распределение не искажено. В этой статье также показано, что операция устранения смещения hCount * представляет собой процедуру начальной загрузки, которая может быть эффективно вычислена без случайной выборки и может быть обобщена для любого средства оценки.
Поскольку ошибки возникают из-за хеш-столкновений с неизвестными объектами вселенной, несколько подходов исправляют столкновения, когда несколько элементов вселенной известны или запрашиваются одновременно [7] [8] [6] . Для каждого из них должна быть известна значительная часть Вселенной, чтобы получить значительные преимущества.
Консервативное обновление изменяет обновление, но не алгоритмы запроса. Чтобы подсчитать c экземпляров события типа i , сначала вычисляется оценка , а затем выполняется обновление для каждой строки j . Хотя эта процедура обновления делает эскиз не линейным, его все же можно объединить.
![{\ mathrm {count}} [j, h_ {j} (i)] \ leftarrow \ max \ {{\ mathrm {count}} [j, h_ {j} (i)], {\ hat {a_ {i) }}} + c \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90d2b8fbfaafb793895ddda34a4a43eee448f9f7)
См. Также [ править ]
- Хеширование функций
- Хеширование с учетом местоположения
- MinHash
- Граф эскиз
Примечания [ править ]
- ^ Следующее обсуждение предполагает, что происходят только «положительные» события, то есть частота различных типов не может уменьшаться со временем. Существуют модификации следующих алгоритмов для более общего случая, когда допускается уменьшение частот.
Ссылки [ править ]
- ^ 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 . Cite journal requires
|journal=(help) - ^ Дэн, Вентилятор; Рафией, Давуд (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
