LA JOLLA—Every day, websites you visit and smartphone apps that you use are crunching huge sets of data to find things that resemble each other: products that are similar to your past purchases; songs that are similar to tunes you’ve liked; faces that are similar to people you’ve identified in photos. All these tasks are known as similarity searches, and the ability to perform these massive matching games well—and fast—has been an ongoing challenge for computer scientists.
“This is a problem that pretty much every technology company with any kind of information retrieval system has to solve, so it’s been something that computer scientists have studied for years,” says Saket Navlakha, assistant professor in Salk’s Integrative Biology Laboratory and lead author of the new paper. “Now, we have this new approach to similarity searches thanks to the fly.”
The way most computerized data systems categorize items?from songs to images?to optimize similarity searches is by reducing the amount of information associated with each item. These systems assign short “hashes” to each item so that similar items are more likely to be assigned the same or a similar hash compared to two very different items. (Hashes are a kind of digital shorthand, the way a bitly is a shorter version of a URL.) Assigning hashes in this way is called “locality-sensitive hashing” to computer scientists. When searching for similar items, a program looks through the hashes, rather than the original items, to find similarities quickly.
Video credit: Salk Institute
Navlakha was chatting with colleague Charles Stevens, a professor in Salk’s Molecular Neurobiology Laboratory and a coauthor of the new work, who had studied fly olfaction, when the former realized that flies—and all animals—are constantly faced with similarity searches as well. So he started combing the literature on the brain circuitry behind fly olfaction to work out just how flies identify similar smells.
“In the natural world, you’re not going to encounter exactly the same odor every time; there’s going to be some noise and fluctuation,” Navlakha explains. “But if you smell something that you’ve previously associated with a behavior, you need to be able to identify that similarity and recall that behavior.” So if a fruit fly knows that the smell of a rotting banana means mealtime, it needs to respond the same way when it encounters a very similar smell, even if it never experienced that exact smell before.
“Say you have a bunch of people clustered by their relationships, and they’re bunched into a crowded room,” he explains. “Then take the same people and relationships, but have them spread out on a football field. It will be much easier to see the structure of relationships and draw boundaries between groups in the expanded space relative to the crowded space.”
While Navlakha and his collaborators did not reveal the actual mechanism by which flies are storing odor information—that was already available in the literature—they are the first to analyze how this process maximizes speed and efficiency for similarity searches. When they applied the process to three standard datasets computer scientists use to test search algorithms, they found that the fly approach improved performance. This approach, they think, may inform computer programs someday.
“Pieces of this approach had been used in the past by computer scientists, but evolution put it together in a very unique way,” says Navlakha.
Navlakha’s collaborators say that the study is among the first to make such concrete parallels between neural circuits in the brain and information processing algorithms used in computer science.
“For the past 20 years I’ve been interested in random projections [a core component of locality-sensitive hashing for similarity search] as they apply to algorithms running on computers,” says Sanjoy Dasgupta, a professor of computer science and engineering at UCSD and first author of the new paper. “It never occurred to me that similar operations may be at work in nature.”
“A dream shared by neurobiologists and computer scientists is to understand how the brain computes well enough that we can adapt its methods to improve machine computation,” adds Stevens. “Our paper provides a proof of principle that this dream may become reality.”
The work and the researchers involved were supported by grants from the National Science Foundation (EAGER PHY-1444273) and the Army Research Office (DOD W911NF-17-1-0045).