# A neural data structure for novelty detection

Contributed by Charles F. Stevens, October 30, 2018 (sent for review August 22, 2018; reviewed by Piotr Indyk and Glenn Turner)

## Significance

This work is significant for two reasons. First, considering fly olfaction in the context of a computational algorithm emphasizes features of olfactory processing that might otherwise be less apparent. For example, comparison of prior approaches for novelty detection makes clear that different odors are not just novel vs. familiar, but rather can have various degrees of novelty depending on the similarities between odors. Second, understanding how the fruit fly olfactory circuit detects novel odors can inspire new methods for similar problems in machine learning. In this way, both computer science and neuroscience benefit from the comparison of these two systems.

## Abstract

Novelty detection is a fundamental biological problem that organisms must solve to determine whether a given stimulus departs from those previously experienced. In computer science, this problem is solved efficiently using a data structure called a Bloom filter. We found that the fruit fly olfactory circuit evolved a variant of a Bloom filter to assess the novelty of odors. Compared with a traditional Bloom filter, the fly adjusts novelty responses based on two additional features: the similarity of an odor to previously experienced odors and the time elapsed since the odor was last experienced. We elaborate and validate a framework to predict novelty responses of fruit flies to given pairs of odors. We also translate insights from the fly circuit to develop a class of distance- and time-sensitive Bloom filters that outperform prior filters when evaluated on several biological and computational datasets. Overall, our work illuminates the algorithmic basis of an important neurobiological problem and offers strategies for novelty detection in computational systems.

### Sign up for PNAS alerts.

Get alerts for new articles, or get an alert when an article is cited.

Assessing whether a stimulus is novel is a basic neural problem that helps alert organisms to new and potentially salient events (1, 2). This problem requires determining how much a given stimulus departs from those previously experienced. Here, we describe a simple data structure used by neural circuits to efficiently solve this problem.

The fruit fly determines the novelty of an odor using a two-step procedure. The first step involves assigning a “tag” (the term used in neurobiology) or “hash” (the term used in computer science) to the odor, where the tag/hash corresponds to a small set of neurons that fire action potentials in response to the odor (3–7). An odor is initially encoded in the fly’s nose as a 50-dimensional vector, corresponding to the firing rates of 50 different types of odorant receptor neurons (ORNs) (8). The 50 ORNs send odor information to 50 projection neuron types (PNs), whose responses are normalized such that the mean firing rate of the PNs is nearly the same for all odors and odor concentrations (6, 9). The PNs then project to about 2,000 Kenyon cells (KCs) that lie in a structure called the “mushroom body.” The connection matrix between the 50 PNs and the 2,000 KCs is sparse, approximately binary, and random (10). Each KC randomly selects about 6 of the 50 PNs and sums up their firing rates. Each KC then provides feedforward excitation to a single inhibitory neuron, which provides feedback inhibition to all of the KCs. As a result of this winner-take-all computation, only the top $\sim $5% (100) of the highest-rate KCs fire in response to the odor; the remaining 95% are silenced. This 5% corresponds to the tag/hash of the odor. Thus, the hash of an odor is a sparse point in a 2,000-dimensional space. Each distinct odor activates a different 5% of the KCs, such that two very different odors will have little to no overlap in their active KCs.

The second step in determining odor novelty is to decide whether an odor, as defined by its hash, has been previously experienced. The output of the mushroom body is generated by 34 mushroom body output neurons (MBONs) that receive input from the KCs and perform many different functions (11–13). Here, we are concerned with one such MBON, called $\text{MBON}-\alpha \prime 3$ (14) [$\text{MBON}-\alpha \prime 3$ actually consists of two distinct neurons that Hattori et al. (14) could not distinguish between; we follow their convention here and treat them together], which receives inputs from 350 of the 2,000 KCs (11) (see

*SI Appendix*for more anatomical details). Based on a series of elegant experiments, Hattori et al. (14) showed that the activity of $\text{MBON}-\alpha \prime 3$ in response to an odor encodes a novelty signal for the odor and that this signal is suppressed with odor familiarization (repeated presentations of the same odor).Hattori et al. (14) proposed the following model of how $\text{MBON}-\alpha \prime 3$ encodes novelty. For each odor presented to the fly, the hash for that odor is a sparse set of about 20 KCs ($\sim $5–10% of the 350 KCs that project to $\text{MBON}-\alpha \prime 3$). Local dopamine released by a neuron called $\text{PPL}1-\alpha \prime 3$ then modifies the strength of the 350 $\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapses. Synapses made by the odor’s 20 activated KCs onto $\text{MBON}-\alpha \prime 3$ weaken, whereas synapses made by nonactive KCs onto $\text{MBON}-\alpha \prime 3$ strengthen. The activity of $\text{MBON}-\alpha \prime 3$ is computed as the weighted sum of its inputs (i.e., the activity of each KC multiplied by its synaptic strength). Thus, repeated exposure to the same odor depresses active $\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapses, which suppresses the activity of $\text{MBON}-\alpha \prime 3$ in response to the odor, indicating that the odor has become familiar. At the same time, the synapses of nonactive KCs onto $\text{MBON}-\alpha \prime 3$ strengthen, increasing over time the novelty response of odors with nonoverlapping hashes.

## Our Contributions

From a computer science perspective, we view the $\mathrm{K}\mathrm{C}\to \mathrm{\text{MBON-}}\alpha \prime 3$ synapses as storing a Bloom filter (Fig. 1). A Bloom filter is a space-efficient data structure that serves as the foundation for answering the question, “Does $x$ belong to $\mathcal{S}$?”, where $x$ is some query item (an odor) and $\mathcal{S}$ is a database of previously observed items. If $x$ does not belong to $\mathcal{S}$, then the item is considered novel, and vice versa. This question naturally comes up in many large-scale computing applications. For example, when Google indexes the web, its web crawler, upon reaching a website ($x$), needs to quickly determine whether it has visited this site in the past ($\mathcal{S}$) to avoid the cost of reindexing. Similarly, determining whether a DNA sequence ($x$) belongs to a database ($\mathcal{S}$) is a common primitive for many bioinformatics applications (15, 16).

Fig. 1.

The fly’s Bloom filter, however, modifies this basic question in three ways:

*i*)

Continuous-valued novelty. For the fly, novelty responses should reflect how different the query item is from those previously experienced. A traditional Bloom filter, on the other hand, reports only a binary response, indicating whether or not the exact item is in the database.

*ii*)

Distance sensitivity. The novelty of an odor with respect to a similar odor should be smaller than the novelty of the odor with respect to a very different odor. A traditional Bloom filter does not provide distance sensitivity, instead treating each pair of unique items as equidistant from all other pairs. Distance sensitivity also provides robustness, since in a noisy environment, it is unlikely that the fly will observe the exact same odor twice.

*iii*)

Time sensitivity. For the fly, if the same or a similar odor was last experienced a long time ago, its novelty should be larger than if the odor was experienced recently. A traditional Bloom filter, on the other hand, does not discount novelty over time.

The first two properties above modify the question to ask, “How close is $x$ to some item in $\mathcal{S}$?” The third property asks, “How long ago was $x$, or some item similar to $x$, observed?” These modifications are also relevant practically. For example, when recommending news articles, one might ask, “How novel is this article compared with other articles the user has (recently) read?” or, “How different is this patient’s profile compared with others who have (recently) signed up for a clinical trial?” (15). While there are Bloom filters that satisfy properties two (15, 17–20) and three (21–23) separately, we are not aware of a Bloom filter that accounts for all three properties together. There are also technical differences between the fly’s Bloom filter and prior filters, which we elaborate below.

Here, we extend the framework of Hattori et al. (14) to quantitatively predict neural novelty responses based on the theory of Bloom filters. We also translate these three properties to extend a fundamental data structure to more application domains.

## Results

### The Mapping Between Bloom Filters and Novelty Detection Circuits.

Here, we consider how to interpret the $\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapses as a Bloom filter and how to modify traditional Bloom filters to take into account the three properties noted in the preceding section.

Consider the problem, “Does $x$ belong to $\mathcal{S}$?” This problem could be easily solved by keeping a sorted list of all of the items in $\mathcal{S}$ and then performing a binary search for $x$ or by inserting each item into a hash table and performing a lookup. The problem with these approaches is that they require storing all items in $\mathcal{S}$ in memory (e.g., in a list or a hash table), which can be prohibitively expensive for very large databases or if storing millions of small databases. Bloom filters are a space-efficient alternative that requires only a small number of bits per item to store, independent of the size or content of each individual item.

Formally, we are given a database of $n$ items, $\mathcal{S}=\left\{{s}_{1},{s}_{2},\dots ,{s}_{n}\right\}$ and a query item $x$. In a traditional Bloom filter, the goal is to output a binary novelty score, $f\left(x,\mathcal{S}\right)\in \left\{\mathrm{0,1}\right\}$ of $x$ with respect to $\mathcal{S}$. The objective function (Does $x$ belong to $\mathcal{S}?$) isFor the fly, the goal is to output a continuous-valued novelty score, $f\left(x,\mathcal{S}\right)\in \left[\mathrm{0,1}\right]$ of $x$ with respect to $\mathcal{S}$, and this score should be distance sensitive (we consider the third property, time sensitivity, later). Distance sensitivity means that $f$ should reduce the novelty of $x$ if there is an item similar to $x$ in the database. The objective function (How close is $x$ to some item in $\mathcal{S}?$) iswhere $d\left(x,{s}_{i}\right)$ is a distance measure between items $x$ and ${s}_{i}$. If $f\left(x,\mathcal{S}\right)=1$, $x$ is highly novel, whereas if $f\left(x,\mathcal{S}\right)=0$, $x$ is highly familiar.

$$f\left(x,\mathcal{S}\right)=\left\{\begin{array}{cc}0\hfill & \hspace{1em}\text{if}x\in \mathcal{S}\hfill \\ 1\hfill & \hspace{1em}\text{otherwise.}\hfill \end{array}\right.$$

$$f\left(x,\mathcal{S}\right)=\underset{{s}_{i}\in \mathcal{S}}{min}\hspace{0.17em}d\left(x,{s}_{i}\right),$$

[1]

The goal of a Bloom filter is to approximate $f\left(x,\mathcal{S}\right)$ using a compressed $m$-bit representation of $\mathcal{S}$. In general, $m>n$, where $n$ is the number of items in $\mathcal{S}$, and a typical value of $m$ is $10n$ (i.e., 10 bits per item stored). In a traditional Bloom filter (Fig. 1

*A*), each of the $m$ bits is initialized to 1. (Conventionally, Bloom filters are initialized to 0 instead of to 1. We describe an “inverted” Bloom filter here so that novel items illicit a high novelty response instead of a low response, but the argument remains the same.) Each $s\in \mathcal{S}$ is inserted into the filter by applying $k\ll m$ independent hash functions to $s$. Each hash function maps $s$ to one of the $m$ positions in the Bloom filter, and each of these positions is reset to 0. To determine the novelty of a query $x$, one applies the same $k$ hash functions to $x$ to obtain $k$ positions in the Bloom filter; if any of these bits are set to 1, then the item definitely does not belong to $\mathcal{S}$. If all of the bits are set to 0, then the item probably belongs to $\mathcal{S}$. This procedure can induce some false positives if, for example, the bits probed for $x$ collectively overlap with the bits reset for items previously inserted (e.g., see Fig. 1*A*for chardonnay).For the fly, we propose that the $\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapses store a Bloom filter for novelty detection (Fig. 1In other words, the synaptic weights of the $k$ active KCs for the odor each decay by some factor, $0\le \delta <1$. The remaining $m-k$ KCs strengthen by a small amount, $0\le \u03f5\le 1$. [Here, we assume that each KC’s activity for an odor is binary (on or off), which is an approximation (

*B*). Here, the $m\hspace{0.17em}\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapses represent the $m$ bits of storage in the Bloom filter. The indexes of the $k$ active KCs for an odor act as the $k$ hashed positions of the odor. When an odor is presented (i.e., inserted into the filter), the strength of each of the $m$ synapses is modified. Let $w\left(i\right)$ correspond to the weight of the*i*^{th}$\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapse. Initially, each $w\left(i\right)=1$. After an odor $x$ is observed, each synaptic weight changes as follows:$$w\left(i\right)=\left\{\begin{array}{cc}w\left(i\right)\times \delta \hfill & \hspace{1em}\text{if the}\hspace{0.17em}{i}^{\text{th}}\text{KC is active for}\hspace{0.17em}x\hfill \\ w\left(i\right)+\u03f5\hfill & \hspace{1em}\text{if the}\hspace{0.17em}{i}^{\text{th}}\text{KC is not active for}\hspace{0.17em}x.\hfill \end{array}\right.$$

[2]

*SI Appendix*).] When ignoring time, we set $\delta =0$ and $\u03f5=0$ so that once an odor activates a KC, its weight gets reset to 0, and no recovery occurs with the presentation of subsequent odors. Thus, all synaptic weights are binary (bits), as in a traditional Bloom filter. See*SI Appendix*, Fig. S3 for justification of these functional forms for recovery and decay.To generate a continuous-valued novelty score of an odor $x$ from the Bloom filter, we sum the weights of the $k$ active $\mathrm{K}\mathrm{C}\to \text{MBON}-\alpha \prime 3$ synapses for odor $x$ and normalize by $k$ to generate novelty responses between 0 and 1 (Fig. 1

*B*). Because all weights are binary (ignoring time), the only weights that will be 1 are those corresponding to KCs that are active for $x$ and no other odor in $\mathcal{S}$ previously inserted into the filter.### Predicting Neural Novelty Responses to Odor Pairs.

Using the reasoning above, the novelty response of an odor with respect to a single previous odor should be proportional to the percentage of KCs shared by the two odors: higher overlap $\to $ smaller novelty response. We tested this hypothesis using neural recordings of $\text{MBON}-\alpha \prime 3$ in response to pairs of odors, where one odor was presented, and then the activity of $\text{MBON}-\alpha \prime 3$ was recorded in response to a second odor (14) (

*SI Appendix*, Table S1). In this setting, $\left|\mathcal{S}\right|=1$ (containing the first odor), and we wish to predict the novelty of $x$, a second odor. Hattori et al. (14) did not describe or analyze how odor similarity might affect novelty responses in the fly.To determine the similarity of two odors below, we used a publicly available database [DoOR 2.0 (24)], which provides ORN responses to different odors by collecting experimental data from many studies.

First, we tested how odor similarity, defined based on the differences in ORN activity for the two odors, affected novelty responses. Specifically, each odor was associated with a vector of recorded ORN activity in response to the odor, using the DoOR database (24). We found a significant correlation between the Euclidean distance between the vectors and the recorded novelty response of $\text{MBON}-\alpha \prime 3$ for the pair: Higher distance $\to $ larger novelty ($r=0.91$; Fig. 2

*A*).Fig. 2.

Second, we tested how well the predicted novelty score from the fly Bloom filter, defined based on the overlap of active Kenyon cells for the pair, correlated with the recorded novelty response. Specifically, the KC responses for each odor were computed by multiplying the vector of ORN activity for the odor by a sparse, binary random projection matrix (7, 10) into an $m=350$-dimensional space. We then set the indexes of the $k=20$ ($\approx 5\%$ of 350) most rapidly firing KCs to 1 and set the rest of the indexes to 0. We again found that the more overlap in active KCs shared by the pair, the lower the novelty response for the pair ($r=-0.94$; Fig. 2

*B*). Due to the small number of odor pairs available, we tested how robust these correlations were, using leave-one-out cross-validation, and found no change to our conclusions (*SI Appendix*, Table S3).Overall, these results show that the similarity between odors—calculated either in input ORN space or in KC hash space—could predict the novelty response for the pair. Further, the similarity between two odors can be read off from the output of the Bloom filter in a manner that is consistent with the first and second properties that we proposed.

### Analytically Predicting Novelty Responses.

In

*SI Appendix*, we mathematically derive the expected novelty response from the fly Bloom filter for an item $x$ with respect to a set of previously observed items $\mathcal{S}$. We also instantiate bounds on the expected novelty responses for the cases where inputs are binary or exponentially distributed [as in faces (25) and odors (6)] (*SI Appendix*, Fig. S1).### Empirical Evaluation on Benchmark Datasets.

To translate these neural insights to the computational domain, we compared three types of Bloom filters—the fly Bloom filter, a traditional Bloom filter, and a prior distance-sensitive Bloom filter (LSBF) (15, 17) (

*SI Appendix*, Algorithms S1–S3). We compared performance on five datasets (*SI Appendix*, Table S2); for each dataset, we used 10-fold cross-validation, where all items from the training set $\mathcal{S}$ are inserted into the Bloom filter. Then, for each item in the test set, we computed its ground-truth novelty response via Eq.**1**and the predicted novelty from the filter, and we report the correlation between the ground-truth and predicted novelty responses over all items in the test set. We set $m=30n$ and varied $k\in \left[\mathrm{5,50}\right]$.First, we evaluated performance on two neural datasets (Fig. 3

*A*and*B*). The first one contains neural activity of 24 ORNs in the fruit fly in response to $n=110$ odors (8). The second one contains neural activity of 99 face patch neurons in the macaque in response to $n=\mathrm{2,000}$ faces (26). In both cases, we found significant improvement in novelty detection using the fly Bloom filter compared with the alternatives. For example, on the odors dataset, the correlation between ground-truth and predicted novelty using the fly Bloom filter was $0.657\pm 0.06$ compared with $0.537\pm 0.08$ using the LSBF ($k=40$). Similarly, on the face data, the correlations were $0.508\pm 0.03$ for the fly vs. $0.404\pm 0.03$ for the LSBF. On all datasets, the traditional Bloom filter had close to zero correlation between ground-truth and predicted novelty because the hash functions used in a traditional Bloom filter are random and not distance sensitive.Fig. 3.

Second, we tested performance on three computational datasets. The first two are image datasets [scale-invariant feature transform descriptors (SIFT) and modified National Institute of Standards and Technology database (MNIST)] with $n=\mathrm{5,000}$ each, and the third one is random data drawn from an exponential distribution (Fig. 3

*C*–*E*). In all three cases, the fly Bloom filter outperforms, or performs no worse than, other filters. For example, on the SIFT dataset, the fly Bloom filter achieved a correlation of $0.535\pm 0.03$ vs. $0.345\pm 0.03$ and $0.002\pm 0.02$ for the LSBF and traditional filters, respectively. We also repeated all experiments with $m=10n$ and found similar results (*SI Appendix*, Fig. S2).Overall, the fly Bloom filter enhances novelty detection vs. that of other filters, while using the same space-efficient representation.

### Building Distance- and Time-Sensitive Bloom Filters.

Similar items observed recently in time should illicit a lower novelty response than similar items observed far apart in time. This means that old data stored in the Bloom filter should slowly decay or be evicted from the filter over time. Eviction is also important in life-long learning applications, where the database is not of fixed size but continuously grows (21–23); unless old data are forgotten, the Bloom filter would eventually fill up such that every bit is reset to zero.

Currently, there is little biological knowledge of how distance sensitivity and time sensitivity combine to create a single novelty response in the fruit fly (

*Discussion*). In*SI Appendix*, we propose candidate objective functions and show that the fly Bloom filter also works well in this scenario (*SI Appendix*, Table S4).## Discussion

The fruit fly brain evolved a simple space-efficient data structure to compute the novelty of odors, directly taking advantage of sparse, high-dimensional representations (27–29) useful for discriminating odors (7, 30). Our framework can be used to predict novelty responses in fruit flies to odor pairs (14) and can be used to enhance novelty detection for computational applications (31, 32), including for anomaly detection (33), computer networking (34), and deep learning (35, 36).

There are many variants of Bloom filters that extend the basic functionality of traditional Bloom filters. These include filters that adapt $k$, the number of hash functions used, based on the popularity of the data (37, 38), that decentralize the filter to handle failures (2, 39), that allow items to be deleted (16, 40, 41), and that use other sophisticated inference steps (42). In practice, some of these features may need to be ported to the fly’s Bloom filter. There are also several methods used to compress high-dimensional datasets that enable estimating $f\left(x,\mathcal{S}\right)$ efficiently using a nearest-neighbors search (43). For example, Jégou et al. (44) learn short codes for dataset items using product quantization techniques, and Johnson et al. (45) further speed up these computations using GPUs. Indyk and Wagner (46) develop a space-efficient tree-based data structure for storing items that requires less bits per item to store than prior structures. Compared with the approach presented here, these methods are not based on Bloom filters, are not dynamic (time sensitive), and do not appear to be biologically plausible. Nonetheless, in practical applications of novelty detection, these approaches should also be considered.

Our work raises three questions about timing mechanisms and their effect on novelty calculations:

*i*)

The rates of synapse weight recovery ($\u03f5$) and decay ($\delta $) may provide clues of how the brain recovers and suppresses novelty over time. Based on experimental data, the functional forms of these two parameters appear to follow an additive-increase, multiplicative-decrease mechanism (

*SI Appendix*, Fig. S3); interestingly, multiplicative weight update rules are also commonly used by online learning algorithms to converge to optimal decisions over time (47–49). While this is one possible mathematical form for recovery and decay, for the fly Bloom filter to compute novelty values as one might expect, two general rules seem to apply. First, decay after initial exposure to an odor should be aggressive. If decay were slow, then the novelty signal would persist over several successive presentations of an odor, which may unnecessarily burden attention. Further, aggressive decay immediately heightens the difference between an odor observed once recently (familiar) vs. an odor that has not been observed for a long time (novel). Second, recovery from familiarity back to novelty should be relatively slower. Otherwise, very soon after observing an odor, the odor would become novel again, limiting the timescale over which novelty can be integrated. More work, however, is needed to test these rules behaviorally.*ii*)

More information is needed about how novelty calculations trade off distance vs. time; i.e., how can the fruit fly distinguish between two similar odors observed far apart in time vs. two dissimilar odors observed recently in —both of which may illicit a high novelty response? Might other MBONs be involved? Computationally, given the local synaptic weight update rule (Eq.

**2**), can we reverse engineer the global objective function that the local rule is trying to optimize?*iii*)

The amount of dopamine released by $\text{PPL}1-\alpha \prime 3$ for an odor, which may affect recovery and decay rates, could be related to the odor’s concentration or valence and may be regulated by feedback from other MBONs (50); at the extreme, if no dopamine is released for an odor, then this might imply that the odor was not “inserted into the filter.”

Understanding these parameters may allow novelty responses to be predicted for a time sequence of odors, instead of simply odor pairs.

The theory of Bloom filters presented here may also help inform studies of novelty detection in other species and brain regions. Evidence points to similar patterns of decay and recovery of novelty responses, albeit over longer timescales, in the vertebrate olfactory system (51). Novelty detection also occurs in the hippocampus (52), in the amygdala (53), and in auditory systems (54), although circuit mechanisms here are less known.

## Materials and Methods

In

*SI Appendix*, we describe (*i*) additional background on the fly olfactory and novelty detection circuits, (*ii*) the data used for analyzing novelty responses to odor pairs and cross-validation results, (*iii*) the three Bloom filters used in our empirical comparison, (*iv*) computational analysis of distance- and time-sensitive Bloom filters, and (*v*) theoretical analysis of the fly Bloom filter for predicting novelty responses.## Acknowledgments

The authors thank John Berkowitz, Shyam Srinivasan, and Jaiyam Sharma for helpful comments on the manuscript. S.N. was supported by the Pew Cheritable Trusts, the Kavli Institute for Brain and Mind, and the National Institute on Deafness and Other Communication Disorders (NIDCD) of the National Institutes of Health under Award 1R01DC017695.

## Supporting Information

Appendix (PDF)

- Download
- 748.85 KB

## References

1

C Ranganath, G Rainer, Neural mechanisms for detecting and remembering novel events.

*Nat Rev Neurosci***4**, 193–202 (2003).2

G Koloniari, N Ntarmos, E Pitoura, D Souravlias, One is enough: Distributed filtering for duplicate elimination.

*Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM ’11*. Available at https://dl.acm.org/citation.cfm?id=2063643. Accessed April 2, 2018. (2011).3

A Leonardo, Degenerate coding in neural systems.

*J Comp Physiol A Neuroethol Sens Neural Behav Physiol***191**, 995–1010 (2005).4

RA Campbell, et al., Imaging a population code for odor identity in the Drosophila mushroom body.

*J Neurosci***33**, 10568–10581 (2013).5

GC Turner, M Bazhenov, G Laurent, Olfactory representations by Drosophila mushroom body neurons.

*J Neurophysiol***99**, 734–746 (2008).6

CF Stevens, What the fly’s nose tells the fly’s brain.

*Proc Natl Acad Sci USA***112**, 9460–9465 (2015).7

S Dasgupta, CF Stevens, S Navlakha, A neural algorithm for a fundamental computing problem.

*Science***358**, 793–796 (2017).8

EA Hallem, JR Carlson, Coding of odors by a receptor repertoire.

*Cell***125**, 143–160 (2006).9

SR Olsen, V Bhandawat, RI Wilson, Divisive normalization in olfactory population codes.

*Neuron***66**, 287–299 (2010).10

SJ Caron, V Ruta, LF Abbott, R Axel, Random convergence of olfactory inputs in the Drosophila mushroom body.

*Nature***497**, 113–117 (2013).11

Y Aso, et al., The neuronal architecture of the mushroom body provides a logic for associative learning.

*Elife***3**, e04577 (2014).12

T Hige, Y Aso, MN Modi, GM Rubin, GC Turner, Heterosynaptic plasticity underlies aversive olfactory learning in Drosophila.

*Neuron***88**, 985–998 (2015).13

SY Takemura, et al., A connectome of a learning and memory center in the adult Drosophila brain.

*Elife***6**, 26975 (2017).14

D Hattori, et al., Representations of novelty and familiarity in a mushroom body compartment.

*Cell***169**, 956–969 (2017).15

A Kirsch, M Mitzenmacher, Distance-sensitive Bloom filters.

*Proceedings of the Meeting on Algorithm Engineering & Expermiments, ALENEX ’06*. Available at https://epubs.siam.org/doi/abs/10.1137/1.9781611972863.4. Accessed April 11, 2018. (2006).16

P Pandey, MA Bender, R Johnson, R Patro, A general-purpose counting filter: Making every bit count.

*Proceedings of the ACM International Conference on Management of Data, SIGMOD ’17*. Available at https://dl.acm.org/citation.cfm?id=3035963. Accessed April 19, 2018. (2017).17

Y Hua, B Xiao, B Veeravalli, D Feng, Locality-sensitive Bloom filter for approximate membership query.

*IEEE Trans Comput***61**, 817–830 (2012).18

M Goswami, R Pagh, F Silvestri, J Sivertsen, Distance sensitive Bloom filters without false negatives.

*Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17*. Available at https://dl.acm.org/citation.cfm?id=3039703. Accessed May 2, 2018. (2017).19

U Manber, S Wu, An algorithm for approximate membership checking with application to password security.

*Inf Process Lett***50**, 191–197 (1994).20

J Qian, Q Zhu, H Chen, Multi-granularity locality-sensitive Bloom filter.

*IEEE Trans Comput***64**, 3500–3514 (2015).21

F Deng, D Rafiei, Approximately detecting duplicates for streaming data using stable Bloom filters.

*Proceedings of the ACM International Conference on Management of Data, SIGMOD ’06*. Available at https://dl.acm.org/citation.cfm?id=1142477. Accessed April 24, 2018. (2006).22

L Zhang, Y Guan, Detecting click fraud in pay-per-click streams of online advertising networks.

*The 28th International Conference on Distributed Computing Systems, 2008. ICDCS’08*. Available at https://ieeexplore.ieee.org/document/4595871. Accessed April 12, 2018. (2008).23

Y Zhao, J Wu, B-sub: A practical Bloom-filter-based publish-subscribe system for human networks.

*Proceedings of the 30th IEEE International Conference on Distributed Computing Systems, ICDCS ’10*. Available at https://ieeexplore.ieee.org/document/5541685. Accessed May 30, 2018. (2010).24

D Munch, CG Galizia, DoOR 2.0–comprehensive mapping of Drosophila melanogaster odorant responses.

*Sci Rep***6**, 21841 (2016).25

CF Stevens, Conserved features of the primate face code.

*Proc Natl Acad Sci USA***115**, 584–588 (2018).26

L Chang, DY Tsao, The code for facial identity in the primate brain.

*Cell***169**, 1013–1028 (2017).27

GJ Rinkus, Sparsey: Event recognition via deep hierarchical sparse distributed codes.

*Front Comput Neurosci***8**, 160 (2014).28

B Babadi, H Sompolinsky, Sparseness and expansion in sensory representations.

*Neuron***83**, 1213–1226 (2014).29

Y Cui, S Ahmad, J Hawkins, The HTM spatial pooler-A neocortical algorithm for online sparse distributed coding.

*Front Comput Neurosci***11**, 111 (2017).30

AC Lin, AM Bygrave, A de Calignon, T Lee, G Miesenbock, Sparse, decorrelated odor coding in the mushroom body enhances learned odor discrimination.

*Nat Neurosci***17**, 559–568 (2014).31

MAF Pimentel, DA Clifton, L Clifton, L Tarassenko, Review: A review of novelty detection.

*Signal Process***99**, 215–249 (2014).32

M Markou, S Singh, Novelty detection: A review—Part 2: Neural network based approaches.

*Signal Process***83**, 2499–2521 (2003).33

C Luo, A Shrivastava, Arrays of (locality-sensitive) count estimators (ACE): Anomaly detection on the edge.

*Proceedings of the 2018 World Wide Web Conference, WWW ’18*. Available at https://dl.acm.org/citation.cfm?id=3186056. Accessed June 8, 2018. (2018).34

A Broder, M Mitzenmacher, Network applications of Bloom filters: A survey.

*Internet Math***1**, 485–509 (2004).35

J Serrà, A Karatzoglou, Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks. arXiv:1706.0399. Preprint, posted June 13, 2017. (2017).

36

A Salvi, S Ercoli, M Bertini, AD Bimbo, Bloom filters and compact hash codes for efficient and distributed image retrieval. arXiv:1605.00957. Preprint, posted May 3, 2016. (2016).

37

J Bruck, J Gao, A Jiang, Weighted Bloom filter.

*IEEE International Symposium on Information Theory*. Available at https://ieeexplore.ieee.org/document/4036381. Accessed April 22, 2018. (2006).38

M Zhong, P Lu, K Shen, J Seiferas, Optimizing data popularity conscious Bloom filters.

*Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, PODC ’08*. Available at https://dl.acm.org/citation.cfm?id=1400798. Accessed May 30, 2018. (2008).39

RP Laufer, PB Velloso, OCMB Duarte, A generalized Bloom filter to secure distributed network applications.

*Comput Netw***55**, 1804–1819 (2011).40

L Fan, P Cao, J Almeida, AZ Broder, Summary cache: A scalable wide-area web cache sharing protocol.

*IEEE/ACM Trans Netw***8**, 281–293 (2000).41

B Fan, DG Andersen, M Kaminsky, MD Mitzenmacher, Cuckoo filter: Practically better than Bloom.

*Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies, CoNEXT ’14*. Available at https://dl.acm.org/citation.cfm?id=2674005.2674994. Accessed April 2, 2018. (2014).42

JL Dautrich, CV Ravishankar, Inferential time-decaying Bloom filters.

*Proceedings of the 16th International Conference on Extending Database Technology, EDBT ’13*. Available at https://dl.acm.org/citation.cfm?id=2452376.2452405. Accessed June 4, 2018. (2013).43

J Wang, W Liu, S Kumar, S Chang, Learning to hash for indexing big data—a survey.

*Proc IEEE***104**, 34–57 (2016).44

H Jegou, M Douze, C Schmid, Product quantization for nearest neighbor search.

*IEEE Trans Pattern Anal Mach Intell***33**, 117–128 (2011).45

J Johnson, M Douze, H Jégou, Billion-scale similarity search with GPUs. arXiv:1702.08734. Preprint, posted February 28, 2017. (2017).

46

P Indyk, T Wagner, Approximate nearest neighbors in limited space.

*Proceedings of the 31st Conference On Learning Theory (COLT), Proceedings of Machine Learning Research*, eds J Dy, A Krause (Proceedings of Machine Learning Research, Stockholm)**Vol 75**, 2012–2036 (2018).47

S Arora, E Hazan, S Kale, The multiplicative weights update method: A meta-algorithm and applications.

*Theor Comput***8**, 121–164 (2012).48

JY Suen, S Navlakha, Using inspiration from synaptic plasticity rules to optimize traffic flow in distributed engineered networks.

*Neural Comput***29**, 1204–1228 (2017).49

DM Chiu, R Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.

*Comput Netw ISDN Syst***17**, 1–14 (1989).50

K Eichler, et al., The complete connectome of a learning and memory centre in an insect brain.

*Nature***548**, 175–182 (2017).51

HK Kato, MW Chu, JS Isaacson, T Komiyama, Dynamic sensory representations in the olfactory bulb: Modulation by wakefulness and experience.

*Neuron***76**, 962–975 (2012).52

R Knight, Contribution of human hippocampal region to novelty detection.

*Nature***383**, 256–259 (1996).53

JU Blackford, JW Buckholtz, SN Avery, DH Zald, A unique role for the human amygdala in novelty detection.

*Neuroimage***50**, 1188–1193 (2010).54

MS Malmierca, MV Sanchez-Vives, C Escera, A Bendixen, Neuronal adaptation, novelty detection and regularity encoding in audition.

*Front Syst Neurosci***8**, 111 (2014).## Information & Authors

### Information

#### Published in

#### Classifications

#### Copyright

© 2018. Published under the PNAS license.

#### Submission history

**Published online**: December 3, 2018

**Published in issue**: December 18, 2018

#### Keywords

#### Acknowledgments

The authors thank John Berkowitz, Shyam Srinivasan, and Jaiyam Sharma for helpful comments on the manuscript. S.N. was supported by the Pew Cheritable Trusts, the Kavli Institute for Brain and Mind, and the National Institute on Deafness and Other Communication Disorders (NIDCD) of the National Institutes of Health under Award 1R01DC017695.

### Authors

#### Competing Interests

The authors declare no conflict of interest.

## Metrics & Citations

### Metrics

#### Citation statements

#### Altmetrics

### Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

#### Cited by

Loading...

## View Options

### View options

#### PDF format

Download this article as a PDF file

DOWNLOAD PDF### Get Access

#### Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Personal login Institutional Login#### Recommend to a librarian

Recommend PNAS to a Librarian#### Purchase options

Purchase this article to access the full text.