fair comparison, we fixed the computational complexity of both algorithms to be the same (Fig. 1C).
That is, the two approaches were fixed to use the
same number of mathematical operations to generate a hash of length k (i.e., a vector with k nonzero values) for each input (13).
We compared the two algorithms for finding
nearest neighbors in three benchmark data sets:
SIFT (d = 128), GLOVE (d = 300), and MNIST (d =
784) (13). SIFT and MNIST both contain vector
representations of images used for image simi-
larity search, whereas GLOVE contains vector
representations of words used for semantic simi-
larity search. We used a subset of each data set
with 10,000 inputs each, in which each input was
represented as a feature vector in d-dimensional
space. To test performance, we selected 1000 ran-
dom query inputs from the 10,000 and compared
true versus predicted nearest neighbors. That is,
for each query, we found the top 2% (200) of its
true nearest neighbors in input space, deter-
mined on the basis of Euclidean distance be-
tween feature vectors. We then found the top 2%
of predicted nearest neighbors in m-dimensional
hash space, determined on the basis of the Eu-
clidean distance between tags (hashes). We varied
the length of the hash (k) and computed the
overlap between the ranked lists of true and
predicted nearest neighbors by using the mean
average precision (19). We averaged the mean
average precision over 50 trials, in which, for
each trial, the random projection matrices and
the queries changed. We isolated each of the three
differences between the fly algorithm and LSH
to test their individual effect on nearest-neighbors
Fig. 2. Empirical comparison of different random projection types and tag-selection methods. In all plots, the x axis is the length of the hash, and
the y axis is the mean average precision denoting how accurately the true nearest neighbors are found (higher is better). (A) Sparse, binary random
projections offer near-identical performance to that of dense, Gaussian random projections, but the former provide a large savings in computation.
(B) The expanded-dimension (from k to 20k) plus winner-take-all (WTA) sparsification further boosts performance relative to non-expansion. Results are
consistent across all three benchmark data sets. Error bars indicate standard deviation over 50 trials.
Fig. 3. Overall comparison between the fly algorithm and LSH. In all plots, the x axis is the length of the hash, and the y axis is the mean average
precision (higher is better). A 10d expansion was used for the fly. Across all three data sets, the fly’s method outperforms LSH, most prominently for
short hash lengths. Error bars indicate standard deviation over 50 trials.