maximum inner product tree
Latest commit 7012ad0 Jan 28, 2013 Mark Levy trivial optimisation, refactor a few methods
Failed to load latest commit information.
.gitignore Initial commit Nov 21, 2012 simple implementation Nov 21, 2012 trivial optimisation, refactor a few methods Jan 28, 2013


Maximum Inner Product Tree

Suppose you have a large collection of vectors and a query vector, and you want to find the top few vectors in the collection which have the largest inner products with the query. You can think of this as a nearest neighbour search where the distance measure is the inner product, the catch being that inner product isn't a proper distance metric as it doesn't satisfy the triangle inequality. The MIP Tree is a clever variant of the Ball Tree designed to solve this problem. In practice it can be several orders of magnitude faster than a linear scan over the entire collection.

This is a simple implementation based on P. Ram & A. Gray, Maximum Inner-Product Search using Tree Data-Structures.


The MIP Tree solves the problem of generating recommendations from the user and item factors output by most recent collaborative filtering algorithms.