Please use this identifier to cite or link to this item:
Title: Similarity search on bregman divergence: Towards non-metric indexing
Authors: Zhang, Z. 
Ooi, B.C. 
Parthasarathy, S.
Tung, A.K.H 
Issue Date: 2009
Citation: Zhang, Z.,Ooi, B.C.,Parthasarathy, S.,Tung, A.K.H (2009). Similarity search on bregman divergence: Towards non-metric indexing. Proceedings of the VLDB Endowment 2 (1) : 13-24. ScholarBank@NUS Repository.
Abstract: In this paper, we examine the problem of indexing over non-metric distance functions. In particular, we focus on a general class of distance functions, namely Bregman Di-vergence [6], to support nearest neighbor and range queries. Distance functions such as KL-divergence and Itakura-Saito distance, are special cases of Bregman divergence, with wide applications in statistics, speech recognition and time series analysis among others. Unlike in metric spaces, key properties such as triangle inequality and distance symmetry do not hold for such distance functions. A direct adaptation of existing indexing infrastructure developed for metric spaces is thus not possible. We devise a novel solution to handle this class of distance measures by expanding and mapping points in the original space to a new extended space. Subsequently, we show how state-of-the-art tree-based indexing methods, for low to moderate dimensional datasets, and vector approximation file (VA-file) methods, for high dimensional datasets, can be adapted on this extended space to answer such queries efficiently. Improved distance bounding techniques and distribution-based index optimization are also introduced to improve the performance of query answering and index construction respectively, which can be applied on both the R-trees and VA files. Extensive experiments are conducted to validate our approach on a variety of datasets and a range of Bregman divergence functions. © 2009 VLDB Endowment.
Source Title: Proceedings of the VLDB Endowment
ISSN: 21508097
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Sep 9, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.