Maximum inner product search using memory efficient randomized partition trees

Loading...
Thumbnail Image
Issue Date
2016-04-29
Embargo End Date
Authors
Keivani, Omid
Advisor
Sinha, Kaushik
Citation

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

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.

Table of Content
Description
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
publication.page.dc.relation.uri
DOI