In this paper, we mine and learn to predict how similar a pair of users’ interests towards videos are, based on demographic, social and interest information of these users. We use the video access patterns of active users as ground truth. We adopt tag-based user profiling to establish this ground truth. We then show the effectiveness of the different features, and their combinations and derivatives, in predicting user interest similarity, based on different machine-learning methods for combining multiple features. We propose a hybrid tree-encoded linear model for combining the features, and show that it out-performs other linear and tree-based models. Our methods can be used to predict user interest similarity when the ground-truth is not available, e.g. for new users, or inactive users whose interests may have changed from old access data, and is useful for video recommendation.