On the efficient calculation of van Rossum distances

Conor Houghton, Thomas KreuzNetwork 2012 · DOI

TL;DR

This paper introduces a computationally efficient algorithm for calculating the van Rossum distance between spike trains, a crucial metric in neuroscience. By employing a "markage vector" trick, the algorithm reduces the computational complexity from quadratic to linear in the number of spikes, making large-scale analyses of neural data feasible.

What Problem Does This Paper Address?

Neuroscience research often relies on quantifying the similarity or difference between neural activity patterns, represented as spike trains. The van Rossum metric is a popular choice for this, measuring the distance between two spike trains by essentially convolving them with an exponential kernel. While calculating a single distance is fast, many applications require computing a distance matrix for all pairs of spike trains in a dataset, or comparing populations of spike trains. These computations can become prohibitively slow, especially with large datasets or when exploring different parameter values for the metric. The paper tackles this computational bottleneck, aiming to make these analyses practical.

Methods

The core innovation is the introduction of a "markage vector." This vector is derived from a spike train and, crucially, allows the original quadratic terms in the van Rossum distance calculation to be replaced by sums involving this vector. This effectively transforms the calculation from an $O(n^2)$ operation (where $n$ is the number of spikes) to an $O(n)$ operation. The paper details how this trick is applied to the standard van Rossum metric, as well as to variations like the synapse-like metric and the multi-neuron van Rossum metric. The markage vector itself can be computed iteratively, further streamlining the process.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and uses simulated spike trains for evaluation.

Key Insights and Ideas

  • The "Markage Vector" is a Game Changer: This is the central insight. By cleverly reformulating the distance calculation, the authors bypass the need for pairwise comparisons of all spike times, drastically reducing computational cost.
  • Linear Complexity is Achievable: The ability to reduce the complexity from $O(n^2)$ to $O(n)$ for spike train comparisons is a significant algorithmic achievement.
  • Generalizability: The method isn't limited to the basic van Rossum metric; it extends to related metrics and even multi-neuron population comparisons, highlighting its broad applicability.
  • Biological Inspiration: The authors note that the "sum over history" replaced by a "running tally" is reminiscent of how biological systems might process information, adding an interesting layer to the computational trick.

Key Results

The paper demonstrates a substantial speedup in calculating van Rossum distances. For the regular van Rossum metric, the complexity is reduced from $O(N^2n^2)$ to $O(N^2n)$ for calculating a distance matrix of $N$ spike trains, each with $n$ spikes. Figure 1 shows that the algorithm with markage is significantly faster than the traditional algorithm, with run times scaling linearly with spike train length $L$ (which is proportional to $n$) compared to a quadratic scaling for the traditional method. For example, the best-fit curves suggest that for the algorithm with markage, $T_1 \approx \frac{17.4}{n} T_0$, indicating a speedup factor that increases with the number of spikes. Similar speedups were observed for the synapse-like and multi-neuron metrics.

Limitations and Future Work

  • Implementation Complexity: The authors acknowledge that the algorithms are "more complicated to implement" than straightforward approaches.
  • Constant Factors: While the asymptotic complexity is improved, the constant factors in the markage algorithm can be larger than the traditional one, meaning the speedup is most pronounced for longer spike trains. The paper suggests the new algorithm is worth using when there are more than approximately 17.4 spikes.
  • Kernel Limitations: The proposed markage trick is most effective for the causal exponential kernel and may not generalize to all kernel choices without significant modification or loss of efficiency.
  • Future Work: The paper mentions that Matlab and C++ source codes are available, implying a desire for wider adoption and testing. Further exploration of the markage trick with other kernel functions or more complex neural coding scenarios could be future directions.

Summary updated

Abstract

The van Rossum metric measures the distance between two spike trains. Measuring a single van Rossum distance between one pair of spike trains is not a computationally expensive task, however, many applications require a matrix of distances between all the spike trains in a set or the calculation of a multi-neuron distance between two populations of spike trains. Moreover, often these calculations need to be repeated for many different parameter values. An algorithm is presented here to render these calculation less computationally expensive, making the complexity linear in the number of spikes rather than quadratic.
BibTeX
@inproceedings{houghton2012efficient,
  author = {Conor Houghton and Thomas Kreuz},
  title = {{On the efficient calculation of van Rossum distances}},
  booktitle = {Network},
  year = {2012},
  doi = {10.3109/0954898x.2012.673048},
}
Figure