Обзор статьи; год публикации: 2017

Газета, созданная Google, содержит идеи, заставляющие задуматься, и ее запомнят надолго.

Ключевой вопрос документа: Можно ли заменить индексирование структур данных (например, B-Trees или HashMaps) моделями машинного обучения (например, нейронными сетями)? (рисунок 1).

Этот простой вопрос полностью сломал мое и другие представления о том, что такое индекс:

Before: indexes == data structures
Now: indexes == models

Раньше у меня было смутное представление о том, что индексы - это умные структуры данных и алгоритмы. Однако более абстрактно индексы можно рассматривать как модели: f(key) == pos. То есть, учитывая key, вернуть (pos)ition, как смоделировано f. Таким образом, f действительно может быть структурой данных / алгоритмом, но в более общем смысле любой функцией, в частности моделью машинного обучения. Следовательно, мы потенциально можем машинно обучиться тому, как эффективно индексировать данные, чтобы (1) ускорить поиск или вставку и (2) потреблять мало памяти.

Такие структуры, как B-деревья, HashMaps или фильтры Блума, дают надежные гарантии погрешности и сложности вычислений. Априори казалось бы, что модели машинного обучения (ML) не могут предложить такие же гарантии. В этой статье авторы добиваются того, чтобы показать именно следующее: модели машинного обучения могут иметь аналогичные или даже лучшие гарантии. Не только это, но и модели машинного обучения могут быть даже более эффективными (для (1) скорости и (2) памяти). Почему? B-деревья и тому подобное - это структуры данных общего назначения. Для сравнения, модели машинного обучения потенциально могут учиться и использовать определенные шаблоны в (реальных) данных.

После постановки основного вопроса авторы демонстрируют, что традиционные структуры данных действительно можно заменить (ML-) изученными индексами, демонстрируя свои собственные реализации ML в трех разных типах. индексов: 1) индекс диапазона (т. е. задан ключ, возвращает диапазон отсортированных позиций), 2) индекс пункта (т. е. задан ключ, возвращает один несортированная позиция) и 3) индекс существования (т. е. по заданному ключу вернуть, существует он или нет). Согласно основному вопросу, диапазонные и точечные индексы можно рассматривать как регрессионные модели, а индекс существования - как задачу классификации.

Затем авторы провели сравнительный анализ своих реализаций машинного обучения. Короче говоря, их изученные индексы показали: 1) по сравнению с B-деревьями для индексов диапазона: до 70% быстрее поиск и почти на 100% (да) меньше памяти; 2) по сравнению с HashMaps для точечных индексов: немного более медленное время доступа приводит к уменьшению объема памяти до 20%; и 3) по сравнению с фильтрами Блума для индексов существования: до 40% меньше памяти.

Вторым по значимости вкладом статьи является практическая реализация индекса изученного диапазона (то есть по сравнению с B-деревьями) в качестве смеси экспертов. Они назвали это: индекс рекурсивной модели (RMI) (рис. 3). Авторы продемонстрировали на практике преимущества такой многоуровневой и иерархической системы. Например, используемые для моделирования кумулятивной функции распределения (CDF) для индекса диапазона, верхние слои могут лучше аппроксимировать общую форму CDF, тогда как листовые модели могут решать и фокусироваться на последняя миля, то есть последние экземпляры данных, распределение которых перестало быть гладким (т. е. показывает больше случайности). В частности, листовые узлы могут быть реализованы с традиционными структурами данных, такими как B-деревья (в отличие, например, от нейронных сетей), в случае, если модели машинного обучения не могут обобщать данные или показывают худшую производительность. Авторы назвали эту комбинацию различных традиционных и машинных моделей гибридными индексами.

Будущее

  • Объем работы был на поиске (чтении) индекса, а не на вставке. Авторы действительно дали много предложений о том, как можно решить вставки, и положительно относятся к этой задаче. Следующими должны быть дальнейшие исследования вставок для изученных индексов.
  • Захватывающий потенциал для изученных индексов - это изучение многомерных структур индексов. То есть это открывает возможность эффективного поиска и ранжирования структур данных, содержащих множество точек данных.
  • Изученные алгоритмы: авторы намекают, что основная идея изучения индексов вполне может быть распространена на более общие алгоритмы, такие как объединение или сортировка данных.
  • Улучшения с графическими процессорами / TPU: авторы попали в точку, указав, что свойства ветвления параллельных изученных индексов могут быть реализованы и, таким образом, извлекать выгоду из экспоненциального выигрыша, ожидаемого для графических процессоров и TPU (в отличие от Мура. закон для процессоров, который по сути мертв) .
  • Многие положительные ответы и улучшения могут означать, что разработку баз данных (и многие другие задачи программирования) может взять на себя ИИ. Сравните с недавней работой по превращению макетов дизайна в настоящий html-код с помощью нейронных сетей.
  • Я с нетерпением жду появления первых реализаций реальных баз данных с открытым исходным кодом, использующих изученные индексы.

Добро

  • Несмотря на множество новаторских идей, газету очень легко читать.
  • Авторы обсудили несколько практических деталей, включая рассмотрение того, как разбиение на страницы диска может повлиять на производительность изученных индексов базы данных.
  • Авторы оставили много вдохновляющих открытых вопросов и даже предложили гипотетические решения.

Чтобы улучшить

  • Авторы не предоставили прямых ссылок на используемые наборы данных или код для своих реализаций машинного обучения. Воспроизводимость бесполезна.

Ссылки и справочные материалы

В 🍃tagtog.net мы стремимся сделать текстовую аналитику простой в использовании для всех.

👏👏👏 если вам понравился пост и вы хотите поделиться им с другими!