{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T08:10:02Z","timestamp":1746000602772,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642380150"},{"type":"electronic","value":"9783642380167"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38016-7_7","type":"book-chapter","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T17:58:58Z","timestamp":1367344738000},"page":"70-81","source":"Crossref","is-referenced-by-count":2,"title":["Probabilistic k-Median Clustering in Data Streams"],"prefix":"10.1007","author":[{"given":"Christiane","family":"Lammersen","sequence":"first","affiliation":[]},{"given":"Melanie","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"7_CR1","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. Journal of the ACM\u00a051(4), 606\u2013635 (2004)","journal-title":"Journal of the ACM"},{"issue":"5","key":"7_CR2","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1109\/TKDE.2008.190","volume":"21","author":"C.C. Aggarwal","year":"2009","unstructured":"Aggarwal, C.C., Yu, P.S.: A survey of uncertain data algorithms and applications. IEEE Transactions on Knowledge and Data Engineering\u00a021(5), 609\u2013623 (2009)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"5","key":"7_CR3","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for euclidean k-medians and related problems. In: Proc. of the 30th STOC, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM Journal on Computing\u00a033(3), 544\u2013562 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. of the 34th STOC, pp. 250\u2013257 (2002)","DOI":"10.1145\/509943.509947"},{"issue":"4","key":"7_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: Static-to-dynamic transformation. Journal of Algorithms\u00a01(4), 301\u2013358 (1980)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"7_CR8","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing\u00a034(4), 803\u2013824 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"7_CR9","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences\u00a065(1), 129\u2013149 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/11731139_24","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"M. Chau","year":"2006","unstructured":"Chau, M., Cheng, R., Kao, B., Ng, J.: Uncertain data mining: An example in clustering location data. In: Ng, W.-K., Kitsuregawa, M., Li, J., Chang, K. (eds.) PAKDD 2006. LNCS (LNAI), vol.\u00a03918, pp. 199\u2013204. Springer, Heidelberg (2006)"},{"issue":"3","key":"7_CR11","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 Journal on Computing\u00a039(3), 923\u2013947 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Cormode, G., McGregor, A.: Approximation algorithms for clustering uncertain data. In: Proc. of the 27th PODS, pp. 191\u2013200 (2008)","DOI":"10.1145\/1376916.1376944"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM\u00a019(2), 248\u2013264 (1972)","journal-title":"Journal of the ACM"},{"key":"7_CR14","unstructured":"Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc. 2nd ACM SIGKDD, pp. 226\u2013231 (1996)"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: Proc. of the 23rd SoCG, pp. 11\u201318 (2007)","DOI":"10.1145\/1247069.1247072"},{"key":"7_CR16","unstructured":"Forgey, E.: Cluster analysis of multivariate data: Efficiency vs. interpretability of classification. Biometrics\u00a0768(21) (1965)"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proc. of the 37th STOC, pp. 209\u2013217 (2005)","DOI":"10.1145\/1060590.1060622"},{"issue":"3","key":"7_CR18","doi-asserted-by":"publisher","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 Transactions on Knowledge and Data Engineering\u00a015(3), 515\u2013528 (2003)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Guha, S., Munagala, K.: Exceeding expectations and clustering uncertain data. In: Proc. of the 28th PODS, pp. 269\u2013278 (2009)","DOI":"10.1145\/1559795.1559836"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"G\u00fcnnemann, S., Kremer, H., Seidl, T.: Subspace clustering for uncertain data. In: Proc. of the SIAM International Conference on Data Mining, pp. 385\u2013396 (2010)","DOI":"10.1137\/1.9781611972801.34"},{"issue":"1","key":"7_CR21","doi-asserted-by":"publisher","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 & Computational Geometry\u00a037(1), 3\u201319 (2007)","journal-title":"Discrete & Computational Geometry"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proc. of the 36th STOC, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"issue":"1","key":"7_CR23","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","volume":"100","author":"D. Haussler","year":"1992","unstructured":"Haussler, D.: Decision theoretic generalizations of the pac model for neural net and other learning applications. Information & Computation\u00a0100(1), 78\u2013150 (1992)","journal-title":"Information & Computation"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: Proc. of the 31st STOC, pp. 428\u2013434 (1999)","DOI":"10.1145\/301250.301366"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proc. of the 34th STOC, pp. 731\u2013740 (2002)","DOI":"10.1145\/510008.510012"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: Proc. of the 40th FOCS, pp. 2\u201313 (1999)","DOI":"10.1109\/SFFCS.1999.814571"},{"issue":"3","key":"7_CR27","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"S.G. Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the euclidean k-median problem. SIAM Journal on Computing\u00a037(3), 757\u2013782 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Kriegel, H.P., Pfeifle, M.: Density-based clustering of uncertain data. In: Proc. of the 11th ACM SIGKDD, pp. 672\u2013677 (2005)","DOI":"10.1145\/1081870.1081955"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Kriegel, H.P., Pfeifle, M.: Hierarchical density-based clustering of uncertain data. In: IEEE International Conference on Data Mining (ICDM), pp. 689\u2013692 (2005)","DOI":"10.1145\/1081870.1081955"},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. Journal of the ACM\u00a057(2) (2010)","DOI":"10.1145\/1667053.1667054"},{"key":"7_CR31","unstructured":"Lammersen, C., Schmidt, M., Sohler, C.: Probabilistic k-median. Tech. rep., Report CGL-TR-02, STREP project Computational Geometric Learning (2011), http:\/\/cgl.uni-jena.de\/pub\/Publications\/WebHome\/CGL-TR-02.pdf"},{"issue":"2","key":"7_CR32","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S.P. Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in pcm. IEEE Transactions on Information Theory\u00a028(2), 129\u2013136 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1-3","key":"7_CR33","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1023\/B:MACH.0000033114.18632.e0","volume":"56","author":"R.R. Mettu","year":"2004","unstructured":"Mettu, R.R., Plaxton, C.G.: Optimal time bounds for approximate clustering. Machine Learning\u00a056(1-3), 35\u201360 (2004)","journal-title":"Machine Learning"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"Ngai, W.K., Kao, B., Chui, C.K., Cheng, R., Chau, M., Yip, K.Y.: Efficient clustering of uncertain data. In: Proc. of the 6th IEEE ICDM, pp. 436\u2013445 (2006)","DOI":"10.1109\/ICDM.2006.63"},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: A metric for distributions with applications to image databases. In: Proc. of the 6th ICCV, pp. 59\u201366 (1998)","DOI":"10.1109\/ICCV.1998.710701"},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"Xu, H., Li, G.: Density-based probabilistic clustering of uncertain data. In: Proc. of the 1st CSSE, vol.\u00a04, pp. 474\u2013477 (2008)","DOI":"10.1109\/CSSE.2008.968"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38016-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T07:35:31Z","timestamp":1745998531000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38016-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642380150","9783642380167"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38016-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}