In commercial implementations of these recommender systems, the utility and similarity matrices would be far too large to be stored as internal arrays. Amazon, for example, has millions of items for sale and hundreds of millions of customers. With m = 100,000,000 and n = 1,000,000, the utility matrix would have m·n = 100,000,000,000,000 slots and the similarity matrix would have n2 = 1,000,000,000,000 slots. Moreover, if the average customer buys 100 items, then only 100n = 100,000,000 of the entries of the utility matrix would be non-zero—that's only 0.0001 percent of the entries, making it a very sparse matrix.
A sparse matrix is a matrix in which nearly all the entries are zero. Even if possible, it is very inefficient to store such a matrix as a two-dimensional array. In practice, other data structures are used.
There are several data structures that are good candidates for storing sparse matrices. A map is a data structure that implements a mathematical function...