Хешування є основною операцією в більшості онлайнових баз даних, таких як каталог бібліотеки чи веб-сайт електронної комерції. Хеш-функція генерує коди, які замінюють вхідні дані. Оскільки ці коди коротші за фактичні дані та зазвичай мають фіксовану довжину, це полегшує пошук і отримання вихідної інформації.
Однак, оскільки традиційні хеш-функції генерують коди випадковим чином, іноді дві частини даних можна хешувати з однаковим значенням. Це спричиняє колізії — під час пошуку одного елемента користувач вказує на багато фрагментів даних з однаковим хеш-значенням. Щоб знайти потрібний, потрібно набагато більше часу, що призводить до сповільнення пошуку та зниження продуктивності.
Певні типи хеш-функцій, відомі як ідеальні хеш-функції, призначені для сортування даних у спосіб, який запобігає зіткненням. Але вони мають бути створені спеціально для кожного набору даних і потребують більше часу для обчислення, ніж традиційні хеш-функції.
Оскільки хешування використовується в багатьох програмах, від індексування бази даних до стиснення даних і криптографії, швидкі та ефективні хеш-функції є критично важливими. Отже, дослідники з Массачусетського технологічного інституту та інших країн вирішили з’ясувати, чи можна використовувати машинне навчання для створення кращих хеш-функцій.
Вони виявили, що в певних ситуаціях використання вивчених моделей замість традиційних хеш-функцій може призвести до удвічі меншої кількості колізій. Навчені моделі – це моделі, створені за допомогою алгоритму машинного навчання на наборі даних. Їхні експерименти також показали, що вивчені моделі часто були більш ефективними з точки зору обчислень, ніж ідеальні хеш-функції.
«У цій роботі ми виявили, що в деяких ситуаціях ми можемо знайти кращий компроміс між обчисленням хеш-функції та колізіями, з якими ми зіткнемося. Ми можемо трохи збільшити час обчислення для хеш-функції, але на водночас ми можемо дуже суттєво зменшити кількість зіткнень у певних ситуаціях», — каже Ібрагім Сабек, постдок у Групі систем даних MIT Лабораторії комп’ютерних наук і штучного інтелекту (CSAIL).
Їх дослідження, яке буде представлено на Міжнародній конференції з дуже великих баз даних, демонструє, як хеш-функція може бути розроблена для значного прискорення пошуку у величезній базі даних. Наприклад, їхня техніка може прискорити обчислювальні системи, які вчені використовують для зберігання та аналізу ДНК, амінокислотних послідовностей або іншої біологічної інформації.
Сабек є співавтором статті разом з аспірантом з електротехніки та інформатики (EECS) Капілом Вайдою. До них приєдналися співавтори Домінік Горн, аспірант Мюнхенського технічного університету; Андреас Кіпф, постдоктор Массачусетського технологічного інституту; Майкл Мітценмахер, професор інформатики Гарвардської школи інженерії та прикладних наук імені Джона А. Полсона; і старший автор Тім Краска, доцент EECS в MIT і співдиректор Data Systems and AI Lab.