They used CPU for both sparse and dense approach. It would be interesting to see price/performance comparision for dense GPU vs sparse CPU, especially as more specialized architectures for dense matrix operations are coming out
Locality sensitive hash is well known technique for approximate nearest search and dimensions reduction. Combining it with dnn may reduce the complexity of the dataset. But I don't know if in this setting the parameters of the lsh are learnable via backprop?