{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:15:03Z","timestamp":1759133703392},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            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\n            <jats:italic>Bregman Divergence<\/jats:italic>\n            [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\n            <jats:italic>extended<\/jats:italic>\n            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\n            <jats:italic>extended space<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687630","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"13-24","source":"Crossref","is-referenced-by-count":23,"title":["Similarity search on Bregman divergence"],"prefix":"10.14778","volume":"2","author":[{"given":"Zhenjie","family":"Zhang","sequence":"first","affiliation":[{"name":"National U. of Singapore"}]},{"given":"Beng Chin","family":"Ooi","sequence":"additional","affiliation":[{"name":"National U. of Singapore"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"Ohio State University"}]},{"given":"Anthony K. H.","family":"Tung","sequence":"additional","affiliation":[{"name":"National U. of Singapore"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1046920.1194902"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2007.383241"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390171"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190700"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354820"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/946247.946585"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1980.1163421"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_14_1","first-page":"36","article-title":"A statistical method for estimation of speech spectral density and formant frequencies","volume":"53","author":"Itakura F.","year":"1970","unstructured":"F. Itakura and S. Saito . A statistical method for estimation of speech spectral density and formant frequencies . Electronics and Communications in Japan , 53 : 36 -- 43 , 1970 . F. Itakura and S. Saito. A statistical method for estimation of speech spectral density and formant frequencies. Electronics and Communications in Japan, 53:36--43, 1970.","journal-title":"Electronics and Communications in Japan"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143908"},{"key":"e_1_2_1_17_1","first-page":"578","volume-title":"AAAI","author":"Long B.","year":"2007","unstructured":"B. Long , Z. M. Zhang , and P. S. Yu . Graph partitioning based on link distributions . In AAAI , pages 578 -- 583 , 2007 . B. Long, Z. M. Zhang, and P. S. Yu. Graph partitioning based on link distributions. In AAAI, pages 578--583, 2007."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471721182"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137931"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.3115\/981574.981598"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/850924.851528"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2007.900138"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066303"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2008.921853"},{"key":"e_1_2_1_25_1","first-page":"631","volume-title":"VLDB","author":"Tung A. K. H.","year":"2006","unstructured":"A. K. H. Tung , R. Zhang , N. Koudas , and B. C. Ooi . Similarity search: A matching based approach . In VLDB , pages 631 -- 642 , 2006 . A. K. H. Tung, R. Zhang, N. Koudas, and B. C. Ooi. Similarity search: A matching based approach. In VLDB, pages 631--642, 2006."},{"key":"e_1_2_1_26_1","first-page":"194","volume-title":"VLDB","author":"Weber R.","year":"1998","unstructured":"R. Weber , H.-J. Schek , and S. Blott . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In VLDB , pages 194 -- 205 , 1998 . R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, pages 194--205, 1998."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:22:53Z","timestamp":1672226573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687630"}},"subtitle":["towards non-metric indexing"],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687630"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687630","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}