Header logo is ei

Efficient Bregman Range Search

2009

Conference Paper

ei


We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence. The range search task is to return all points in a potentially large database that are within some specified distance of a query. It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval. In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks. Here we describe an algorithm for range search for an arbitrary Bregman divergence. This broad class of dissimilarity measures includes the relative entropy, Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences. Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality. We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences.

Author(s): Cayton, L.
Book Title: Advances in Neural Information Processing Systems 22
Journal: Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009
Pages: 243-251
Year: 2009
Day: 0
Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta
Publisher: Curran

Department(s): Empirical Inference
Research Project(s): Optimization and Large Scale Learning
Bibtex Type: Conference Paper (inproceedings)

Event Name: 23rd Annual Conference on Neural Information Processing Systems (NIPS 2009)
Event Place: Vancouver, BC, Canada

Address: Red Hook, NY, USA
Digital: 0
ISBN: 978-1-615-67911-9
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{6860,
  title = {Efficient Bregman Range Search},
  author = {Cayton, L.},
  journal = {Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009},
  booktitle = {Advances in Neural Information Processing Systems 22},
  pages = {243-251},
  editors = {Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta},
  publisher = {Curran},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Red Hook, NY, USA},
  year = {2009}
}