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

Предисловие
Благодарности
Об этой книге
Об авторах
Глава 1
Введение
1.1 Пример
1.2 Структура этой книги
1.3 Отличие этой книги от других и ее целевая аудитория
1.4 Почему массивные данные представляют трудности для современных систем?
1.4.1 Разрыв в производительности центрального процессора и памяти
1.4.2 Иерархия памяти
1.4.3 Задержка относительно пропускной способности
1.4.4 Как насчет распределенных систем?
1.5 Конструирование алгоритмов с учетом аппаратного обеспечения
Резюме
Часть I
Наброски на основе хеша
Глава 2
Обзор хеш-таблиц и современного хеширования
2.1 Хеширование повсюду
2.2 Ускоренный курс по структурам данных
2.3 Сценарии использования в современных системах
2.3.1 Дедупликация в программных решениях по резервному копированию/хранению данных
2.3.2 Обнаружение плагиата с помощью идентификации цифровых отпечатков на основе меры MOSS и алгоритма Рабина–Карпа
2.4 O(1): что в этом такого?
2.5 Урегулирование коллизий: теория и практика
2.6 Сценарий использования: принцип работы словаря в языке Python
2.7 Хеш-функция MurmurHash
2.8 Хеш-таблицы для распределенных систем: согласованное хеширование
2.8.1 Типичная проблема хеширования
2.8.2 Хеш-кольцо
2.8.3 Поиск
2.8.4 Добавление нового узла/ресурса
2.8.5 Удаление узла
2.8.6 Сценарий согласованного хеширования: хордовый протокол
2.8.7 Согласованное хеширование: упражнения по программированию
Резюме
Глава 3
Приближенная принадлежность: блумовские и порционные фильтры
3.1 Принцип работы
3.1.1 Вставка
3.1.2 Поиск
3.2 Варианты использования
3.2.1 Фильтры Блума в сетях: Squid
3.2.2 Мобильное приложение для биткоинов
3.3 Простая реализация
3.4 Конфигурирование фильтра Блума
3.4.1 Работа с фильтрами Блума: мини-эксперименты
3.5 Немного теории
3.5.1 Можно ли добиться большего?
3.6 Адаптации и альтернативы фильтров Блума
3.7 Порционный фильтр
3.7.1 Формирование частных и остатков
3.7.2 Понятие битов метаданных
3.7.3 Вставка в порционный фильтр: пример
3.7.4 Исходный код Python для поиска
3.7.5 Изменение размера и слияние
3.7.6 Соображения по поводу частоты ложноположительных результатов и пространства
3.8 Сравнение блумовских и порционных фильтров
Резюме
Глава 4
Оценивание частоты и набросок count-min
4.1 Преобладающий элемент
4.1.1 Общая задача о тяжеловесах
4.2 Набросок count-min: принцип работы
4.2.1 Обновление
4.2.2 Оценивание
4.3 Варианты использования
4.3.1 k верхних беспокойно спящих пользователей
4.3.2 Масштабирование распределительного сходства между словами
4.4 Ошибка и пространство в наброске count-min
4.5 Простая реализация наброска count-min
4.5.1 Упражнения
4.5.2 Вытекающий из формулы интуитивный вывод: немного математики
4.6 Диапазонные запросы с помощью наброска count-min
4.6.1 Диадические интервалы
4.6.2 Фаза обновления
4.6.3 Фаза оценивания
4.6.4 Вычисление диадических интервалов
Резюме
Глава 5
Оценивание кардинального числа и алгоритм HyperLogLo
5.1 Подсчет числа несовпадающих элементов в базах данных
5.2 Постепенное конструирование алгоритма HyperLogLog
5.2.1 Первая примерка: вероятностный подсчет
5.2.2 Стохастическое усреднение, или «Когда жизнь преподносит вам лимоны»
5.2.3 Алгоритм LogLog
5.2.4 Алгоритм HyperLogLog: стохастическое усреднение вместе с гармоническим средним
5.3 Пример использования: ловля червей с помощью алгоритма HyperLogLog
5.4 Но как это работает? Мини-эксперимент
5.4.1 Влияние числа корзин (m)
5.5 Пример использования: агрегация с использованием алгоритма HyperLogLog
Резюме
Часть II
Реально-временная аналитика
Глава 6
Потоковые данные: сведение всего воедино
6.1 Система обработки потоковых данных: метапример
6.1.1 Соединение на основе фильтра Блума
6.1.2 Дедупликация
6.1.3 Балансировка нагрузки и отслеживание сетевого трафика
6.2 Практические ограничения и понятия потоков данных
6.2.1 В реальном времени
6.2.2 Малое время и малое пространство
6.2.3 Сдвиги в концепциях и дрейфы концепций
6.2.4 Модель скользящего окна
6.3 Немного математики: формирование и оценивание выборок
6.3.1 Стратегия формирования смещенной выборки
6.3.2 Оценивание по репрезентативной выборке
Резюме
Глава 7
Формирование выборок из потоков данных
7.1 Формирование выборок из реперного потока
7.1.1 Формирование выборки Бернулли
7.1.2 Формирование резервуарной выборки
7.1.3 Формирование смещенной резервуарной выборки
7.2 Формирование выборок из скользящего окна
7.2.1 Формирование цепной выборки
7.2.2 Формирование приоритетной выборки
7.3 Сравнение алгоритмов формирования выборок
7.3.1 Настройка симуляции: алгоритмы и данные
Резюме
Глава 8
Приближенные квантили на потоках данных
8.1 Точные квантили
8.2 Приближенные квантили
8.2.1 Аддитивная ошибка
8.2.2 Относительная ошибка
8.2.3 Относительная ошибка в области значений данных
8.3 T-дайджест: принцип его работы
8.3.1 Дайджест
8.3.2 Масштабные функции
8.3.3 Слияние t-дайджестов
8.3.4 Пространственные границы t-дайджеста
8.4 Q-дайджест
8.4.1 Конструирование q-дайджеста с нуля
8.4.2 Слияние q-дайджестов
8.4.3 Соображения по поводу ошибки и пространства в q-дайджестах
8.4.4 Квантильные запросы с использованием q-дайджестов
8.5 Исходный код симуляции и ее результаты
Резюме
Часть III
Структуры данных для баз данных и алгоритмы внешней памятиа
Глава 9
Введение в модель внешней памятих
9.1 Модель внешней памяти: предварительные сведения
9.2 Пример 1: отыскание минимума
9.2.1 Вариант использования: минимальный медианный доход
9.3 Пример 2: двоичный поиск
9.3.1 Вариант использования в области биоинформатики
9.3.2 Анализ времени выполнения
9.4 Оптимальный поиск
9.5 Пример 3: слияние K сортированных списков
9.5.1 Слияние журналов времени/дат
9.5.2 Модель внешней памяти: простая либо упрощенческая?
9.6 Что дальше
Резюме
Глава 10
Структуры данных для баз данных: B-деревья, Bε-деревья и LSM-деревьях
10.1 Принцип работы индексации
10.2 Структуры данных этой главы
10.3 B-деревья
10.3.1 Балансирование B-дерева
10.3.2 Поиск
10.3.3 Вставка
10.3.4 Удаление
10.3.5 B+-деревья
10.3.6 Чем отличаются операции на B+-дереве
10.3.7 Вариант использования: B-деревья в MySQL (и многих других местах)
10.4 Немного математики: почему поиск в B-дереве оптимален во внешней памяти?
10.4.1 Почему вставки/удаления в B-дереве не являются оптимальными во внешней памяти
10.5 Bε-деревья
10.5.1 Bε-дерево: принцип работы
10.5.2 Механика буферизации
10.5.3 Вставка и удаление
10.5.4 Поиск
10.5.5 Анализ стоимости
10.5.6 Bε-дерево: спектр структур данных
10.5.7 Вариант использования: Bε-деревья в TokuDB
10.5.8 Торопитесь медленно, как операции ввода-вывода
10.6 Журнально-структурированные деревья слияния (LSM-деревья)
10.6.1 LSM-дерево: принцип работы
10.6.2 Анализ стоимости LSM-дерева
10.6.3 Вариант использования: LSM-деревья в Cassandra
Резюме
Глава 11
Сортировка во внешней памятих
11.1 Варианты использования сортировки
11.1.1 Планирование движений робота
11.1.2 Онкогеномика
11.2 Трудности сортировки во внешней памяти: пример
11.2.1 Двупутная сортировка слиянием во внешней памяти
11.3 Сортировка слиянием во внешней памяти (M/B-путная сортировка слиянием)
11.3.1 Поиск и сортировка: оперативная память по сравнению с внешней памятью
11.4 Как насчет внешней быстрой сортировки?
11.4.1 Двупутная быстрая сортировка во внешней памяти
11.4.2 На пути к многопутной быстрой сортировке во внешней памяти
11.4.3 Отыскание достаточного числа опорных точек
11.4.4 Отыскание достаточно хороших опорных точек
11.4.5 Сведение всего воедино
11.5 Немного математики: почему сортировка слиянием во внешней памяти оптимальна?
11.6 Подведение итогов
Резюме
Справочные материалы
Об иллюстрации на обложке
Предметный указатель