Bregman Hyperplane Trees for Fast Approximate Nearest Neighbor Search

Bregman Hyperplane Trees for Fast Approximate Nearest Neighbor Search

Bilegsaikhan Naidan (Department of Computer and Information Science, Norwegian University of Science and Technology, Trondheim, Norway) and Magnus Lie Hetland (Department of Computer and Information Science, Norwegian University of Science and Technology, Trondheim, Norway)
DOI: 10.4018/jmdem.2012100104

Abstract

This article presents a new approximate index structure, the Bregman hyperplane tree, for indexing the Bregman divergence, aiming to decrease the number of distance computations required at query processing time, by sacrificing some accuracy in the result. The experimental results on various high-dimensional data sets demonstrate that the proposed index structure performs comparably to the state-of-the-art Bregman ball tree in terms of search performance and result quality. Moreover, this method results in a speedup of well over an order of magnitude for index construction. The authors also apply their space partitioning principle to the Bregman ball tree and obtain a new index structure for exact nearest neighbor search that is faster to build and a slightly slower at query processing than the original.
Article Preview
Top

2. Preliminaries

Let jmdem.2012100104.m01 be our database of vectors. Let jmdem.2012100104.m02 be a strictly convex differentiable function. The Bregman divergence (Bregman, 1967) between jmdem.2012100104.m03 based on jmdem.2012100104.m04 is defined as:

jmdem.2012100104.m05
(1)

Here, jmdem.2012100104.m06 denotes the gradient of the function jmdem.2012100104.m07at jmdem.2012100104.m08 and jmdem.2012100104.m09 denotes the dot product between jmdem.2012100104.m10 and jmdem.2012100104.m11. In other words, a Bregman divergence measures the distance between jmdem.2012100104.m12 and its first-order Taylor expansion. The definition is illustrated in Figure 1.

Figure 1.

Illustration of the Bregman divergence jmdem.2012100104.m13

jmdem.2012100104.f01

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing