Nuovo metodo accelera il recupero dei dati in enormi database

New method speeds up data retrieval in massive databases.

I ricercatori hanno utilizzato il machine learning per costruire funzioni hash più veloci ed efficienti, che sono un componente chiave dei database.

Hashing è un’operazione fondamentale nella maggior parte dei database online, come un catalogo di una biblioteca o un sito di e-commerce. Una funzione di hash genera dei codici che determinano direttamente la posizione in cui i dati verranno memorizzati. Quindi, utilizzando questi codici, è più facile trovare e recuperare i dati.

• Imparare a far crescere modelli di machine learning
• Un metodo per progettare reti neurali ottimalmente adatte per determinati compiti
• I droni navigano in ambienti invisibili con reti neurali liquide.

Tuttavia, poiché le tradizionali funzioni di hash generano i codici in modo casuale, a volte due pezzi di dati possono essere hashati con lo stesso valore. Ciò provoca collisioni, ossia quando la ricerca di un elemento porta l’utente a molti pezzi di dati con lo stesso valore di hash. Ci vuole molto più tempo per trovare quello giusto, con conseguente rallentamento delle ricerche e riduzione delle prestazioni.

Certain tipi di funzioni di hash, note come funzioni di hash perfette, sono progettate per posizionare i dati in modo da evitare collisioni. Ma richiedono molto tempo per essere costruite per ogni dataset e impiegano più tempo per essere calcolate rispetto alle funzioni di hash tradizionali.

Dato che l’hashing è utilizzato in così tante applicazioni, dall’indicizzazione dei database alla compressione dei dati alla crittografia, le funzioni di hash veloci ed efficienti sono cruciali. Quindi, i ricercatori del MIT e di altri luoghi si sono messi alla ricerca di un modo per utilizzare il machine learning per costruire funzioni di hash migliori.

Hanno scoperto che, in determinate situazioni, l’utilizzo di modelli appresi invece delle tradizionali funzioni di hash poteva portare a metà collisioni. Questi modelli appresi vengono creati eseguendo un algoritmo di machine learning su un dataset per catturare caratteristiche specifiche. Gli esperimenti del team hanno anche dimostrato che i modelli appresi erano spesso più efficienti dal punto di vista computazionale delle funzioni di hash perfette.

“Ciò che abbiamo scoperto in questo lavoro è che in alcune situazioni possiamo trovare un miglior compromesso tra il calcolo della funzione di hash e le collisioni che incontreremo. In queste situazioni, il tempo di calcolo della funzione di hash può aumentare un po’, ma allo stesso tempo le collisioni possono essere ridotte in modo significativo”, afferma Ibrahim Sabek, un postdoc del MIT Data Systems Group del Computer Science and Artificial Intelligence Laboratory (CSAIL).

La loro ricerca, che verrà presentata alla Conferenza Internazionale sulle Basi di Dati Molto Grandi del 2023, dimostra come una funzione di hash possa essere progettata per accelerare significativamente le ricerche in un enorme database. Ad esempio, la loro tecnica potrebbe accelerare i sistemi di calcolo che gli scienziati utilizzano per memorizzare e analizzare il DNA, le sequenze di aminoacidi o altre informazioni biologiche.

Sabek è il co-autore principale del paper insieme a Kapil Vaidya, uno studente di dottorato del Dipartimento di Ingegneria Elettrica e Informatica (EECS). Si uniscono a loro Dominik Horn, uno studente di dottorato presso la Technical University di Monaco di Baviera; Andreas Kipf, un postdoc del MIT; Michael Mitzenmacher, professore di informatica presso la Harvard John A. Paulson School of Engineering and Applied Sciences; e l’autore senior Tim Kraska, professore associato di EECS al MIT e co-direttore del Data, Systems, and AI Lab.

Discutendo di hashing

Data in input, o chiave, una funzione di hash tradizionale genera un numero casuale, o codice, che corrisponde allo slot in cui quella chiave verrà memorizzata. Per fare un esempio semplice, se ci sono 10 chiavi da inserire in 10 slot, la funzione genererebbe un intero tra 1 e 10 per ogni input. È altamente probabile che due chiavi finiscano nello stesso slot, causando collisioni.

Le funzioni di hash perfette forniscono un’alternativa priva di collisioni. I ricercatori forniscono alla funzione alcune informazioni aggiuntive, come il numero di slot in cui i dati devono essere inseriti. Quindi può eseguire ulteriori calcoli per capire dove inserire ogni chiave per evitare collisioni. Tuttavia, questi calcoli aggiuntivi rendono la funzione più difficile da creare e meno efficiente.

“Ci chiedevamo, se conosciamo meglio i dati – che provengono da una particolare distribuzione – possiamo utilizzare modelli appresi per costruire una funzione di hash che possa effettivamente ridurre le collisioni?” dice Vaidya.

Una distribuzione dei dati mostra tutti i possibili valori in un dataset e con quale frequenza ogni valore si presenta. La distribuzione può essere utilizzata per calcolare la probabilità che un determinato valore sia presente in un campione di dati.

I ricercatori hanno preso un piccolo campione da un dataset e utilizzato il machine learning per approssimare la forma della distribuzione dei dati, o come i dati sono distribuiti. Il modello appreso utilizza quindi l’approssimazione per prevedere la posizione di una chiave nel dataset.

Hanno scoperto che i modelli appresi erano più facili da costruire e più veloci da eseguire delle funzioni di hash perfette e che portavano a meno collisioni rispetto alle funzioni di hash tradizionali se i dati erano distribuiti in modo prevedibile. Ma se i dati non sono distribuiti in modo prevedibile perché i vuoti tra i punti dei dati variano troppo, l’utilizzo di modelli appresi potrebbe causare più collisioni.

“Potremmo avere un enorme numero di input di dati e i gap tra gli input consecutivi sono molto diversi, quindi apprendere un modello per catturare la distribuzione dei dati di questi input è piuttosto difficile”, spiega Sabek.

Meno collisioni, risultati più veloci

Quando i dati erano distribuiti in modo prevedibile, i modelli appresi potevano ridurre il rapporto di chiavi in collisione in un set di dati dal 30% al 15%, rispetto alle funzioni hash tradizionali. Sono stati in grado anche di raggiungere una migliore efficienza rispetto alle funzioni hash perfette. Nei casi migliori, i modelli appresi hanno ridotto il tempo di esecuzione di quasi il 30%.

Mentre esploravano l’uso di modelli appresi per l’hashing, i ricercatori hanno anche scoperto che l’efficienza era influenzata principalmente dal numero di sottomodelli. Ogni modello appreso è composto da modelli lineari più piccoli che approssimano la distribuzione dei dati per diverse parti dei dati. Con più sottomodelli, il modello appreso produce un’approssimazione più accurata, ma ci vuole più tempo.

“Ad una certa soglia di sottomodelli, si ottiene abbastanza informazioni per costruire l’approssimazione necessaria per la funzione hash. Ma dopo di che, non porterà a una maggiore riduzione di collisioni”, afferma Sabek.

Basandosi su questa analisi, i ricercatori vogliono utilizzare i modelli appresi per progettare funzioni hash per altri tipi di dati. Hanno anche in programma di esplorare l’hashing appreso per i database in cui i dati possono essere inseriti o eliminati. Quando i dati vengono aggiornati in questo modo, il modello deve cambiare di conseguenza, ma cambiare il modello mantenendo l’accuratezza è un problema difficile.

“Vogliamo incoraggiare la comunità ad utilizzare l’apprendimento automatico all’interno di strutture dati e algoritmi più fondamentali. Qualsiasi tipo di struttura dati principale ci presenta l’opportunità di utilizzare l’apprendimento automatico per catturare le proprietà dei dati e ottenere una migliore efficienza. C’è ancora molto da esplorare”, dice Sabek.

“Le funzioni di hash e di indicizzazione sono fondamentali per molte funzionalità dei database. Date le varie tipologie di utenti e casi d’uso, non esiste un’unica funzione di hash adatta a tutti e i modelli appresi aiutano ad adattare il database ad un utente specifico. Questo articolo rappresenta un’ottima analisi equilibrata della fattibilità di queste nuove tecniche e fa un buon lavoro nel parlare in modo rigoroso dei pro e dei contro, aiutandoci a comprendere quando tali metodi possono aspettarsi di funzionare bene”, afferma Murali Narayanaswamy, uno scienziato principale dell’apprendimento automatico presso Amazon, che non ha partecipato a questo lavoro. “Esplorare questo tipo di miglioramenti è un’area di ricerca entusiasmante sia in ambito accademico che industriale, e il tipo di rigore dimostrato in questo lavoro è fondamentale affinché questi metodi possano avere un grande impatto”.

Questo lavoro è stato supportato, in parte, da Google, Intel, Microsoft, la National Science Foundation degli Stati Uniti, la U.S. Air Force Research Laboratory e l’acceleratore di intelligenza artificiale della U.S. Air Force.