Database for a trie, or other appropriate structure for recommendation engine We are storing the information about our users showing interest in our items. Based on this information, we would like to create a simple recommendation engine that will take the items I1, I2, I3 etc of the current user, search for all other users that had shown interest in those items, and then output the items I4, I5, I6 etc of the other users, sorted by their decreasing popularity. So, basically, the standard "other buyer were also interested in..." functionality.

I'm asking myself what kind of a database is suitable for a realtime recommendation engine like this. My current idea is to build a trie of item IDs, then sort the item IDs of the current user (as the order of items is irrelevant) and to go down the trie; the children of the last trie node will build the needed output.

The problem is that we have 2 million items so that according to our estimation the trie will have at least 1E12 nodes, so that we probably need a distributed sharded database to store it. Before we reinvent the wheel, are there any ready-to-use databases or generally, non-cloud solutions for recommendation engines out there?
Have a look at Apache Mahout. Last version features also user-item-based recommenders.