Solution for in Time/Space Complexity challenge in Recommendation System?

Question

I have a book Recommendation System project and have a huge data set of feature vectors. What is the best solution for in memory computation? I mean, the program should:

1. calculate the cosine Similarity among Database Books
2. be REAL TIME, because it's an interactive business site.

I've already thought about big data analysis tools and management such as Spark, Hadoop, ... . However, I am really new to Spark Techs and therefore not sure whether it's practical or not. I am really mixed up how can it be helpful? I have studied spark's documentation in java but it confused me more about how spark can be helpful?

Answer 1

Apache Spark is a great solution for such problems.

But, first let's be clear about the definition of real time processing. It's the type of processing that must guarantee response within specified time which on an interactive business site is actually very low. You can read about those kind of specifications in this answer.

Spark doesn't provide such luxury in predicting under 0.1 sec and I'm citing

Excerpt from Chapter 5 in my book Usability Engineering, from 1993:

• 0.1 second is about the limit for having the user feel that the system is reacting instantaneously, meaning that no special feedback is necessary except to display the result.

Having an interactive business site on which you'd want to display predictions doesn't mean that your predictions has to be in real time.

So the obvious is, actually, the following :

Q: Now that I have computed recommendations for my users, what should I do ?

A: Let's define a serving layer for our systems fast enough to query when recommendations are needed.

It can be anything fast enough to answer your calls e.g Elasticsearch, Solr, HBase, Redis. Whatever flavor suits you.

On other hands, well

Q: I don't want my system to be static, I need to recompute my predictions every T hours/days/etc

A: Spark can do a scheduled job perfectly here. (a simple cron would do)

Q: But when do I retrain my recommender system ?

A: I would say it actually depends on so many stuff a bit too broad to discuss here. You can read about the topic here if you wish.

Ok, so we defined now our batch layer.

Q: And what about data coming in real time, through Kafka, Rabbit, etc. ?

A: This is actually when it can get more complicated, because the method that you'll use to compute distances, approximations, new recommendations will depends on what type of recommender systems you are building and what technologies you are using.

Spark streaming can fit very well to apply "simple" computations on "window" based micro batches. This can be our speed layer.

To conclude, all of the above defines what is called a lambda architecture. And one of the best framework that follows this design is Oryx (personal opinion). It's quite interesting, you ought taking a look at it.

I also believe that it's quite possible to have a RT set-up for a recommendation system without the speed layer.

I hope that this answers your question.

Answer 2

For in-memory computation wouldn't it be simpler to start with Python or R and one of their machine learning libraries? If the data does not fit into RAM, you can load only a part of it (for example, load only p fraction of vectors by loading each vector with probability p at random). Once you analyse your data, and understand which methods work best, you can scale up your system and rewrite your code in one of these distributed computation tools (or perhaps you find that you don't need this at all).

Answer 3

The best solution is not to compute the cosine similarity (in order to recommend an item) but to transform your features so that you can use approximate similarity search, for which many fast options exist. In other words, precalculate to expedite queries. (This means you will have found a co-embedding for your users and items.)