Введение 3
Постановка задачи 5
1 Описание существующего алгоритма Ь0-семплирования 6
1.1 Введение 6
1.2 Постановка задачи 6
1.3 Общая схема алгоритма 7
1.4 Извлечение 9
1.5 Итоговые оценки 11
1.6 Объединение Ь0-семплеров 11
2 Модификация алгоритма для семплирования множества элементов ....13
2.1 Введение 13
2.2 Общая схема модифицированного алгоритма 14
2.3 Нахождение ожидаемого размера семплируемого множества 14
2.3.1 Для одного уровня 15
2.3.2 Итоговый результат 16
2.4 Нижняя оценка ожидаемого размера 17
2.5 Анализ введённой структуры данных 22
3 Проведение численных экспериментов над введённой структурой данных24
3.1 Введение 24
3.2 Анализ распределения элементов по уровням 24
3.3 Сравнение с базовой структурой данных по размеру семплируемого множества25
3.4 Анализ полученных теоретических результатов 28
3.5 Равномерность результирующего множества 28
Заключение 30
Список литературы
В последнее время возросла необходимость в алгоритмах быстрой обработки больших объёмов данных. Очень часто входных данных настолько много, что хранить их все в оперативной памяти не представляется возможным. Одним из решений данной проблемы является построение так называемых потоковых алгоритмов ( [10]).
В потоковой модели данные представлены в виде последовательности, которая обрабатывается в один или несколько проходов. Другим ограничением является объем используемой памяти. Как правило, его полагают равным 0(1).
Конечно же, ввиду поставленных условий точный ответ на задачу, как правило, получить невозможно. Но иногда возможно построить алгоритм, позволяющий найти оценку точного ответа, которая будет близка к нему с высокой вероятностью. Для получения таких оценок используют аппарат теории вероятностей.
Одним из типов потоковых алгоритмов являются так называемые линейные эскизы ( [10]). Эскиз это структура данных, хранящая краткое содержание потока, по которому она была построена. Линейные эскизы так же обладают свойством линейности, т.е. на них определена операция сложения, которая позволяет эффективно "складывать" эскизы построенные по разным потокам. Благодаря этому свойству становится возможным распределенно хранить несколько эскизов, каждый из которых обрабатывает свой поток данных. По приходе запроса все эскизы складываются в один, после чего над ним производятся необходимые действия. Так как размер эскизов мал, суммарная коммуникационная сложность тоже будет мала.
Главными факторами, по которым характеризуются потоковые алгоритмы являются объем требуемой памяти, количество проходов по потоку данных, время исполнения, а также точность получаемого ответа вместе с вероятностью его получения. Как правило, если сложность алгоритма по памяти составляет 0(/(п)), то сложность по времени не должна превышать 0(kf (п)), где к — количество проходов по потоку данных. В противном случае время работы будет неприемлемо большим.
Основным объектом изучения данной работы является структура данных равномерного или Lo-семплирования. Lo-семплер это эскиз, построенный по численному вектору, выводом которого является равномерно распределенное подмножество ненулевых элементов данного вектора. В главе1 описывается версия этой структуры данных, приведенная в статье [1]. Она позволяет с высокой вероятностью равномерно семплировать один элемент вектора. Относительно недавно этому алгоритму нашли применение в задах из теории графов. Здесь он используется для построения эскизов динамически изменяющихся графов, позволяющих хранить информацию о последних в сжатом виде. Эскизы графов такого рода используются для решения множества других задач ( [2], [3]). Ещё одним алгоритмом, где применяется Lo-семплирование является построение £-сетей - структур данных аппроксимирующих множества в (возможно многомерных) геометрических пространствах ( [8]).
В главе2 на основе описанного алгоритма вводится новый, который позволяет семплировать не один элемент, а множество элементов. Для введённого алгоритма находится мат. ожидание размера результата, а также его нижняя оценка. Полученные оценки могут быть использованы для получения множеств, которые будут в среднем иметь требуемый размер.
Построенный алгоритм может быть использован для составления выборок из динамически изменяющихся массивов. Как правило, выборки размера К = Q( f log1) достаточно для получения е-аппроксимации некоторой статистики с вероятностью 1 — 6. Данная структура данных может быть использована для работы с так называемыми обратными распределениями. Например, в контексте задачи анализа IP-траффика обратные распределения используются для распознавания вредоносных действий ( [9]). Помимо этого получение равномерной выборки из ненулевых элементов массива позволяет приблизительно решать многие другие задачи. Например, к ним относятся поточечные запросы (point queries), запросы по интервалам (range queries), нахождение "тяжелых" элементов (heavy-hitters) и квантилей ( [7]). Также, в силу того, что структура данных является эскизом, её поддержание можно осуществлять распределённо. Это позволяет легко вычислять результат от суммы и разности потоков, что может быть полезно, например, для вычисления коэффициента сходства Жаккара. Ещё стоит отметить, что существуют некоторые аналоги введенной структуры данных ( [6], [7]). Преимущества и недостатки алгоритмов обсуждаются в конце главы2.
Глава3 содержит экспериментальный анализ введённой структуры данных Lo- семплирования. Здесь над ней проводятся некоторые опыты, а также сравнение с базовой структурой данных, описанной в главе1. Проводимые численные эксперименты позволяют получить рекомендации по использованию алгоритма и показывают состоятельность полученных для него оценок.
Был введен алгоритм равномерного семплирования множества ненулевых элементов динамически изменяющегося целочисленного вектора (2.2). Получены формулы для математического ожидания размера результирующего множества (2.3), что позволяет точно оценивать поведение структуры данных. Так как на практике как правило требуется уметь получать семпл требуемого размера К, были получены условия, при которых мат. ожидание. размера семпла составляет Q(K) (2.4). Благодаря этому становится возможным устанавливать параметры алгоритма таким образом, чтобы получать в среднем на выходе желаемый результат. Сравнение с существующими аналогичными структурами данных показало, что введенный алгоритм по некоторым параметрам лучше (2.5).
В главе3 произведен экспериментальный анализ введенного алгоритма. Было произведено экспериментальное сравнение нового алгоритма с тем, на котором он был основан. Были показаны общие черты обоих алгоритмов (3.2), а также ключевые отличия, которые позволяют получать лучший результат(3.3). В итоге, была показана состоятельность полученной нижней оценки (3.4) и равномерность результирующего множества (3.5).
