{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:31Z","timestamp":1740109291923,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1422591","CCF-1422324"],"award-info":[{"award-number":["IIS-1422591","CCF-1422324"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1547167","CCF-1716400"],"award-info":[{"award-number":["CNS-1547167","CCF-1716400"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1910492"],"award-info":[{"award-number":["IIS-1910492"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s00453-020-00691-w","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T07:04:00Z","timestamp":1583305440000},"page":"2415-2431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Sum Query Algorithm for Distance-Based Locally Dominating Functions"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0492-6380","authenticated-orcid":false,"given":"Ziyun","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"key":"691_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 180\u2013186. SIAM (2009)","DOI":"10.1137\/1.9781611973068.21"},{"key":"691_CR2","unstructured":"Agarwal, P.K., Har-peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Combinatorial and Computational Geometry, MSRI. pp. 1\u201330. University Press (2005)"},{"key":"691_CR3","unstructured":"Andoni, A.: Nearest Neighbor Search: the Old, the New, and the Impossible. PhD thesis, Massachusetts Institute of Technology (2009)"},{"key":"691_CR4","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P., Nguyen, H.L., Razenshteyn, I.: Beyond locality-sensitive hashing. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1018\u20131028. SIAM (2014)","DOI":"10.1137\/1.9781611973402.76"},{"issue":"3","key":"691_CR5","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B Aronov","year":"2008","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"key":"691_CR6","unstructured":"Bach, F., Lacoste-Julien, S., Obozinski, G.: On the equivalence between herding and conditional gradient algorithms. In: Proceedings of the 29th International Conference on International Conference on Machine Learning. pp. 1355\u20131362. Omnipress (2012)"},{"key":"691_CR7","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001","volume-title":"Concentration Inequalities: A Nonasymptotic Theory of Independence","author":"S Boucheron","year":"2013","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013)"},{"key":"691_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Siminelakis, P.: Hashing-Based-Estimators for Kernel Density in High Dimensions. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science. pp. 1032-1043. (2017)","DOI":"10.1109\/FOCS.2017.99"},{"key":"691_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Huang, Z., Liu, Y., Xu, J.: On clustering induced voronoi diagrams. In: Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 390\u2013399. (2013)","DOI":"10.1109\/FOCS.2013.49"},{"issue":"3","key":"691_CR10","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen, K.: On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput. 39(3), 923\u2013947 (2009)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"691_CR11","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1109\/TSP.2016.2628353","volume":"65","author":"EC Cort\u00e9s","year":"2017","unstructured":"Cort\u00e9s, E.C., Scott, C.: Sparse approximation of a kernel mean. IEEE Trans. Signal Process. 65(5), 1310\u20131323 (2017)","journal-title":"IEEE Trans. Signal Process."},{"key":"691_CR12","doi-asserted-by":"crossref","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. pp. 569\u2013578. ACM (2011)","DOI":"10.1145\/1993636.1993712"},{"issue":"1","key":"691_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput. 8(1), 321\u2013350 (2012)","journal-title":"Theory Comput."},{"key":"691_CR14","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. pp. 291\u2013300. ACM (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"691_CR15","unstructured":"Har-Peled, S.: Computing the k nearest-neighbors for all vertices via Dijkstra. Preprint arXiv:1607.07818 (2016)"},{"issue":"301","key":"691_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"691_CR17","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1214\/aoms\/1177704472","volume":"33","author":"E Parzen","year":"1962","unstructured":"Parzen, E.: On estimation of a probability density function and mode. Ann. Math. Stat. 33(3), 1065\u20131076 (1962)","journal-title":"Ann. Math. Stat."},{"key":"691_CR18","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Tai, W.M.: Improved coresets for kernel density estimates. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2718\u20132727. SIAM (2018)","DOI":"10.1137\/1.9781611975031.173"},{"key":"691_CR19","doi-asserted-by":"crossref","unstructured":"Rahul, S., Tao, Y.: Efficient top-k indexing via general reductions. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pp. 277\u2013288. ACM (2016)","DOI":"10.1145\/2902251.2902290"},{"key":"691_CR20","doi-asserted-by":"crossref","unstructured":"Sheng, C., Tao, Y.: Dynamic top-k range reporting in external memory. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems. pp. 121\u2013130. ACM (2012)","DOI":"10.1145\/2213556.2213576"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00691-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00691-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00691-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T00:21:27Z","timestamp":1614817287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00691-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,4]]},"references-count":20,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["691"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00691-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,3,4]]},"assertion":[{"value":"17 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}