Powerful Search Algorithm Was Inspired by Fruit Fly’s Brain

Some of the most advanced search algorithms in the world — like the ones that suggest similar songs on Spotify or other stuff you might like to buy on Amazon — could learn a few things from the humble fruit fly.

That’s according to a team of researchers from the Salk Institute who discovered that the novel neural circuitry in a fruit fly’s tiny brain could be the inspiration for next-generation search algorithms that look for close matches in large datasets.

The finding, reported in the journal Science, explains how the humble fruit fly has evolved a smart solution to a fundamental challenge of computer science: how to design a search algorithm that tags and groups similar entries quickly in a very large database. These so-called similarity searches or nearest-neighbor searches are at the heart of many tech applications, from face-matching algorithms that organize your photos to marketing algorithms that try to predict your buying habits.

They’re also, the researchers showed, hardwired into the fruit fly’s brain. The tiny insects rely on similarity searches to quickly sort through odors in their environment. The smell of a rotting apple core means food, while the smell of a harsh chemical means poison. But more importantly, the fly can quickly process new odors that share similar characteristics or vectors with known smells. And the fly’s brain does this in an ingenious way — ingenious, at least, to computer scientists.

Saket Navlakha is an assistant professor in the Salk Institute’s Integrative Biology Lab and lead author of the fruit fly paper. A computer scientist by training, Navlakha stumbled onto the fruit fly’s nifty adaptation through conversations with his Salk colleague Charles Stevens, a molecular neurobiologist who’s studied the fly’s olfactory circuitry. Navlakha soon realized that the fly’s odor algorithms represented a new, and possibly more efficient type of similarity search.

When computer scientists write algorithms to run similarity searches, Navlakha told Seeker, they try to reduce the total number of vectors or dimensions that the computer has to analyze. In an image search, for example, the algorithm will only look at a fraction of the pixels in a 1,000-pixel image, maybe five or 10 percent, and then tag that image with a shorthand identifier called a hash.

“What the fruit fly is doing is the exact opposite,” said Navlakha. “Instead of reducing the number of dimensions, it actually expands them to be much larger — 10,000 pixels instead of 1,000.”

At first, that seems counterintuitive, since more pixels would appear to require more processing power and more time, reducing the overall speed and efficiency of the similarity search. But fruit flies have a trick up their sleeve, er, wing.

There are three steps to fruit fly’s search algorithm, which has been maximized for speed and low-power efficiency over millennia of neural evolution. In the first step, Navlakha explained, the smell is picked up by 50 odor-receptor neurons in the fly’s nose. Each neuron fires at a slightly different rate, so the odor is said to have 50 dimensions.

Then, instead of reducing those 50 dimensions down to five or 10 representative vectors, it explodes up to 2,000 dimensions. But the way that it expands is the brilliant part. Rather than simply multiplying each of the original 50 signals by 40, Navlakha said, the fly brain uses a technique called sparse, binary, random projection.

Here’s how it works. The 2,000 dimensions are encoded in 2,000 Kenyon cells, a type of neuron in the fly’s brain. Each of the Kenyon cells gets its firing rate by adding up the values of six randomly selected neurons from the original 50 odor receptors. Using this random sampling method, the fly can dive deeper into the odor data without overburdening its circuitry.

Navlakha uses the analogy of trying to identify family relationships within a group of 100 people.

“What computer scientists will do with those 100 people is stuff them into a crowded room. This is the low-dimensional space,” said Navlakha. “What the fly is doing is taking those 100 people and spreading them out on a football field. Then you can imagine that it would be very easy to delineate and find this group structure, as opposed to everyone being on top of each other in a room.”

RELATED: Some Butterflies Have Been Fooling Others for 2 Million Years

Once the odor data is spread out in the fly’s brain across 2,000 cells, a single neuron called APL does the sorting. It inhibits or shuts off all but the highest-firing Kenyon cells (the top five percent) and uses a “winner-take-all” method to tag the odor with a single descriptive hash.

The fly’s circuitry itself wasn’t a new discovery; the neurobiology was already relatively well understood. The new part was taking the fly’s three-step neural algorithm and translating it into computer code. Navlakha and his colleagues wanted to test the fly’s random expansion algorithm against more conventional similarity-search algorithms on large datasets.

The team ran the two algorithms against a standard database of 10,000 images with the goal of identifying a cluster of nearest matches. The results of each algorithm would be compared to the results of a slower, one-by-one, linear search that was sure to find the most similar images.

The fruit fly algorithm was the clear winner, effectively doubling the accuracy the conventional computer science method in both an image-similarity search and a text-based document search. The next step, Navlakha said, will be to analyze mammalian neural circuitry for further refinements and upgrades to nature’s evolutionary algorithm.

“It’s a really exciting time to study not only the brain, but all of biology. There are so many strategies of computation and flexibility and adaptation that we can learn,” said Navlakha. “This idea of using a random projection is such a fundamental principle in computer science. To see that evolution has figured out that it’s a good way to solve this problem... it keeps me up at night thinking about all this stuff.”

WATCH: What Makes Flies the Greatest Fliers?