Алгоритмы и структуры для массивных наборов данных

Предисловие....12 Благодарности....14 Об этой книге....15 Об авторах....19 Глава 1....20 Введение....20 1.1 Пример....22 1.2 Структура этой книги....29 1.3 Отличие этой книги от других и ее целевая аудитория....29 1.4 Почему массивные данные представляют трудности для современных систем?....31 1.4.1 Разрыв в производительности центрального процессора и памяти....31 1.4.2 Иерархия памяти....31 1.4.3 Задержка относительно пропускной способности....33 1.4.4 Как насчет распределенных систем?....34 1.5 Конструирование алгоритмов с учетом аппаратного обеспечения....34 Резюме....36 Часть I....38 Наброски на основе хеша....38 Глава 2....39 Обзор хеш-таблиц и современного хеширования....39 2.1 Хеширование повсюду....40 2.2 Ускоренный курс по структурам данных....42 2.3 Сценарии использования в современных системах....45 2.3.1 Дедупликация в программных решениях по резервному копированию/хранению данных....45 2.3.2 Обнаружение плагиата с помощью идентификации цифровых отпечатков на основе меры MOSS и алгоритма Рабина–Карпа....47 2.4 O(1): что в этом такого?....49 2.5 Урегулирование коллизий: теория и практика....51 2.6 Сценарий использования: принцип работы словаря в языке Python....54 2.7 Хеш-функция MurmurHash....55 2.8 Хеш-таблицы для распределенных систем: согласованное хеширование....57 2.8.1 Типичная проблема хеширования....57 2.8.2 Хеш-кольцо....59 2.8.3 Поиск....61 2.8.4 Добавление нового узла/ресурса....62 2.8.5 Удаление узла....64 2.8.6 Сценарий согласованного хеширования: хордовый протокол....68 2.8.7 Согласованное хеширование: упражнения по программированию....70 Резюме....70 Глава 3....72 Приближенная принадлежность: блумовские и порционные фильтры....72 3.1 Принцип работы....75 3.1.1 Вставка....75 3.1.2 Поиск....76 3.2 Варианты использования....77 3.2.1 Фильтры Блума в сетях: Squid....77 3.2.2 Мобильное приложение для биткоинов....77 3.3 Простая реализация....79 3.4 Конфигурирование фильтра Блума....80 3.4.1 Работа с фильтрами Блума: мини-эксперименты....83 3.5 Немного теории....84 3.5.1 Можно ли добиться большего?....86 3.6 Адаптации и альтернативы фильтров Блума....88 3.7 Порционный фильтр....89 3.7.1 Формирование частных и остатков....90 3.7.2 Понятие битов метаданных....92 3.7.3 Вставка в порционный фильтр: пример....93 3.7.4 Исходный код Python для поиска....95 3.7.5 Изменение размера и слияние....98 3.7.6 Соображения по поводу частоты ложноположительных результатов и пространства....99 3.8 Сравнение блумовских и порционных фильтров....100 Резюме....102 Глава 4....104 Оценивание частоты и набросок count-min....104 4.1 Преобладающий элемент....106 4.1.1 Общая задача о тяжеловесах....108 4.2 Набросок count-min: принцип работы....109 4.2.1 Обновление....109 4.2.2 Оценивание....109 4.3 Варианты использования....111 4.3.1 k верхних беспокойно спящих пользователей....111 4.3.2 Масштабирование распределительного сходства между словами....115 4.4 Ошибка и пространство в наброске count-min....118 4.5 Простая реализация наброска count-min....119 4.5.1 Упражнения....120 4.5.2 Вытекающий из формулы интуитивный вывод: немного математики....121 4.6 Диапазонные запросы с помощью наброска count-min....122 4.6.1 Диадические интервалы....123 4.6.2 Фаза обновления....124 4.6.3 Фаза оценивания....126 4.6.4 Вычисление диадических интервалов....127 Резюме....129 Глава 5....131 Оценивание кардинального числа и алгоритм HyperLogLo....131 5.1 Подсчет числа несовпадающих элементов в базах данных....132 5.2 Постепенное конструирование алгоритма HyperLogLog....134 5.2.1 Первая примерка: вероятностный подсчет ....135 5.2.2 Стохастическое усреднение, или «Когда жизнь преподносит вам лимоны»....136 5.2.3 Алгоритм LogLog....138 5.2.4 Алгоритм HyperLogLog: стохастическое усреднение вместе с гармоническим средним....140 5.3 Пример использования: ловля червей с помощью алгоритма HyperLogLog....143 5.4 Но как это работает? Мини-эксперимент....145 5.4.1 Влияние числа корзин (m)....147 5.5 Пример использования: агрегация с использованием алгоритма HyperLogLog....149 Резюме....153 Часть II....154 Реально-временная аналитика....154 Глава 6....155 Потоковые данные: сведение всего воедино....155 6.1 Система обработки потоковых данных: метапример....160 6.1.1 Соединение на основе фильтра Блума....161 6.1.2 Дедупликация....164 6.1.3 Балансировка нагрузки и отслеживание сетевого трафика....165 6.2 Практические ограничения и понятия потоков данных....168 6.2.1 В реальном времени....168 6.2.2 Малое время и малое пространство....169 6.2.3 Сдвиги в концепциях и дрейфы концепций....170 6.2.4 Модель скользящего окна....171 6.3 Немного математики: формирование и оценивание выборок....173 6.3.1 Стратегия формирования смещенной выборки....174 6.3.2 Оценивание по репрезентативной выборке....178 Резюме....179 Глава 7....181 Формирование выборок из потоков данных....181 7.1 Формирование выборок из реперного потока....182 7.1.1 Формирование выборки Бернулли....182 7.1.2 Формирование резервуарной выборки....187 7.1.3 Формирование смещенной резервуарной выборки....193 7.2 Формирование выборок из скользящего окна....198 7.2.1 Формирование цепной выборки....199 7.2.2 Формирование приоритетной выборки....203 7.3 Сравнение алгоритмов формирования выборок....207 7.3.1 Настройка симуляции: алгоритмы и данные....207 Резюме....211 Глава 8....213 Приближенные квантили на потоках данных....213 8.1 Точные квантили....214 8.2 Приближенные квантили....217 8.2.1 Аддитивная ошибка....217 8.2.2 Относительная ошибка....219 8.2.3 Относительная ошибка в области значений данных....220 8.3 T-дайджест: принцип его работы....220 8.3.1 Дайджест....221 8.3.2 Масштабные функции ....222 8.3.3 Слияние t-дайджестов....227 8.3.4 Пространственные границы t-дайджеста....230 8.4 Q-дайджест....231 8.4.1 Конструирование q-дайджеста с нуля....232 8.4.2 Слияние q-дайджестов....234 8.4.3 Соображения по поводу ошибки и пространства в q-дайджестах....235 8.4.4 Квантильные запросы с использованием q-дайджестов....236 8.5 Исходный код симуляции и ее результаты ....237 Резюме....242 Часть III....244 Структуры данных для баз данных и алгоритмы внешней памятиа....244 Глава 9....245 Введение в модель внешней памятих....245 9.1 Модель внешней памяти: предварительные сведения....247 9.2 Пример 1: отыскание минимума....250 9.2.1 Вариант использования: минимальный медианный доход....250 9.3 Пример 2: двоичный поиск....253 9.3.1 Вариант использования в области биоинформатики....253 9.3.2 Анализ времени выполнения....255 9.4 Оптимальный поиск....257 9.5 Пример 3: слияние K сортированных списков....259 9.5.1 Слияние журналов времени/дат....260 9.5.2 Модель внешней памяти: простая либо упрощенческая?....264 9.6 Что дальше....265 Резюме....265 Глава 10....267 Структуры данных для баз данных: B-деревья, Bε-деревья и LSM-деревьях....267 10.1 Принцип работы индексации....268 10.2 Структуры данных этой главы....270 10.3 B-деревья....272 10.3.1 Балансирование B-дерева....273 10.3.2 Поиск....274 10.3.3 Вставка....274 10.3.4 Удаление....277 10.3.5 B+-деревья....281 10.3.6 Чем отличаются операции на B+-дереве....282 10.3.7 Вариант использования: B-деревья в MySQL (и многих других местах)....282 10.4 Немного математики: почему поиск в B-дереве оптимален во внешней памяти?....283 10.4.1 Почему вставки/удаления в B-дереве не являются оптимальными во внешней памяти....286 10.5 Bε-деревья....286 10.5.1 Bε-дерево: принцип работы....287 10.5.2 Механика буферизации....287 10.5.3 Вставка и удаление....289 10.5.4 Поиск....290 10.5.5 Анализ стоимости....291 10.5.6 Bε-дерево: спектр структур данных....292 10.5.7 Вариант использования: Bε-деревья в TokuDB....293 10.5.8 Торопитесь медленно, как операции ввода-вывода....294 10.6 Журнально-структурированные деревья слияния (LSM-деревья)....295 10.6.1 LSM-дерево: принцип работы....297 10.6.2 Анализ стоимости LSM-дерева ....300 10.6.3 Вариант использования: LSM-деревья в Cassandra....300 Резюме....302 Глава 11....303 Сортировка во внешней памятих....303 11.1 Варианты использования сортировки....304 11.1.1 Планирование движений робота....304 11.1.2 Онкогеномика....305 11.2 Трудности сортировки во внешней памяти: пример....307 11.2.1 Двупутная сортировка слиянием во внешней памяти....308 11.3 Сортировка слиянием во внешней памяти (M/B-путная сортировка слиянием)....310 11.3.1 Поиск и сортировка: оперативная память по сравнению с внешней памятью....312 11.4 Как насчет внешней быстрой сортировки?....314 11.4.1 Двупутная быстрая сортировка во внешней памяти....315 11.4.2 На пути к многопутной быстрой сортировке во внешней памяти....315 11.4.3 Отыскание достаточного числа опорных точек....317 11.4.4 Отыскание достаточно хороших опорных точек....318 11.4.5 Сведение всего воедино....319 11.5 Немного математики: почему сортировка слиянием во внешней памяти оптимальна?....319 11.6 Подведение итогов....322 Резюме....322 Справочные материалы....324 Об иллюстрации на обложке....332 Предметный указатель....333