2012 MaximumInnerProductSearchUsingC

• (Ram & Gray, 2012) ⇒ Parikshit Ram, and Alexander G. Gray. (2012). “Maximum Inner-product Search Using Cone Trees.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339677

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Maximum+Inner-product+Search+Using+Cone+Trees
• http://dl.acm.org/citation.cfm?id=2339530.2339677&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithm design and analysis; cone trees; data mining; dual-tree branch-and-bound; metric trees; [[search process; trees

Abstract

The problem of 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. However, the 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 problem and contrast it with the previous problems considered. First, we propose a general branch-and-bound algorithm based on a (single) tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Our proposed branch-and-bound algorithms are based on novel inner-product bounds. Finally we present a new data structure, the cone tree, for increasing the efficiency of the dual-tree algorithm. 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 in some cases.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 MaximumInnerProductSearchUsingC	Parikshit Ram Alexander G. Gray			Maximum Inner-product Search Using Cone Trees				10.1145/2339530.2339677		2012