You’re seated in a vast control room, tasked with monitoring a secret underground laboratory—a place filled with screens displaying millions of data points: images, sounds, medical records, messages—all streaming before your eyes like a roaring river. Suddenly, an alarm sounds, and a red light begins flashing above your head, drawing your attention toward it. Somewhere in this chaos, corrupted data is hiding—but you have no name, no coordinates, not even a single descriptive clue to guide your search.
All you see is a vague message from the alert system: “We’ve seen this error before... It looks like that one... but it’s not exactly the same!”
And now, as a human search engine, you face the ultimate question: “How can you find something among billions of data points — when you can’t even define what it is?”
Welcome to the Observatory, where we go through the ground-breaking science of our time and dive into the fascinating world of discovery and innovation.
You’ve probably experienced similar search problems in daily life: a song whose melody you faintly remember, but you can’t recall the lyrics or the singer’s name; or finding a key in the lobby of a building full of apartments, without having any clue which door it belongs to. These examples reveal a reality that highlights the importance of the world of computers: we humans simply do not have the time or the capacity to solve these problems at scale, but computers see the world differently.
For them, every sound sample is just a numerical vector, every distance is a calculation, and every similarity is a mathematical problem. Within moments, a search engine begins compressing, comparing, transforming through multi-dimensional spaces, and applying smart shortcuts — those shortcuts we call “search and similarity algorithms.”
A realm where guessing disappears, because every similarity becomes computable, every piece of data finds its place, and even the most ambiguous descriptions turn — through mathematics — into prey waiting to be captured.
Today, we’re going to talk about a scientific innovation—an approach that Vahab Mirrokni has introduced precisely for tackling these large-scale search problems. To get a glimpse of what Mirrokni has worked on, we need to talk about nearest neighbor search algorithms. First, let’s understand what an algorithm actually is. Algorithms are sets of step-by-step instructions designed to solve problems or perform specific tasks.
The first nearest neighbor search algorithm was based on quantization. To better understand this algorithm, let’s use a simple example, imagine we have a massive database containing billions of images, each represented by a long vector. Now we input a new image and want to find the most similar one in the database.
Instead of comparing this new image to every single image individually, we use quantization.
That means: instead of fully encoding the entire long vector, we divide it into smaller parts.
For each small part, we create a codebook — which is basically a compact, limited sequence of codes corresponding to that segment of the image. When the computer sees these codes, it knows which part of the image we’re talking about.
The final code for the whole image vector then becomes just a combination of these short codes. The strengths of this method are its extremely high speed, significant savings in RAM usage, and scalability.
However, its weaknesses include approximate search, bias error in distance estimation, and sensitivity to initial settings and parameters. The bias error means that the algorithm may systematically misestimate the true distance between two data points. In other words, its estimates may consistently lean in one direction — either regularly underestimating the real distance or overestimating it. Sensitivity to initial settings and parameters means that the algorithm’s performance strongly depends on early choices; if those choices are wrong, the final results will be inaccurate.
The second algorithm is the graph-based nearest neighbor search. This is a widely used and practical method for finding the “most similar” item to a query within a large-scale database.
Its idea is that, instead of comparing items one by one, it first builds a connectivity map or a graph of the entire dataset. Each data item becomes a node or vertex, and nodes that are similar are connected by an edge, marking them as “neighbors.” When a new query comes in, the algorithm doesn’t search the whole dataset but rather navigates this graph to reach the nearest node to the query.
An important point is that this algorithm typically uses greedy search, meaning that at each step, it chooses the most promising option it sees — though there’s no guarantee it will reach the global optimum. This approach strikes the best balance between speed and accuracy, has industrial popularity, and is far beyond being a mere research concept — it’s something with real-world applications.
Yet, it has its downsides: graph construction is slow, requires continuous updating, consumes a large amount of memory, and due to the greedy nature of its search, it often gets stuck in local optima instead of finding the global one.
The next algorithm is the tree-based nearest neighbor search. Instead of linearly scanning all data, this algorithm first builds a hierarchical tree structure that divides the space into smaller regions. Each branch or node of this tree represents a portion of the space and contains all data points located within that region.
Searching with this method is much like asking for directions in a big city — rather than checking every building one by one, you first find the right district, then the correct street, and finally reach the target house. This tree structure enables the algorithm to quickly locate the correct “region.”
Let’s explore its structure more precisely. First, the tree must be constructed. To do this, the algorithm recursively divides the space — meaning it repeatedly splits the space into smaller parts, and then continues splitting those parts again until it reaches manageable regions. “Recursive” here means that the algorithm performs an operation over and over on its own output. After that, a precise traversal known as MT-DFS is carried out. In this stage, the tree is traversed, and the best option found so far is kept as the candidate.
Then the search goes deeper into the tree, and if it finds that the distance between a new branch and the query, which is our measure of similarity, is greater than that between the candidate branch and the query, it prunes that branch — meaning it completely ignores it.
Finally, it performs an approximate search on the tree. So what are the advantages of this method? high compatibility with high-dimensional spaces, very fast speed, relatively good performance, and acceptable accuracy.
Disadvantages: the method is inherently approximate, trading accuracy for speed, and it has a high overlap cost — meaning that a single data point may have to be examined simultaneously in multiple branches or regions, which is computationally expensive.
Now that we've become familiar with how computers perform nearest neighbor search in a vast collection of data, it’s time to move on to the heart of the topic — the work of Vahab Mirrokni and his colleagues, who introduced a fascinating improvement to Locality-Sensitive Hashing or LSH.
Let’s now move to the core idea — Locality-Sensitive Hashing based on p-stable distributions. To understand this technique better, let’s start with an example: Imagine you’ve entered a supermarket, looking for a specific product like milk of a particular brand. Of course, finding it doesn’t take long, but if you’re looking for *something similar* to that product, the situation becomes more complex — now factors such as fat percentage, production date, and many other parameters come into play.
Computers tackle this through nearest neighbor search — something we’ve just talked about, with several algorithms designed for that task. One of these algorithms is LSH, or *Locality-Sensitive Hashing.*
In simple terms, it works like putting all our items into categorized boxes. The idea is that if two data points or items, in our supermarket example are similar, they should most likely end up in the same box. That way, when searching for similar items, you only need to look inside the box of your original item — not through the entire supermarket.
This algorithm isn’t new; it has been widely used. However, applying it efficiently to real-valued data such as images, audio recordings, and documents remained a challenge. These types of data are often represented as points in high-dimensional spaces, where finding similar items quickly becomes computationally expensive.
The result of Mirrokni and his colleagues’ research was the development of the p-stable LSH technique, which made similarity search in high-dimensional Euclidean spaces significantly more efficient. Now, you know what time it is — time for another example!
A room filled with colored balls floating in space serves as a visual representation of our data points. The goal is to identify which balls are close to one another. To do this, a lamp is placed on the ceiling, casting a random line or vector through the space. The direction of this line is not chosen arbitrarily; instead, it is determined by a mathematical formula known as a p-stable distribution, which is the key part of the process.
Now, picture shining a light through the room so that the shadows of all the balls fall onto that line. In mathematical terms, this is called a projection. Next, we divide that line into equal segments — like marking a ruler.
The result?
If two balls in space are very close together, their shadows on the line will most likely fall within the same segment of this ruler-like grid. If they are far apart, their shadows will fall into distant segments.
The p-stable formula ensures that this “shadowing” process isn’t random — it preserves the real distances and similarities between objects.
This technique achieves exceptional speed. In experiments conducted by Mirrokni, it proved to be up to 40 times faster than classical methods. Furthermore, it’s much easier for programmers to implement, since it doesn’t require converting complex data formats.
It also works directly on real-world distances — such as direct or Euclidean distance — making it highly suitable for searching through images, videos, and text documents. Real world distances are those that we humans can intuitively perceive and measure, while the Euclidean distance simply represents the shortest possible distance between two points.
To truly understand the value of this approach, we need to go deeper into its inner layers.
Let’s start with a question: Why is the “stable distribution” chosen?
In our earlier example, we said this method works like casting the shadow of objects onto a random line — but not any line will be usable!
In a dark room, shadows of objects can be cast onto the wall using a flashlight. When the angle of the light beam is poor, the shadow of a large object may appear the same size as that of a small one.
This is exactly where Mirrokni's innovation appears: if the linear vector, in other words, the line onto which we cast shadows, is chosen from a specific distribution — the p-stable distribution — something almost magical happens:
- The distance between the shadows of two objects on the line holds a precise and direct relationship with their real distance in space. In other words, the true spatial distance is preserved.
- That means if the shadows are close to each other, then the actual objects themselves are also close in the real world.
Another major feature of Mirrokni’s research is the random shift mechanism, which enhances the original formula using a combination of mathematical tools: first, the inner product — representing the projection of vectors onto the random line — and second, the division of that line into segments of length r .Perhaps the most important part of this research is the step where a random value is added to the shadow positions.
In practical terms: suppose two points are very close together, but just by bad luck, they fall exactly on the border between two grid cells, one lands in cell 3 and the other in cell 4. Even though they’re close, they’d end up in separate boxes.
Adding that random number shifts the grid slightly to the right or left, ensuring that the probability of nearby points getting separated is greatly reduced. This tweak significantly improves accuracy.
To further improve accuracy, the method adds another step: a two‑stage structure designed to address the potential shadowing error.
- Stage 1 — Parameter k: Instead of projecting once, we project *n* times and combine all the results. This ensures that only truly similar items end up grouped together in the same box.
- Stage 2 — Parameter L: This parameter addresses the problem of “over-strictness.”
If the algorithm is too strict, it might miss some genuine neighbors.
To fix that, the process is repeated multiple times-say, twenty times-with different grids, producing 20 distinct tables. If two items don’t fall into the same group in table 1, they might do so in table 12. The proposed method shows excellent performance with sparse data.
For example, on a news website, there are thousands of articles — each may correspond to a vector with a hundred thousand characters, yet only about 500 words actually distinguish one article from another.
An article about “fire” might contain the word “fire” as its unique identifier, while still sharing many common words and characters such as “the,” “of,” “in,” etc., with other articles. Traditional algorithms scan all hundred thousand entries, even the ones with zero value meaning all the shared words. But Mirrokni’s approach, using inner product projection, automatically ignores zero-value entries — meaning only those 500 distinctive words are processed, leading to vastly faster searches.
With that in mind, the Mirrokni method isn’t just another algorithm — it’s really a bridge between data distribution and data engineering. What this researcher has essentially proposed is a new approach: instead of translating complex data into the computer’s language of zeros and ones just to measure similarity, we can build an intelligent mathematical network — almost like a ruler — that casts directly over the original data and classifies it with remarkable speed and precision.
Final music