Maximum Inner-Product Search using Tree Data-structures

Details Maximum Inner-Product Search using Tree Data-structures Maximum Inner-Product Search using Tree Data-structures

2012-02-28

arxiv.org/abs/1202.6101v1

Computer Science

Computational Geometry

Under submission in KDD 2012

Scientific paper

The problem of {\em efficiently} finding the best match for a query in a given set with respect to the Euclidean distance or the cosine similarity has been extensively studied in literature. However, a closely related problem of efficiently finding the best match with respect to the inner product has never been explored in the general setting to the best of our knowledge. In this paper we consider this general problem and contrast it with the existing best-match algorithms. First, we propose a general branch-and-bound algorithm using a tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Finally we present a new data structure for increasing the efficiency of the dual-tree algorithm. These branch-and-bound algorithms involve novel bounds suited for the purpose of best-matching with inner products. We evaluate our proposed algorithms on a variety of data sets from various applications, and exhibit up to five orders of magnitude improvement in query time over the naive search technique.

Affiliated with

Also associated with

No associations

Rating

Maximum Inner-Product Search using Tree Data-structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum Inner-Product Search using Tree Data-structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Inner-Product Search using Tree Data-structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605446