Bregman Hyperplane Trees for Fast Approximate Nearest Neighbor Search

Bilegsaikhan Naidan and Magnus Lie Hetland
Additional contact information
Bilegsaikhan Naidan: Department of Computer and Information Science, Norwegian University of Science and Technology, Trondheim, Norway
Magnus Lie Hetland: Department of Computer and Information Science, Norwegian University of Science and Technology, Trondheim, Norway

International Journal of Multimedia Data Engineering and Management (IJMDEM), 2012, vol. 3, issue 4, 75-87

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.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/jmdem.2012100104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jmdem0:v:3:y:2012:i:4:p:75-87

Access Statistics for this article

International Journal of Multimedia Data Engineering and Management (IJMDEM) is currently edited by Chengcui Zhang

More articles in International Journal of Multimedia Data Engineering and Management (IJMDEM) from IGI Global
Bibliographic data for series maintained by Journal Editor ().