{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:06:30Z","timestamp":1757617590731,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":42,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819610891"},{"type":"electronic","value":"9789819610907"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_8","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:32:59Z","timestamp":1741105979000},"page":"91-103","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bi-criteria Sublinear Time Algorithms for\u00a0Clustering with\u00a0Outliers in\u00a0High Dimensions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4819-2585","authenticated-orcid":false,"given":"Jiawei","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4524-8507","authenticated-orcid":false,"given":"Wenjie","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1307-6077","authenticated-orcid":false,"given":"Hu","family":"Ding","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Deshpande, A., Kannan, R.: Adaptive sampling for k-means clustering. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 15\u201328. Springer (2009)","key":"8_CR1","DOI":"10.1007\/978-3-642-03685-9_2"},{"unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley (2004)","key":"8_CR2"},{"unstructured":"Arthur, D., Vassilvitskii, S.: K-Means++: the advantages of careful seeding. In: SODA, pp. 1027\u20131035. Society for Industrial and Applied Mathematics (2007)","key":"8_CR3"},{"unstructured":"Ash, J.T., Zhang, C., Krishnamurthy, A., Langford, J., Agarwal, A.: Deep batch active learning by diverse, uncertain gradient lower bounds. In: ICLR (2020)","key":"8_CR4"},{"unstructured":"Awasthi, P., Balcan, M.F.: Center based clustering: a foundational perspective. Handbook of Cluster Analysis (2015)","key":"8_CR5"},{"unstructured":"Bachem, O., Lucic, M., Hassani, S.H., Krause, A.: Fast and provably good seedings for k-means. In: Advances in Neural Information Processing Systems, NIPS\u201916, pp. 55\u201363. Curran Associates Inc., NY, USA (2016)","key":"8_CR6"},{"unstructured":"Bhaskara, A., Vadgama, S., Xu, H.: Greedy sampling for approximate clustering in the presence of outliers. In: NeurIPS, vol.\u00a032. Curran Associates, Inc. (2019)","key":"8_CR7"},{"key":"8_CR8","first-page":"1","volume":"15","author":"P Bhattacharjee","year":"2021","unstructured":"Bhattacharjee, P., Mitra, P.: A survey of density based clustering algorithms. Front. Comp. Sci. 15, 1\u201327 (2021)","journal-title":"Front. Comp. Sci."},{"doi-asserted-by":"crossref","unstructured":"Braverman, V., et al.: The power of uniform sampling for coresets. In: FOCS, pp. 462\u2013473. IEEE (2022)","key":"8_CR9","DOI":"10.1109\/FOCS54457.2022.00051"},{"doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58(3), 11:1\u201311:37 (2011)","key":"8_CR10","DOI":"10.1145\/1970392.1970395"},{"issue":"3","key":"8_CR11","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1541880.1541882","volume":"41","author":"V Chandola","year":"2009","unstructured":"Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: a survey. ACM Comput. Surv. 41(3), 15 (2009)","journal-title":"ACM Comput. Surv."},{"unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: SODA, pp. 642\u2013651. SIAM (2001)","key":"8_CR12"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: STOC, pp. 30\u201339. ACM (2003)","key":"8_CR13","DOI":"10.1145\/780542.780548"},{"doi-asserted-by":"crossref","unstructured":"Chawla, S., Gionis, A.: k-means\u2013: a unified approach to clustering and outlier detection. In: SDM, pp. 189\u2013197. SIAM (2013)","key":"8_CR14","DOI":"10.1137\/1.9781611972832.21"},{"unstructured":"Chen, J., Azer, E.S., Zhang, Q.: A practical algorithm for distributed clustering and outlier detection. In: NeurIPS, pp. 2253\u20132262 (2018)","key":"8_CR15"},{"unstructured":"Chen, K.: A constant factor approximation algorithm for k-median clustering with outliers. In: SODA, pp. 826\u2013835. SIAM (2008)","key":"8_CR16"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Han, L., Xu, D., Xu, Y., Zhang, Y.: k-median\/means with outliers revisited: a simple FPT approximation. In: International Computing and Combinatorics Conference, pp. 295\u2013302. Springer (2023)","key":"8_CR17","DOI":"10.1007\/978-3-031-49193-1_22"},{"issue":"2","key":"8_CR18","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1214\/aos\/1031833664","volume":"25","author":"JA Cuesta-Albertos","year":"1997","unstructured":"Cuesta-Albertos, J.A., Gordaliza, A., Matran, C.: Trimmed k-means: an attempt to Robustify quantizers. Ann. Stat. 25(2), 553\u2013576 (1997)","journal-title":"Ann. Stat."},{"doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time approximation for clustering via random sampling. In: ICALP, pp. 396\u2013407. Springer (2004)","key":"8_CR19","DOI":"10.1007\/978-3-540-27836-8_35"},{"unstructured":"Deshpande, A., Kacham, P., Pratap, R.: Robust k-means++. In: UAI. Proceedings of Machine Learning Research, vol.\u00a0124, pp. 799\u2013808 (2020)","key":"8_CR20"},{"unstructured":"Ding, H.: A sub-linear time framework for geometric optimization with outliers in high dimensions. In: Grandoni, F., Herman, G., Sanders, P. (eds.) ESA (2020)","key":"8_CR21"},{"unstructured":"Ding, H., Wang, Z.: Layered sampling for robust optimization problems. In: ICML, vol.\u00a0119, pp. 2556\u20132566 (2020)","key":"8_CR22"},{"unstructured":"Dua, D., Graff, C.: UCI Machine Learning Repository (2017)","key":"8_CR23"},{"unstructured":"Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: ACM SIGKDD (1996)","key":"8_CR24"},{"doi-asserted-by":"crossref","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: STOC, pp. 569\u2013578. ACM (2011)","key":"8_CR25","DOI":"10.1145\/1993636.1993712"},{"doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Khodamoradi, K., Rezapour, M., Salavatipour, M.R.: Approximation schemes for clustering with outliers. In: SODA, pp. 398\u2013414 (2018)","key":"8_CR26","DOI":"10.1137\/1.9781611975031.27"},{"unstructured":"Georgogiannis, A.: Robust k-means: a theoretical revisit. NIPS (2016)","key":"8_CR27"},{"unstructured":"Grunau, C., Rozho\u0148, V.: Adapting k-means algorithms for outliers. In: International Conference on Machine Learning, pp. 7845\u20137886. PMLR (2022)","key":"8_CR28"},{"unstructured":"Gupta, S.: Approximation algorithms for clustering and facility location problems, Ph.D. thesis, University of Illinois at Urbana-Champaign (2018)","key":"8_CR29"},{"issue":"7","key":"8_CR30","first-page":"757","volume":"10","author":"S Gupta","year":"2017","unstructured":"Gupta, S., Kumar, R., Lu, K., Moseley, B., Vassilvitskii, S.: Local search methods for k-means with outliers. VLDB 10(7), 757\u2013768 (2017)","journal-title":"VLDB"},{"unstructured":"Huang, J., Liu, W., Ding, H.: Is simple uniform sampling effective for center-based clustering with outliers: When and why? arXiv preprint arXiv:2103.00558 (2023)","key":"8_CR31"},{"doi-asserted-by":"crossref","unstructured":"Huang, L., Jiang, S., Li, J., Wu, X.: Epsilon-coresets for clustering (with outliers) in doubling metrics. In: FOCS, pp. 814\u2013825. IEEE (2018)","key":"8_CR32","DOI":"10.1109\/FOCS.2018.00082"},{"unstructured":"Huang, L., Jiang, S.H.C., Lou, J.: The power of uniform sampling for k-median. In: International Conference on Machine Learning. PMLR (2023)","key":"8_CR33"},{"unstructured":"Huang, L., Jiang, S.H.C., Lou, J., Wu, X.: Near-optimal coresets for robust clustering. In: International Conference on Learning Representations. ICLR (2023)","key":"8_CR34"},{"unstructured":"Im, S., Qaem, M.M., Moseley, B., Sun, X., Zhou, R.: Fast noise removal for k-means clustering. In: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics. PMLR (2020)","key":"8_CR35"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: STOC (1999)","key":"8_CR36","DOI":"10.1145\/301250.301366"},{"issue":"8","key":"8_CR37","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"Anil K. Jain","year":"2010","unstructured":"Jain, Anil K..: Data clustering: 50 years beyond k-means. Pattern Recogn. Lett. 31(8), 651\u2013666 (2010). https:\/\/doi.org\/10.1016\/j.patrec.2009.09.011","journal-title":"Pattern Recogn. Lett."},{"doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Li, S., Sandeep, S.: Constant approximation for k-median and k-means with outliers via iterative rounding. In: STOC. ACM (2018)","key":"8_CR38","DOI":"10.1145\/3188745.3188882"},{"issue":"1\u20133","key":"8_CR39","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1023\/B:MACH.0000033114.18632.e0","volume":"56","author":"RR Mettu","year":"2004","unstructured":"Mettu, R.R., Plaxton, C.G.: Optimal time bounds for approximate clustering. Mach. Learn. 56(1\u20133), 35\u201360 (2004)","journal-title":"Mach. Learn."},{"issue":"1\u20133","key":"8_CR40","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1023\/B:MACH.0000033115.78247.f0","volume":"56","author":"A Meyerson","year":"2004","unstructured":"Meyerson, A., O\u2019callaghan, L., Plotkin, S.: A k-median algorithm with running time independent of data size. Mach. Learn. 56(1\u20133), 61\u201387 (2004)","journal-title":"Mach. Learn."},{"unstructured":"Mishra, N., Oblinger, D., Pitt, L.: Sublinear time approximate clustering. In: SODA, pp. 439\u2013447. Society for Industrial and Applied Mathematics (2001)","key":"8_CR41"},{"doi-asserted-by":"crossref","unstructured":"Zhao, Z., Christensen, R., Li, F., Hu, X., Yi, K.: Random sampling over joins revisited. In: International Conference on Management of Data (2018)","key":"8_CR42","DOI":"10.1145\/3183713.3183739"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1090-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T07:01:34Z","timestamp":1757142094000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The research of this work was supported in part by the National Natural Science Foundation of China 62272432, the National Key Research and Development Program of China 2021YFA1000900, and the Natural Science Foundation of Anhui Province 2208085MF163.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interest"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}