Item-Item similarity based on text We're build an item-item recommender based on the text descriptions of the items. Our initial approach was to calculate the TF-IDF vectors for each item. We used a hashing tf with 5000 possible hashes for the words. Then approximate all-pairs using a sampling technique (DIMSUM).

We have an mxn matrix where m is the number of words, n is the number of items. The naive approach of calculating all column cosine similarities won't work here since we have n=10^7 m=10^4. 

Our first attempt was using DIMSUM http://stanford.edu/~rezab/papers/dimsum.pdf which is an all-pairs sampling technique. The problem with DIMSUM is it works for data where m >> n. Our matrix is short and wide n>m.

My Question:
What is a good approach for estimating all-pairs similarity of items based on words. Where number of items is 10^7, number of words is 10^4. We only want items pairs above a certain threshold of similarity.

We don't have to do it this way, our task is to recommend a small set of items given one item, we have ways of doing this using collaborative filtering, but we want to also handle new items that we have no user data for so we're trying to find a way to use tf-idf vectors for that case.
There are methods that approximate Jaccard similarity using hash functions, one of them MinHash. They scale well with the number of dimensions and  evaluate similarity of two items. If you want to do nearest neighbor queries (finding similar items given one item) you should look at locality sensitive hashing (LSH), which essentially maps similar items to the same hash value. There is a nice implementation in scikit-learn called LSHForest. It approximates cosine distance and scales well to large number of items and dimensions.