@cblake: I'm pretty sure I don't. For a tree of size N (power-of-2) I use 2N-1 memory. If it uses more it's a bug. Also AFAIK traditional fenwick trees often use one-based indexing but those requires 2x memory when N is a power of 2.
I agree with the F+tree sentiment, I was a bit confused between both when doing my research, the main benefit the paper provides is a baseline to measure against and related datasets like [https://archive.ics.uci.edu/ml/datasets/Bag+of+Words](https://archive.ics.uci.edu/ml/datasets/Bag+of+Words): up to 140000 unique words and 730M words to parse and get a frequency table from. Here are my research references: [https://github.com/numforge/laser/blob/master/research/random_sampling_optimisation_resources.md](https://github.com/numforge/laser/blob/master/research/random_sampling_optimisation_resources.md). Anyway we can take this in Laser, feel free to open an issue if there are bugs or PR in new research. Unfortunately this will probably take a backseat until I actually have time or refocus on NLP (like a year).
