Computer Science > Computational Geometry
[Submitted on 3 Aug 2011 (this version), latest version 15 Sep 2013 (v7)]
Title:Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality
View PDFAbstract:Bregman divergences are important distance measures that are used extensively in data-driven applications such as computer vision, text mining, and speech processing, and are a key focus of interest in machine learning. Answering nearest neighbor (NN) queries under these measures very important in these applications and has been the subject of extensive study, but is problematic because these distance measures lack metric properties like symmetry and the triangle inequality.
In this paper, we present the first approximate nearest-neighbor (ANN) algorithms, which run in polylog(n) time for Bregman divergences of fixed dimension. To do so, we explore two properties of Bregman divergences that are vital to the analysis: a reverse triangle inequality (RTI) and a relaxed triangle inequality called mu-defectiveness. We show that even though Bregman divergences do not satisfy the triangle inequality, the above properties can be utilized to design an efficient search data structure that follows the general two-stage paradigm of a ring-tree decomposition followed by a quad tree search used in previous near-neighbor algorithms for Euclidean space, as well as spaces of bounded doubling dimension.
The resulting algorithm resolves a query for a d-dimensional (1+ eps)-ANN in O((log(n)/eps)^{O(d)}) time and O(n log^{d-1} n) space. We also show that a O(log n) nearest neighbor can be obtained in O(log n) time.
Submission history
From: Amirali Abdullah [view email][v1] Wed, 3 Aug 2011 12:50:09 UTC (75 KB)
[v2] Tue, 28 Feb 2012 18:40:24 UTC (80 KB)
[v3] Wed, 29 Feb 2012 19:38:30 UTC (80 KB)
[v4] Thu, 1 Mar 2012 20:16:53 UTC (105 KB)
[v5] Thu, 12 Apr 2012 11:56:55 UTC (85 KB)
[v6] Tue, 2 Oct 2012 13:27:38 UTC (85 KB)
[v7] Sun, 15 Sep 2013 22:23:33 UTC (435 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.