Muitos problemas na computação se resumem a uma questão aparentemente simples: dado um objeto, como encontrar o objeto mais similar a ele? Por exemplo, imagine que você deseja encontrar a pessoa fisicamente mais próxima de você. A resposta parece óbvia quando há poucas pessoas presentes. Mas o que acontece quando precisamos pesquisar em espaços cada vez mais complexos?
Quando você está em uma linha e quer encontrar a pessoa mais próxima, a tarefa é simples: você olha para a esquerda e depois para a direita, comparando sua distância com as pessoas ao seu redor. No entanto, se você estiver em uma sala, precisa encontrar a pessoa mais próxima no espaço bidimensional. Novamente, não é um grande problema, pois você pode se virar e verificar as distâncias em diferentes direções.
E se as pessoas pudessem flutuar no espaço tridimensional? Nesse caso, as coisas se tornam complicadas, pois seria necessário procurar em altura, profundidade e largura. Ao adicionar uma dimensão temporal, as coisas começam a se tornar frustrantes. À medida que o número de dimensões continua a crescer, a tarefa rapidamente se torna impraticável.
Aqui está a chocante verdade: muitos dados do mundo real são representados em dimensões muito mais altas, às vezes 100 dimensões ou até mais! Desta forma, o adjetivo apropriado "amaldiçoado" é usado para descrever esses dados.
Uma solução inovadora para busca rápida entre dados semelhantes em grandes conjuntos de dados foi proposta pelo Dr. Vahab Mirrokni, um pesquisador iraniano e graduado da Universidade Sharif de Tecnologia e do Instituto de Tecnologia de Massachusetts (MIT). Seu algoritmo "Hashing Sensível à Localidade" (LSH) é agora considerado uma das técnicas de hashing mais populares no processamento de big data e inteligência artificial. Mirrokni, que atualmente é pesquisador sênior no Google, recebeu o Prêmio Mustafa (pbuh) em 2025 em reconhecimento a essa conquista.
Para uma melhor compreensão desta técnica, devemos primeiro abordar um dos desafios fundamentais da era de dados, um desafio que torna a busca por uma informação valiosa em uma vasta quantidade de dados semelhante a procurar uma agulha em um feno em constante crescimento.
Dados Amaldiçoados
Com o avanço da tecnologia e o surgimento de diversas formas de dados no mundo da computação e processamento, encontramos dados amaldiçoados com dimensões notavelmente altas. Uma imagem colorida de 1000 x 1000 pixels (onde cada pixel é uma dimensão) é considerada um conjunto de dados de três milhões de dimensões em um computador! Isso ocorre porque cada pixel é representado pela combinação tripla de valores de vermelho, verde e azul, que é um dos métodos padrão de armazenamento de imagens coloridas. Mesmo após aplicar métodos de redução de dimensionalidade, ainda lidamos com centenas ou milhares de dimensões no processamento de imagens.
Ao processar arquivos de texto, entramos no campo do processamento de linguagem natural, onde as palavras são convertidas em vetores numéricos usando certos métodos. Cada palavra recebe um vetor numérico de n dimensões (100-300 dimensões) para que palavras semelhantes tenham vetores semelhantes. Em seguida, para processar um texto, as palavras-chave são identificadas, extraídas e examinadas. Com esses métodos, um texto, que consiste em várias palavras, se torna altamente dimensional. Assim, um parágrafo pode ter dezenas de milhares de dimensões!
Outra classe de dados que tem recebido muita atenção na última década é os dados genéticos. Cada célula de todo ser vivo contém uma molécula chamada DNA, que é composta por quatro tipos de moléculas mais simples chamadas bases. Dado que o comprimento do DNA em humanos atinge cerca de 3 bilhões de pares de bases, quando representado e analisado computacionalmente, essa enorme sequência pode dar origem a dados extremamente de alta dimensão. Partes do DNA, chamadas genes, são em grande parte conservadas ao longo das gerações, determinando a função do corpo de um organismo. A preservação da informação do DNA de cada ser humano pode ser feita de duas maneiras: ou a sequência molecular completa é preservada, ou apenas partes do gene, dos quais existem aproximadamente 25.000 partes com diferentes comprimentos, são preservadas. Em qualquer caso, enfrentamos uma vasta quantidade de informações.
Próximo, Mas Tão Longe: O Desafio da Busca em Dados de Alta Dimensão
Nesse espaço de alta dimensão, ocorre a "maldade da dimensionalidade". Os dados são incomumente esparsos, de modo que quase tudo está igualmente espaçado. Em outras palavras, o conceito de "similaridade" desaparece, pois todos os dados parecem quase idênticos, e procurar o vizinho mais próximo se torna uma missão impossível e o cálculo se torna impraticável.
Procurar o vizinho mais próximo é um dos principais problemas em ciência de dados, aprendizado de máquina e recuperação de informações. O principal objetivo desse processo é encontrar o ponto (ou pontos) mais próximo a um determinado ponto, que pode ser determinado com base em um critério de similaridade. Existem várias métricas para medir a distância entre dados, duas das mais simples são a distância euclidiana e a distância de Manhattan. Na primeira, a distância entre dois pontos no espaço é medida pelo comprimento do segmento de linha que os conecta diretamente, enquanto na segunda, a distância é calculada como se estivesse se movendo de um ponto para outro passo a passo, ou seja, a soma das diferenças nos dados ao longo de diferentes dimensões.
Na superfície, parece uma tarefa simples encontrar a imagem que mais se assemelha à imagem-alvo em um banco de dados de imagens, ou encontrar os organismos mais geneticamente semelhantes para criar uma árvore evolutiva. No entanto, essas tarefas apresentam desafios altamente complexos. Em alguns casos, pode haver a necessidade de detectar similaridade textual e plágio, ou de analisar as emoções expressas nos textos. O mercado de publicidade e os sistemas de recomendação não estão isentos desses desafios, se o objetivo é recomendar um produto com base nos gostos de um indivíduo e de usuários semelhantes. Na verdade, em todos esses casos, estamos apenas procurando os dados mais semelhantes a um determinado ponto de dados. Se os dados fossem de baixa dimensão, a resposta seria obtida em um tempo razoável, utilizando métodos tradicionais e algoritmos rápidos. No entanto, o que torna a tarefa difícil é a sua alta dimensão.