Конспект: частые элементы и квантили в потоке

Понятия

Тяжёлый ключ - ключ, занимающий в потоке долю больше заданной.

Ранг значения - число элементов, меньших его. Квантиль порядка φ - элемент на месте φ · n в отсортированных данных; перцентиль - квантиль с порядком в процентах.

Ошибка по рангу ε - ответом годится любое значение с рангом от (φ − ε) · n до (φ + ε) · n.

Уплотнение - сортировка буфера и замена его на каждый второй элемент удвоенного веса.

Что унести

АЛГОРИТМ БОЛЬШИНСТВА: кандидат и счётчик
счётчик 0 → кандидат = x, счётчик 1;   x = кандидат → +1;   иначе → −1
если большинство (> N/2) есть, в конце кандидат - оно;  кандидата проверяют вторым проходом
7 3 7 7 2 7 5 7 7 1 7  →  [7, 3]          7 3 7 2 7 5 1 4 6  →  [6, 1], большинства нет

МИСРЫ-ГРИСА, k счётчиков                          SPACESAVING, k счётчиков
свой ключ: +1                                     свой ключ: +1
новый, место есть: (x, 1)                         новый, место есть: (x, 1)
новый, места нет: все −1, нули удалить,           новый, места нет: выселить ключ с наименьшим m,
                  x не добавлять                                    добавить (x, m + 1)
частота − N/(k+1) ≤ счётчик ≤ частота             частота ≤ счётчик ≤ частота + m,   m ≤ N/k
в сводке всё, что чаще N/(k+1)                    в сводке всё, что чаще N/k;  сумма счётчиков = N

поток 6000, k = 9, частоты 1208 / 712 / 461:
Мисры-Гриса   699 / 205 / 2      занижение до 509, порог 600
SpaceSaving   1208 / 716 / 583   наименьший счётчик 582;  583 у ключа с частотой 2 - унаследовано

	Мисры-Гриса	SpaceSaving	count-min
ошибка	вниз, не больше `N/(k+1)`	вверх, не больше `N/k`	вверх, не больше `2N/w` с вероятностью `1 − 1/2ᵈ`
хранит ключи	да	да	нет
случайность	нет	нет	хеш-функции
удаления	нет	нет	да

КВАНТИЛИ
точно в малой памяти нельзя  ⇒  допуск по рангу ε
выборка:  s = ln(2/δ) / (2ε²)        ε = 0,05 → 738;   ε = 0,01 → 18 445
400 из 8000:  медиана 38 = 38;   p90  160 → 181, место 0,913;   p99  643 → 693, место 0,991
среднее 76,4 при медиане 38 - время ответа описывают квантилями

ХВОСТ
ε = 0,01 вокруг p99 - это любое место от 0,98 до 1,0:  значения от 482 до 997
p99,9 по выборке из 400 - её наибольший элемент;  нужен размер много больше 1/(1 − φ)
перцентили частей не усредняются:  p99 = 10 и p99 = 1000 по сто запросов  →  общий p99 = 10

УПЛОТНЕНИЕ: буфер элементов веса w
отсортировать → монетка: с первого или со второго → оставить каждый второй → вес 2w, уровень выше
любой ранг меняется не больше чем на w, в среднем на 0
случайные знаки:  m уплотнений дают сдвиг порядка √m;   без монетки - порядка m
уровней ≈ log₂(n / ёмкость);  запрос - отсортировать элементы с весами и накапливать вес

n = 4000:     ёмкость 32,  96 элементов:   p90  230, место 0,928
              ёмкость 128, 352 элемента:   p90  170, место 0,901;   p99  676, место 0,987
точно:        37 / 168 / 741
ту же точность по рангу выборка дала бы на 200 000 элементов

ЧТО ВЫБРАТЬ ДЛЯ КВАНТИЛЕЙ
ошибка по рангу, с вероятностью        KLL: уплотнение, ёмкости убывают к нижним уровням
ошибка по рангу, всегда                Гринвальда-Ханны: значения с числом представленных и допуском
границы известны заранее               гистограмма со счётчиками; объединение - сложение
точность по значению в хвосте          промежутки геометрической прогрессией (DDSketch), t-digest
наименьшее и наибольшее                две отдельные переменные

Ловушки джокера

Не проверил кандидата в большинство. Кандидат называется всегда, и без большинства он случаен.

Прочитал счётчик Мисры-Гриса как частоту. Это нижняя граница; верхняя - счётчик плюс N/(k + 1).

Дал новому ключу единицу в SpaceSaving. Поздний тяжёлый ключ вылетает как слабейший.

Взял «топ-9» из девяти счётчиков. Нижние строки сводки - унаследованные значения.

Искал ключи с долей 1% сводкой на девять счётчиков. Гарантия начинается с доли 1/(k + 1).

Усреднил перцентили серверов. Результат не является перцентилем ничего.

Принял ошибку по рангу за ошибку по значению. При 0,3% по рангу значение ушло на 9%.

Уплотнял без монетки. Сдвиги складываются вместо того, чтобы гаситься.

Поставил границы гистограммы до роста нагрузки. Всё ушло в последний промежуток.

Проверь себя

Почему взаимное уничтожение оставляет большинство? Откуда k + 1 в оценке Мисры-Гриса? Почему новый ключ в SpaceSaving наследует счётчик? Чем ошибка по рангу отличается от ошибки по значению и где это важно? Почему при уплотнении оставляют каждый второй, а не случайную половину, и зачем монетка?

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий