WarpLDA: a Cache Efficient O(1) Algorithm for Latent Dirichlet
  Allocation
  Developing efficient and scalable algorithms for Latent Dirichlet Allocation
(LDA) is of wide interest for many applications. Previous work has developed an
O(1) Metropolis-Hastings sampling method for each token. However, the
performance is far from being optimal due to random accesses to the parameter
matrices and frequent cache misses.
  In this paper, we first carefully analyze the memory access efficiency of
existing algorithms for LDA by the scope of random access, which is the size of
the memory region in which random accesses fall, within a short period of time.
We then develop WarpLDA, an LDA sampler which achieves both the best O(1) time
complexity per token and the best O(K) scope of random access. Our empirical
results in a wide range of testing conditions demonstrate that WarpLDA is
consistently 5-15x faster than the state-of-the-art Metropolis-Hastings based
LightLDA, and is comparable or faster than the sparsity aware F+LDA. With
WarpLDA, users can learn up to one million topics from hundreds of millions of
documents in a few hours, at an unprecedentedly throughput of 11G tokens per
second.
