How to store users' similarity

For recommendation, we use user-based recommendation. The problems with this method are that in the early stage of the product, there is no sufficient user's behaviors data. Second, how to store the users' similarity to the relational database is a question. The space complexity of the data will be O(n^2).