Конспект: потоковые алгоритмы и резервуарная выборка

Понятия

Потоковый алгоритм - один проход по данным, состояние много меньше потока, малое время на элемент.

Приближение с параметрами ε, δ - ошибка не больше ε с вероятностью не меньше 1 − δ.

Объединяемая сводка - из сводок двух частей данных получается сводка целого.

Резервуар - k мест, в которых в любой момент лежит равновероятная выборка из уже пришедших элементов.

Мультимножество - набор, где важна кратность элементов и не важен порядок.

Второй момент F₂ - сумма квадратов частот ключей.

Что унести

ТОЧНО, В ПОСТОЯННОЙ ПАМЯТИ                      НЕ СЧИТАЕТСЯ ТОЧНО БЕЗ ПАМЯТИ НА ВСЁ
количество, сумма, наименьшее, наибольшее       число различных элементов
среднее:    a = a + (x − a) / n                 медиана                  
дисперсия:  накопить (x − a_старое)·(x − a_новое)     был ли уже такой элемент
пропущенное число: n(n + 1)/2 − сумма, или исключающее ИЛИ

почему: по памяти точного счётчика различных восстанавливается множество виденных → N бит

ОБЪЕДИНЕНИЕ СВОДОК
сумма - сложение;  наименьшее - минимум;  среднее - только вместе с количеством
200 элементов со средним 10 и 800 со средним 20:  18, а не 15

РЕЗЕРВУАРНАЯ ВЫБОРКА, k мест
элемент номер i:   i ≤ k - положить;   иначе j = случайное от 0 до i − 1,  при j < k:  резервуар[j] = x
при n ≥ k: P(позиция i в выборке) = k/n;  при n < k хранят все n
один из восьми, 6000 опытов:  738 … 781 при ожидаемых 750
ошибка «заменять с вероятностью 1/2»:  265 … 745 при ожидаемых 450
объединение:  хранить число виденных;  для k = 1 взять первую с вероятностью n₁/(n₁ + n₂)

ВЗВЕШЕННАЯ ВЫБОРКА
один элемент:   W = W + w;  заменить выбранного с вероятностью w / W
k элементов:    ключ u^(1/w),  хранить k наибольших          на практике сравнивают ln(u) / w
почему степень: наибольшее из w случайных чисел ≤ t с вероятностью tʷ - как и u^(1/w)
веса 1, 2, 3, 4:  доли 0,097  0,202  0,296  0,405
ключ u·w неверен: для весов 1 и 2 лёгкий выигрывает в 1/4 случаев вместо 1/3
объединение:  слить наборы пар «ключ, элемент», оставить k наибольших - счётчики не нужны

ВЫБОРКА ПО ХЕШУ ИДЕНТИФИКАТОРА
оставить событие, если хеш(пользователь) mod 100 = 0
выбирает 1% ПОЛЬЗОВАТЕЛЕЙ со всеми их событиями;  решение одинаково на всех машинах
резервуар и ключи выбирают СОБЫТИЯ: активные пользователи в такой выборке перепредставлены

ОТПЕЧАТОК МУЛЬТИМНОЖЕСТВА
y = y · (x − a) mod p; p простое, коды 0 ≤ a < p инъективны
x - равномерная общая точка; длины потоков ≤ n
разные отпечатки доказывают различие
для фиксированных разных входов P(коллизия) ≤ n/p
3, 5 и 4, 4:  количество и сумма совпадают, отпечатки нет

ВТОРОЙ МОМЕНТ
знак s(ключ) = ±1, постоянный;   Z = Z + s(ключ) на каждый элемент;   E[Z²] = F₂
Z² = Σ fᵢ²  +  перекрёстные слагаемые со случайными знаками, в среднем ноль
дисперсия до 2·F₂²  ⇒  среднее по группе, затем медиана групп
замер: точно 488 874;  средние групп 139 294 … 899 380;  медиана 475 705;  общее среднее 436 066

Гарантия AMS: четыре независимых знака дают Var(Z²)≤2F₂²; среднее O(ε⁻²) копий и медиана O(log(1/δ)) групп обеспечивают относительную ошибку ε с вероятностью отказа δ.

Джонсон-Линденштраус: общая случайная линейная проекция в O(ε⁻²log(N/δ)) координат сохраняет попарные квадраты евклидовых расстояний конечного набора с отказом не больше δ.

Корсет сохраняет заданное семейство стоимостей, а не все свойства данных; t-спаннер сохраняет расстояния с растяжением не больше t. Для потоков вставок невзвешенных рёбер работает жадное сохранение длинных связей.

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

Посчитал различных множеством. Память растёт вместе с данными - это доказанное свойство задачи.

Объединил средние без количеств. Среднее средних верно только для частей равного размера.

Написал randrange(k) вместо randrange(videl). Выборка состоит из последних элементов потока.

Взял первые k или каждый сотый. Первые описывают начало потока, каждый сотый ловит периодичность.

Слил две выборки без счётчиков. Строки сервера с малым потоком оказываются перепредставлены.

Взял ключ u · w. Тяжёлые элементы выбираются чаще положенного.

Оценил долю пользователей по выборке событий. Активные пользователи весят в ней больше.

Сверил потоки по сумме или по исключающему ИЛИ. Замена 3, 5 на 4, 4 и пара дубликатов проходят незамеченными.

Перевыбрал знак ключа при повторе. Счётчик превращается в сумму независимых ±1 и перестаёт зависеть от частот.

Проверь себя

Какие вопросы о потоке решаются точно и почему остальные - нет? Почему шанс k/i для новичка даёт всем k/n? Что нужно хранить, чтобы объединять выборки, и почему ключам это не нужно? Чем выборка по хешу отличается от резервуарной? Почему квадрат суммы знаков в среднем равен сумме квадратов частот?

Понятия

Что унести

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

Проверь себя

Комментарии

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