Many problems in computing boil down to a deceptively simple question: given one thing, how do you find the thing most similar to it? Imagine, for example, that you want to find the person who is physically closest to you. The answer seems obvious when there are only a few people around. But what happens when we have to search through increasingly complex spaces?
When you're standing in a straight line and want to find the person closest to you, the job is simple: you look left and then right, comparing your distance to the people around you. If you're in a room, however, you need to find the closest person in two-dimensional space. Again, it's not much of a problem since you can turn around and check the distances in different directions.
What if people could float in 3D space? In this case, things become complicated because you have to search in height, depth, and width. By adding a temporal dimension, things start to get frustrating. As the number of dimensions keeps growing, the task quickly becomes impractical.
Here's the shocking truth: much real-world data is represented in far higher dimensions, sometimes 100 dimensions or even more! Hence, the apt adjective “cursed” is used to describe this data.
An innovative solution for quick search among similar data in large datasets was proposed by Dr. Vahab Mirrokni, an Iranian researcher and graduate of Sharif University of Technology and the Massachusetts Institute of Technology (MIT). His "Locality-Sensitive Hashing" (LSH) algorithm is now considered one of the popular hashing techniques in big data processing and artificial intelligence. Mirrokni, who is now a senior researcher at Google, was awarded the Mustafa(pbuh) Prize in 2025 in recognition of this achievement.
For a better grasp of this technique, we must first address one of the fundamental challenges of the age of data, a challenge which has made finding a piece of valuable information among a vast amount of data like searching for a needle in an ever-growing haystack.
Cursed Data
With the advancement of technology and the emergence of diverse forms of data into the world of computing and processing, we have encountered cursed data with remarkably high dimensionality. A color image of 1000 x 1000 pixels (where each pixel is one dimension) is considered a three-million-dimensional data on a computer! This is because each pixel is represented by the triple combination of red, green, and blue values, which is one of the standard methods of storing color images. Even after applying dimensionality reduction methods, we still deal with hundreds or thousands of dimensions in image processing.
When processing text files, we enter the realm of natural language processing, where words are converted into numerical vectors using certain methods. Each word is assigned an n-dimensional numerical vector (100-300 dimensions) so that similar words have similar vectors. Then, to process a text, key words are identified, extracted, and examined. With these methods, a text, which consists of several words, becomes highly dimensional. Thus, a paragraph can have tens of thousands of dimensions!
Another class of data that has received a lot of attention in the last decade is genetic data. Each cell of every living being contains a molecule called DNA, which is made up of four types of simpler molecules called bases. Given that the length of DNA in humans reaches about 3 billion base pairs, when represented and analyzed computationally, this enormous sequence can give rise to extremely high-dimensional data. Parts of DNA, called genes, are largely conserved over generations, determining the function of an organism's body. The preservation of each human's DNA information can be done in two ways: either the entire molecular sequence is preserved, or only parts of the gene, of which there are approximately 25,000 parts with different lengths, are preserved. In either case, we face a vast amount of information.
Close, Yet So Far Away: The Challenge of Searching in High-Dimensional Data
In such a high-dimensional space, the “curse of dimensionality” occurs. The data is uncommonly sparse, so that almost everything is equally spaced apart. In other words, the concept of “similarity” disappears as all data looks almost identical, and searching for the nearest neighbor becomes an impossible mission and computation becomes impractical.
Searching for the closest neighbor is one of the central issues in data science, machine learning, and information retrieval. The main objective of this process is to find the nearest point (or points) to a given point, which can be determined based on a similarity criterion. There are various metrics for measuring data distance, two of the simplest of which are Euclidean distance and Manhattan distance. In the former, the length of the line segment that directly connects two points in space is measured, while in the latter, the distance is calculated as if moving from one point to another step by step, that is, the sum of the differences in the data across different dimensions.
On the surface, it seems a straightforward job to find the image that most closely resembles our target image from an image database, or to find the most genetically similar organisms to create an evolutionary family tree, but these tasks present highly complex challenges. Sometimes there may be requirements for detecting textual similarity and plagiarism, or analyzing the emotions expressed in the texts. The advertising market and recommendation systems are not exempt from these challenges if they want to recommend a product based on individuals’ tastes and those of similar users. In fact, in all these cases, we are only looking for the most similar data to a specific data point. If the data were low-dimensional, the answer would be ready within a fairly reasonable time using traditional methods and fast algorithms. However, what makes it difficult to meet the demands is their high dimensionality.
Your Comment