{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:01:30Z","timestamp":1725879690348},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319530062"},{"type":"electronic","value":"9783319530079"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53007-9_7","type":"book-chapter","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T10:13:23Z","timestamp":1486030403000},"page":"72-82","source":"Crossref","is-referenced-by-count":0,"title":["Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[]},{"given":"Harry","family":"Lang","sequence":"additional","affiliation":[]},{"given":"Keith","family":"Levin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,26]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"B\u0101doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC 2002, pp. 250\u2013257. ACM, New York (2002)","DOI":"10.1145\/509907.509947"},{"issue":"4","key":"7_CR2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I. Static-to-dynamic transformation. J. Algorithms 1(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Braverman, V., Meyerson, A., Ostrovsky, R., Roytman, A., Shindler, M., Tagiku, B.: Streaming k-means on well-clusterable data. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 26\u201340. SIAM (2011)","DOI":"10.1137\/1.9781611973082.3"},{"key":"7_CR4","unstructured":"Bury, M., Schwiegelshohn, C.: Random projections for k-means: maintaining coresets beyond merge & reduce. CoRR, abs\/1504.01584 (2015)"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median, and positive correlation in budgeted optimization. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 737\u2013756. SIAM (2015)","DOI":"10.1137\/1.9781611973730.50"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 30\u201339. ACM, New York (2003)","DOI":"10.1145\/780542.780548"},{"issue":"3","key":"7_CR7","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen, K.: On coresets for $$k$$ k -median and $$k$$ k -means clustering in metric and euclidean spaces and their applications. SIAM J. Comput. 39(3), 923\u2013947 (2009)","journal-title":"SIAM J. Comput."},{"key":"7_CR8","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, STOC 2011, pp. 569\u2013578. ACM, New York (2011)","DOI":"10.1145\/1993636.1993712"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-642-40450-4_41","volume-title":"Algorithms \u2013 ESA 2013","author":"H Fichtenberger","year":"2013","unstructured":"Fichtenberger, H., Gill\u00e9, M., Schmidt, M., Schwiegelshohn, C., Sohler, C.: BICO: BIRCH meets coresets for k-means clustering. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 481\u2013492. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40450-4_41"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Guha, S.: Tight results for clustering and summarizing data streams. In: Proceedings of the 12th International Conference on Database Theory, ICDT 2009, pp. 268\u2013275. ACM, New York (2009)","DOI":"10.1145\/1514894.1514926"},{"issue":"3","key":"7_CR11","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/TKDE.2003.1198387","volume":"15","author":"S Guha","year":"2003","unstructured":"Guha, S., Meyerson, A., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams: theory and practice. IEEE Trans. Knowl. Data Eng. 15(3), 515\u2013528 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"7_CR12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00454-006-1271-x","volume":"37","author":"S Har-Peled","year":"2007","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. Discrete Comput. Geom. 37(1), 3\u201319 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: Coresets for $$k$$ k -means and $$k$$ k -median clustering and their applications. In: STOC 2004, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, p. 426. IEEE Computer Society, Washington, DC (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"7_CR15","first-page":"2375","volume-title":"Advances in Neural Information Processing Systems 24","author":"M Shindler","year":"2011","unstructured":"Shindler, M., Wong, A., Meyerson, A.W.: Fast and accurate k-means for large datasets. In: Shawe-Taylor, J., Zemel, R., Bartlett, P., Pereira, F., Weinberger, K. (eds.) Advances in Neural Information Processing Systems 24, pp. 2375\u20132383. Curran Associates Inc., Red Hook (2011)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53007-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T05:38:38Z","timestamp":1568785118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53007-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319530062","9783319530079"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53007-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}