Haszowanie to podstawowa operacja w większości internetowych baz danych, takich jak katalog biblioteczny lub witryna e-commerce. Funkcja skrótu generuje kody, które bezpośrednio określają lokalizację, w której dane będą przechowywane. Tak więc, używając tych kodów, łatwiej jest znaleźć i pobrać dane.

Ponieważ jednak tradycyjne funkcje skrótu generują kody w sposób losowy, czasami dwie części danych można zahaszować tą samą wartością. Powoduje to kolizje — wyszukiwanie jednego elementu wskazuje użytkownikowi wiele fragmentów danych o tej samej wartości skrótu. Znalezienie właściwego zajmuje znacznie więcej czasu, co skutkuje wolniejszym wyszukiwaniem i mniejszą wydajnością.

Niektóre typy funkcji skrótu, znane jako doskonałe funkcje skrótu, mają na celu umieszczanie danych w sposób zapobiegający kolizjom. Ich konstruowanie dla każdego zestawu danych jest jednak czasochłonne, a obliczenia zajmują więcej czasu niż tradycyjne funkcje skrótu.

Ponieważ haszowanie jest używane w tak wielu aplikacjach, od indeksowania baz danych, przez kompresję danych, po kryptografię, szybkie i wydajne funkcje haszujące mają kluczowe znaczenie. Tak więc naukowcy z MIT i innych krajów postanowili sprawdzić, czy mogliby wykorzystać uczenie maszynowe do zbudowania lepszych funkcji mieszających.

Odkryli, że w pewnych sytuacjach użycie wyuczonych modeli zamiast tradycyjnych funkcji skrótu może skutkować o połowę mniejszą liczbą kolizji. Te wyuczone modele są tworzone przez uruchomienie algorytmu uczenia maszynowego na zbiorze danych w celu przechwycenia określonych cech. Eksperymenty zespołu wykazały również, że wyuczone modele były często bardziej wydajne obliczeniowo niż doskonałe funkcje mieszające.

„W tej pracy odkryliśmy, że w niektórych sytuacjach możemy znaleźć lepszy kompromis między obliczeniem funkcji skrótu a kolizjami, z którymi przyjdzie nam się zmierzyć. W takich sytuacjach czas obliczeń dla funkcji skrótu można nieco wydłużyć, ale jednocześnie znacznie zmniejszyć liczbę kolizji” – mówi Ibrahim Sabek, postdoc w MIT Data Systems Group of the Computer Science and Artificial Intelligence Laboratorium (CSAIL).

Ich badania, które zostaną zaprezentowane na Międzynarodowej Konferencji nt. Bardzo Dużych Baz Danych w 2023 r., pokazują, w jaki sposób można zaprojektować funkcję skrótu, aby znacznie przyspieszyć przeszukiwanie ogromnej bazy danych. Na przykład ich technika może przyspieszyć systemy obliczeniowe, których naukowcy używają do przechowywania i analizowania DNA, sekwencji aminokwasowych lub innych informacji biologicznych.

Sabek jest współprowadzącym autorem artykułu wraz ze studentem Wydziału Elektrotechniki i Informatyki (EECS) Kapilem Vaidyą. Dołączają do nich współautorzy Dominick Horn, absolwent Politechniki w Monachium; Andreas Kipf, postdoc z MIT; Michael Mitzenmacher, profesor informatyki w Szkole Inżynierii i Nauk Stosowanych im. Johna A. Paulsona na Harvardzie; oraz starszy autor Tim Kraska, profesor nadzwyczajny EECS na MIT i współdyrektor Data, Systems, and AI Lab.

Wyszyfrowanie tego

Biorąc pod uwagę dane wejściowe lub klucz, tradycyjna funkcja skrótu generuje losową liczbę lub kod, który odpowiada szczelinie, w której ten klucz będzie przechowywany. Aby użyć prostego przykładu, jeśli w 10 gniazdach należy umieścić 10 kluczy, funkcja wygeneruje losową liczbę całkowitą z przedziału od 1 do 10 dla każdego wejścia. Jest wysoce prawdopodobne, że dwa klucze trafią do tego samego gniazda, powodując kolizje.

Doskonałe funkcje skrótu zapewniają bezkolizyjną alternatywę. Badacze przekazują tej funkcji dodatkową wiedzę, np. o liczbie slotów, w których mają zostać umieszczone dane. Następnie może wykonać dodatkowe obliczenia, aby dowiedzieć się, gdzie umieścić każdy klucz, aby uniknąć kolizji. Jednak te dodatkowe obliczenia sprawiają, że tworzenie funkcji jest trudniejsze i mniej wydajne.

„Zastanawialiśmy się, czy jeśli wiemy więcej o danych – że będą pochodzić z określonej dystrybucji – czy możemy użyć wyuczonych modeli do zbudowania funkcji skrótu, która może faktycznie zmniejszyć liczbę kolizji?” – mówi Vaidya.

Dystrybucja danych przedstawia wszystkie możliwe wartości w zbiorze danych oraz częstotliwość występowania poszczególnych wartości. Rozkładu można użyć do obliczenia prawdopodobieństwa, że ​​dana wartość znajduje się w próbce danych.

Naukowcy pobrali małą próbkę ze zbioru danych i wykorzystali uczenie maszynowe do przybliżenia kształtu rozkładu danych lub sposobu rozłożenia danych. Wyuczony model wykorzystuje następnie przybliżenie do przewidywania lokalizacji klucza w zbiorze danych.

Odkryli, że wyuczone modele były łatwiejsze do zbudowania i szybsze w działaniu niż doskonałe funkcje skrótu oraz że prowadziły do ​​mniejszej liczby kolizji niż tradycyjne funkcje skrótu, jeśli dane są dystrybuowane w przewidywalny sposób. Ale jeśli dane nie są przewidywalnie rozmieszczone, ponieważ luki między punktami danych są zbyt duże, użycie wyuczonych modeli może spowodować więcej kolizji.

„Możemy mieć ogromną liczbę danych wejściowych, a luki między kolejnymi danymi wejściowymi są bardzo różne, więc nauczenie się modelu do uchwycenia rozkładu danych wejściowych jest dość trudne”, wyjaśnia Sabek.

Mniej kolizji, szybsze rezultaty

Kiedy dane były dystrybuowane w sposób przewidywalny, wyuczone modele mogły zmniejszyć odsetek kolidujących ze sobą kluczy w zbiorze danych z 30 do 15 procent w porównaniu z tradycyjnymi funkcjami mieszającymi. Byli również w stanie osiągnąć lepszą przepustowość niż doskonałe funkcje skrótu. W najlepszych przypadkach wyuczone modele skracały czas działania o prawie 30 procent.

Badając wykorzystanie wyuczonych modeli do haszowania, naukowcy odkryli również, że na przepustowość największy wpływ miała liczba podmodeli. Każdy wyuczony model składa się z mniejszych modeli liniowych, które przybliżają rozkład danych dla różnych części danych. Przy większej liczbie podmodeli wyuczony model daje dokładniejsze przybliżenie, ale zajmuje to więcej czasu.

„Przy pewnym progu podmodeli otrzymujesz wystarczającą ilość informacji, aby zbudować przybliżenie potrzebne do funkcji skrótu. Ale potem nie doprowadzi to do większej poprawy redukcji kolizji” – mówi Sabek.

Opierając się na tej analizie, naukowcy chcą wykorzystać wyuczone modele do projektowania funkcji skrótu dla innych typów danych. Planują również zbadać wyuczone haszowanie dla baz danych, w których można wstawiać lub usuwać dane. Kiedy dane są aktualizowane w ten sposób, model musi się odpowiednio zmienić, ale zmiana modelu przy zachowaniu dokładności jest trudnym problemem.

„Chcemy zachęcić społeczność do korzystania z uczenia maszynowego w bardziej podstawowych strukturach danych i algorytmach. Każdy rodzaj podstawowej struktury danych daje nam możliwość wykorzystania uczenia maszynowego do przechwytywania właściwości danych i uzyskania lepszej wydajności. Jest jeszcze wiele do odkrycia” – mówi Sabek.

„Funkcje mieszania i indeksowania są podstawą wielu funkcjonalności baz danych. Biorąc pod uwagę różnorodność użytkowników i przypadków użycia, nie ma jednego uniwersalnego haszowania, a wyuczone modele pomagają dostosować bazę danych do konkretnego użytkownika. Ten artykuł jest świetnie wyważoną analizą wykonalności tych nowych technik i dobrze mówi o zaletach i wadach, a także pomaga nam zrozumieć, kiedy można oczekiwać, że takie metody będą działać dobrze”, mówi Murali Narayanaswamy, główny naukowiec zajmujący się uczeniem maszynowym w Amazon, który nie był zaangażowany w tę pracę. „Eksploracja tego rodzaju ulepszeń jest ekscytującym obszarem badań zarówno w środowisku akademickim, jak i przemysłowym, a rodzaj rygoru pokazany w tej pracy ma kluczowe znaczenie, aby te metody miały duży wpływ”.

Prace te były częściowo wspierane przez Google, Intel, Microsoft, amerykańską National Science Foundation, US Air Force Research Laboratory oraz US Air Force Artificial Intelligence Accelerator.