{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:36Z","timestamp":1750307016719,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,6,17]],"date-time":"2012-06-17T00:00:00Z","timestamp":1339891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,6,17]]},"DOI":"10.1145\/2261250.2261255","type":"proceedings-article","created":{"date-parts":[[2012,6,20]],"date-time":"2012-06-20T13:33:01Z","timestamp":1340199181000},"page":"31-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximate bregman near neighbors in sublinear time"],"prefix":"10.1145","author":[{"given":"Amirali","family":"Abdullah","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Moeller","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suresh","family":"Venkatasubramanian","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_21"},{"key":"e_1_3_2_1_2_1","volume-title":"ECCC, 2011","author":"Ackermann M.","year":"2011","unstructured":"Ackermann , M. , Blomer , J. , and Scholz , C . Hardness and non-approximability of bregman clustering problems. Tech. rep ., ECCC, 2011 . http:\/\/eccc.hpi-web.de\/report\/ 2011 \/015\/. Ackermann, M., Blomer, J., and Scholz, C. Hardness and non-approximability of bregman clustering problems. Tech. rep., ECCC, 2011. http:\/\/eccc.hpi-web.de\/report\/2011\/015\/."},{"key":"e_1_3_2_1_3_1","first-page":"1088","volume-title":"Proc. 20th SODA","author":"Ackermann M. R.","year":"2009","unstructured":"Ackermann , M. R. , and Blomer , J . Coresets and approximate clustering for {B}regman divergences . In Proc. 20th SODA ( 2009 ), pp. 1088 -- 1097 . Ackermann, M. R., and Blomer, J. Coresets and approximate clustering for {B}regman divergences. In Proc. 20th SODA (2009), pp. 1088--1097."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.58"},{"key":"e_1_3_2_1_5_1","series-title":"e","volume-title":"Methods of Information Geometry","author":"Amari S.","year":"2000","unstructured":"Amari , S. , and Nagaoka , H . Methods of Information Geometry , vol. 191 of e . Translations of Mathematical monographs. Oxford University Press , 2000 . Amari, S., and Nagaoka, H. Methods of Information Geometry, vol. 191 of e. Translations of Mathematical monographs. Oxford University Press, 2000."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1046920.1194902"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9256-1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Bregman L. M. The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming. USSR Computational Mathematics and Mathematical Physics 7. (1967) 200--217.  Bregman L. M. The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming. USSR Computational Mathematics and Mathematical Physics 7. (1967) 200--217.","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390171"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009390"},{"key":"e_1_3_2_1_13_1","volume-title":"COLT '08","author":"Chaudhuri K.","year":"2008","unstructured":"Chaudhuri , K. , and McGregor , A. Finding metric structure in information theoretic clustering . In COLT '08 ( 2008 ). Chaudhuri, K., and McGregor, A. Finding metric structure in information theoretic clustering. In COLT '08 (2008)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013912006537"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/129837"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996454"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064138"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.232083"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAP.1980.1142407"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875592"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1123-0"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.017"},{"key":"e_1_3_2_1_27_1","first-page":"1","volume":"2","author":"Mahalanobis P. C.","year":"1936","unstructured":"Mahalanobis , P. C. On the generalised distance in statistics. Proc. National Institute of Sciences in India 2 , 1 ( 1936 ). 49--55. Mahalanobis, P. C. On the generalised distance in statistics. Proc. National Institute of Sciences in India 2, 1 (1936). 49--55.","journal-title":"Proc. National Institute of Sciences in India"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_103"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10044-007-0076-8"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2159046"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.007"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2018176"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1109\/ICME.2009.5202635","volume-title":"Proceedings of the 2009 IEEE international conference on Multimedia and Expo (Piscataway","author":"Nielsen F.","year":"2009","unstructured":"Nielsen , F. , Piro , P. , and Barlaud , M . Bregman vantage point trees for efficient nearest neighbor queries . In Proceedings of the 2009 IEEE international conference on Multimedia and Expo (Piscataway , NJ, USA , 2009 ), ICME'09, IEEE Press . pp. 878 -- 881 . Nielsen, F., Piro, P., and Barlaud, M. Bregman vantage point trees for efficient nearest neighbor queries. In Proceedings of the 2009 IEEE international conference on Multimedia and Expo (Piscataway, NJ, USA, 2009), ICME'09, IEEE Press. pp. 878--881."},{"key":"e_1_3_2_1_34_1","volume-title":"In European Workshop on Computational Geometry","author":"Nielsen F.","year":"2009","unstructured":"Nielsen , F. , Piro , P. , and Barlaud , M . Tailored bregman ball trees for effective nearest neighbors . In In European Workshop on Computational Geometry ( 2009 ). Nielsen, F., Piro, P., and Barlaud, M. Tailored bregman ball trees for effective nearest neighbors. In In European Workshop on Computational Geometry (2009)."},{"key":"e_1_3_2_1_35_1","volume-title":"AMS","author":"Sariel-Har-Peled","year":"2011","unstructured":"Sariel-Har-Peled . Geometric Approximation Algorithms . AMS , 2011 . http:\/\/goo.gl\/pLiEO. Sariel-Har-Peled. Geometric Approximation Algorithms. AMS, 2011. http:\/\/goo.gl\/pLiEO."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11526346_18"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687630"}],"event":{"name":"SoCG '12: Symposium on Computational Geometry 2012","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chapel Hill North Carolina USA","acronym":"SoCG '12"},"container-title":["Proceedings of the twenty-eighth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2261250.2261255","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2261250.2261255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:08Z","timestamp":1750236548000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2261250.2261255"}},"subtitle":["beyond the triangle inequality"],"short-title":[],"issued":{"date-parts":[[2012,6,17]]},"references-count":36,"alternative-id":["10.1145\/2261250.2261255","10.1145\/2261250"],"URL":"https:\/\/doi.org\/10.1145\/2261250.2261255","relation":{},"subject":[],"published":{"date-parts":[[2012,6,17]]},"assertion":[{"value":"2012-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}