Os pesquisadores usaram o aprendizado de máquina para criar funções de hash mais rápidas e eficientes, que são um componente-chave dos bancos de dados.
Uma tela pop-up estilizada tem um ícone de "hash". Muitas outras versões translúcidas da tela se acumulam abaixo, sobre um fundo decorativo.
Pesquisadores do MIT e de outros lugares decidiram usar o aprendizado de máquina para criar melhores funções de hash.
Hashing é uma operação central na maioria dos bancos de dados online, como um catálogo de biblioteca ou um site de comércio eletrônico. Uma função hash gera códigos que determinam diretamente o local onde os dados seriam armazenados. Então, usando esses códigos, fica mais fácil encontrar e recuperar os dados.
No entanto, como as funções hash tradicionais geram códigos aleatoriamente, às vezes duas partes dos dados podem sofrer hash com o mesmo valor. Isso causa colisões — ao pesquisar um item, o usuário aponta para muitos dados com o mesmo valor de hash. Leva muito mais tempo para encontrar o caminho certo, resultando em pesquisas mais lentas e desempenho reduzido.
Certos tipos de funções hash, conhecidas como funções hash perfeitas, são projetadas para colocar os dados de forma a evitar colisões. Mas eles são demorados para serem construídos para cada conjunto de dados e levam mais tempo para serem computados do que as funções de hash tradicionais.
Como o hash é usado em muitos aplicativos, desde indexação de banco de dados até compactação de dados e criptografia, funções de hash rápidas e eficientes são essenciais. Assim, pesquisadores do MIT e de outros lugares decidiram usar o aprendizado de máquina para criar melhores funções de hash.
Eles descobriram que, em certas situações, usar modelos aprendidos em vez de funções de hash tradicionais pode resultar em metade das colisões. Esses modelos aprendidos são criados executando um algoritmo de aprendizado de máquina em um conjunto de dados para capturar características específicas. Os experimentos da equipe também mostraram que os modelos aprendidos eram frequentemente mais eficientes computacionalmente do que as funções hash perfeitas.
“O que descobrimos neste trabalho é que em algumas situações podemos chegar a um melhor tradeoff entre o cálculo da função hash e as colisões que enfrentaremos. Nessas situações, o tempo de computação da função hash pode ser aumentado um pouco, mas ao mesmo tempo suas colisões podem ser reduzidas de forma muito significativa”, diz Ibrahim Sabek, pós-doutorando no MIT Data Systems Group of the Computer Science and Artificial Intelligence Laboratório (CSAIL).
Sua pesquisa, que será apresentada na Conferência Internacional de Bancos de Dados Muito Grandes de 2023, demonstra como uma função de hash pode ser projetada para acelerar significativamente as pesquisas em um banco de dados enorme. Por exemplo, sua técnica pode acelerar sistemas computacionais que os cientistas usam para armazenar e analisar DNA, sequências de aminoácidos ou outras informações biológicas.
Sabek é o co-autor principal do artigo com Kapil Vaidya, aluno de pós-graduação do Departamento de Engenharia Elétrica e Ciência da Computação (EECS). Eles são acompanhados por co-autores Dominick Horn, um estudante de pós-graduação na Universidade Técnica de Munique; Andreas Kipf, pós-doutorado do MIT; Michael Mitzenmacher, professor de ciência da computação na Harvard John A. Paulson School of Engineering and Applied Sciences; e o autor sênior Tim Kraska, professor associado da EECS no MIT e codiretor do Data, Systems, and AI Lab.
Fazendo hash
Dada uma entrada de dados, ou chave, uma função hash tradicional gera um número aleatório, ou código, que corresponde ao slot onde essa chave será armazenada. Para usar um exemplo simples, se houver 10 chaves a serem colocadas em 10 slots, a função gerará um número inteiro entre 1 e 10 para cada entrada. É altamente provável que duas chaves acabem no mesmo slot, causando colisões.
Funções de hash perfeitas fornecem uma alternativa livre de colisão. Os pesquisadores fornecem à função algum conhecimento extra, como o número de slots nos quais os dados devem ser colocados. Em seguida, ele pode realizar cálculos adicionais para descobrir onde colocar cada chave para evitar colisões. No entanto, esses cálculos adicionados tornam a função mais difícil de criar e menos eficiente.
“Estávamos nos perguntando, se soubermos mais sobre os dados – que virão de uma distribuição específica – podemos usar modelos aprendidos para criar uma função de hash que pode realmente reduzir as colisões?” diz Vaidya.
Uma distribuição de dados mostra todos os valores possíveis em um conjunto de dados e com que frequência cada valor ocorre. A distribuição pode ser usada para calcular a probabilidade de um determinado valor estar em uma amostra de dados.
Os pesquisadores pegaram uma pequena amostra de um conjunto de dados e usaram o aprendizado de máquina para aproximar a forma da distribuição dos dados ou como os dados são espalhados. O modelo aprendido então usa a aproximação para prever a localização de uma chave no conjunto de dados.
Eles descobriram que modelos aprendidos eram mais fáceis de construir e mais rápidos de executar do que funções hash perfeitas e que levavam a menos do que as funções de hash tradicionais se os dados forem distribuídos de maneira previsível. Mas se os dados não forem distribuídos de forma previsível porque as lacunas entre os pontos de dados variam muito, o uso de modelos aprendidos pode causar mais colisões.
“Podemos ter um grande número de entradas de dados, e as lacunas entre entradas consecutivas são muito diferentes, portanto, aprender um modelo para capturar a distribuição de dados dessas entradas é bastante difícil”, explica Sabek.
Menos colisões, resultados mais rápidos
Quando os dados eram distribuídos de forma previsível, os modelos aprendidos podiam reduzir a proporção de chaves em colisão em um conjunto de dados de 30% para 15%, em comparação com as funções de hash tradicionais. Eles também foram capazes de obter uma taxa de transferência melhor do que as funções hash perfeitas. Nos melhores casos, os modelos aprendidos reduziram o tempo de execução em quase 30%.
À medida que exploravam o uso de modelos aprendidos para hash, os pesquisadores também descobriram que a taxa de transferência era mais afetada pelo número de submodelos. Cada modelo aprendido é composto por modelos lineares menores que aproximam a distribuição de dados para diferentes partes dos dados. Com mais submodelos, o modelo aprendido produz uma aproximação mais precisa, mas leva mais tempo.
“Em um determinado limite de submodelos, você obtém informações suficientes para construir a aproximação necessária para a função hash. Mas depois disso, não levará a mais melhorias na redução de colisões”, diz Sabek.
Com base nessa análise, os pesquisadores querem usar modelos aprendidos para projetar funções de hash para outros tipos de dados. Eles também planejam explorar o hashing aprendido para bancos de dados nos quais os dados podem ser inseridos ou excluídos. Quando os dados são atualizados dessa maneira, o modelo precisa mudar de acordo, mas alterar o modelo mantendo a precisão é um problema difícil.
“Queremos encorajar a comunidade a usar o aprendizado de máquina dentro de estruturas de dados e algoritmos mais fundamentais. Qualquer tipo de estrutura de dados central nos apresenta uma oportunidade de usar aprendizado de máquina para capturar propriedades de dados e obter melhor desempenho. Ainda há muito que podemos explorar”, diz Sabek.
“As funções de hashing e indexação são essenciais para muitas funcionalidades do banco de dados. Dada a variedade de usuários e casos de uso, não há um tamanho único para todos os hashing, e os modelos aprendidos ajudam a adaptar o banco de dados a um usuário específico. Este artigo é uma excelente análise equilibrada da viabilidade dessas novas técnicas e faz um bom trabalho ao falar rigorosamente sobre os prós e contras, e nos ajuda a entender quando esses métodos podem funcionar bem”, diz Murali Narayanaswamy, um dos principais cientistas de aprendizado de máquina da Amazon, que não estava envolvido com este trabalho. “Explorar esses tipos de aprimoramentos é uma área empolgante de pesquisa tanto na academia quanto na indústria, e o tipo de rigor demonstrado neste trabalho é fundamental para que esses métodos tenham grande impacto”.
Este trabalho foi financiado, em parte, pelo Google, Intel, Microsoft, Fundação Nacional de Ciências dos EUA, Laboratório de Pesquisa da Força Aérea dos EUA e Acelerador de Inteligência Artificial da Força Aérea dos EUA.
Fonte: https://news.mit.edu/
Nenhum comentário:
Postar um comentário