Maximum inner product search using memory efficient randomized partition trees

Abstract

Finding the maximum inner product is a well-known problem and it has been used in many applications such as recommender systems. It is also known that this problem can be converted to a nearest neighbor problem using various transformations. Local sensitivity hashing (LSH) is the most used algorithm for this purpose, but it has some disadvantages (e.g. many parameters should be fixed initially and there is no optimal way to fix them). In this paper we use an existing method called Random projection tree (RPT) and also propose two space efficient versions of it at nearly no additional cost. Moreover, we prove what the best transformation for RPT is. Finally, we test our method on many real world datasets such as Movielens and Netflix. The results connote that with the same amount of computations (even less), RPT have higher accuracy than LSH.