A neural algorithm for a fundamental computing problem

By Sanjoy Dasgupta, C. Stevens, Saket Navlakha. 2017

238 citations recorded by the source corpus.

Fly brain inspires computing algorithm Flies use an algorithmic neuronal strategy to sense and categorize odors. Dasgupta et al. applied insights from the fly system to come up with a solution to a computer science problem. On the basis of the algorithm that flies use to tag an odor and categorize similar ones, the authors generated a new solution to the nearest-neighbor search problem that underlies tasks such as searching for similar images on the web. Science, this issue p. 793 Smell circuitry in the fly brain reveals a superior strategy for a common computer science task. Similarity search—for example, identifying similar images in a database or similar documents on the web—is a fundamental computing problem faced by large-scale information retrieval systems. We discovered that the fruit fly olfactory circuit solves this problem with a variant of a computer science algorithm (called locality-sensitive hashing). The fly circuit assigns similar neural activity patterns to similar odors, so that behaviors learned from one odor can be applied when a similar odor is experienced. The fly algorithm, however, uses three computational strategies that depart from traditional approaches. These strategies can be translated to improve the performance of computational similarity searches. This perspective helps illuminate the logic supporting an important sensory function and provides a conceptually new algorithm for solving a fundamental computational problem.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning (2018, methodology): “Furthermore, research from the neuroscience community suggests that locality-sensitivity hashing, the technique used in Section IV) to find nearest neighbors in the DkNN, may be a general principle of computation in the brain [91], [92].”
Neuronal mechanisms underlying innate and learned olfactory processing in Drosophila. (2019, background): “168 Notably, the KCs’ sparse coding scheme still allows flies to generalize learned associations 169 to similar odors (which could be viewed as noisy variations of the same odor) [52-54], a 170 property characteristic of a computer algorithm called locality-sensitive hashing, which 171 resembles KC ”
High-Dimensional Sparse Cross-Modal Hashing with Fine-Grained Similarity Embedding (2021, background): “Very recently, with biological observations on the fruit fly’s olfactory circuit, some studies have shown the mechanism of highdimensional sparse coding [8, 25, 35, 40].”