x1 * a + x2 * b + x3 * c + ... + x1000 * zzz + ...
If a, b, c ... zzz, are all fixed constants already discovered by your learning algorithm. That's a very fast calculation, and doesn't take anything like 50ms.
Also, in the real world, you can establish a significance cutoff for a lot of these constants and get something like this as your final equation:
x13 * m + x523 * cdf + x777 * wdc + x893 * ydz
And the learning side of things should have culled that list of thousand features down to a list of 5 - 10 that mattered.
It really sounds like the off-the-shelf stuff isn't built for efficiency.
The team behind the paper built a model that had good performance on training data. They're a smart lot so they knew they needed to cross-validate. The results held up in cross-validation! Hooray, the model works! ...right?
That's as far as a lot of data scientists go. This paper points out that you need to have a model that does (at least) three things: 1. Generates good scores with training and testing data 2. Outperforms existing models in the real world 3. Runs really really quickly There are a lot of data scientists who have no idea how to do #2 and #3. This paper says "These parts are really important!!!"
Features likely include more than just the single users history, so they need to be updated often enough for the model to do fast predictions. E.g. you want your model to capture if many people are booking from the same area at once because there were results from a sports game etc, but you dont want to run an expensive query for every user of the page.
Definitely not the first thing to worry about in a startup, but better performance at Booking.com's scale is serious $$$.