Maximum inner product search using memory efficient randomized partition trees
Keivani, Omid. 2016. Maximum inner product search using memory efficient randomized partition trees. --In Proceedings: 12th Annual Symposium on Graduate Research and Scholarly Projects. Wichita, KS: Wichita State University, p. 63
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.
Presented to the 12th Annual Symposium on Graduate Research and Scholarly Projects (GRASP) held at the Heskett Center, Wichita State University, April 29, 2016.
Research completed at Department of Electricial Engineering and Computer Science, College of Engineering