{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:56:11Z","timestamp":1757620571677,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":21,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819502141"},{"type":"electronic","value":"9789819502158"}],"license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"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":[[2026]]},"DOI":"10.1007\/978-981-95-0215-8_16","type":"book-chapter","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T16:25:44Z","timestamp":1753979144000},"page":"206-217","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Framework for\u00a0Clustering with\u00a0Noisy Queries"],"prefix":"10.1007","author":[{"given":"Jinghui","family":"Xia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,1]]},"reference":[{"issue":"177","key":"16_CR1","first-page":"1","volume":"18","author":"E Abbe","year":"2018","unstructured":"Abbe, E.: Community detection and stochastic block models: recent developments. J. Mach. Learn. Res. 18(177), 1\u201386 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Ailon, N., Bhattacharya, A., Jaiswal, R.: Approximate correlation clustering using same-cluster queries. In: Latin American Symposium on Theoretical Informatics, pp. 14\u201327. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-77404-6_2"},{"key":"16_CR3","unstructured":"Ashtiani, H., Kushagra, S., Ben-David, S.: Clustering with same-cluster queries. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, vol.\u00a029, pp. 3216\u20133224. Curran Associates, Inc. (2016)"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"key":"16_CR5","unstructured":"Bressan, M., Cesa-Bianchi, N., Lattanzi, S., Paudice, A.: Exact recovery of mangled clusters with same-cluster queries. In: Proceedings of the 34th International Conference on Neural Information Processing Systems, vol.\u00a033, pp. 9324\u20139334. Curran Associates, Inc. (2020)"},{"key":"16_CR6","unstructured":"Chien, I.E., Pan, C., Milenkovic, O.: Query k-means clustering and the double dixie cup problem. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 6650\u20136659. Curran Associates Inc., Red Hook, NY, USA (2018)"},{"issue":"39","key":"16_CR7","first-page":"1079","volume":"7","author":"E Even-Dar","year":"2006","unstructured":"Even-Dar, E., Mannor, S., Mansour, Y.: Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res. 7(39), 1079\u20131105 (2006)","journal-title":"J. Mach. Learn. Res."},{"issue":"328","key":"16_CR8","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1080\/01621459.1969.10501049","volume":"64","author":"IP Fellegi","year":"1969","unstructured":"Fellegi, I.P., Sunter, A.B.: A theory for record linkage. J. Am. Stat. Assoc. 64(328), 1183\u20131210 (1969)","journal-title":"J. Am. Stat. Assoc."},{"issue":"301","key":"16_CR9","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":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"PW Holland","year":"1983","unstructured":"Holland, P.W., Laskey, K.B., Leinhardt, S.: Stochastic blockmodels: first steps. Soc. Netw. 5(2), 109\u2013137 (1983)","journal-title":"Soc. Netw."},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Mitzenmacher, M., Tsourakakis, C.: Clustering with a faulty oracle. In: Proceedings of the Web Conference 2020, pp. 2831\u20132834. Association for Computing Machinery (2020)","DOI":"10.1145\/3366423.3380045"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web. WWW \u201910, pp. 641\u2013650. Association for Computing Machinery, New York, NY, USA (2010)","DOI":"10.1145\/1772690.1772756"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Li, Y., Song, Y., Zhang, Q.: Learning to cluster via same-cluster queries. In: Proceedings of the 30th ACM International Conference on Information and Knowledge Management, pp. 978\u2013987. Association for Computing Machinery, New York, NY, USA (2021)","DOI":"10.1145\/3459637.3482365"},{"key":"16_CR14","unstructured":"Mazumdar, A., Saha, B.: Clustering with noisy queries. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 5790\u20135801. Curran Associates Inc., Red Hook, NY, USA (2017)"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Mazumdar, A., Saha, B.: A theoretical analysis of first heuristics of crowdsourced entity resolution. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 970\u2013976. AAAI Press (2017)","DOI":"10.1609\/aaai.v31i1.10636"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 529\u2013537. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959929"},{"key":"16_CR17","unstructured":"Mukherjee, C.S., Peng, P., Zhang, J.: Recovering unbalanced communities in the stochastic block model with application to clustering with a faulty oracle. In: Proceedings of the 37th International Conference on Neural Information Processing Systems. NIPS \u201923. Curran Associates Inc., Red Hook, NY, USA (2023)"},{"key":"16_CR18","unstructured":"Peng, P., Zhang, J.: Towards a query-optimal and time-efficient algorithm for clustering with a faulty oracle. In: Proceedings of Thirty Fourth Conference on Learning Theory. Proceedings of Machine Learning Research, vol.\u00a0134, pp. 3662\u20133680. PMLR (2021)"},{"key":"16_CR19","unstructured":"Pia, A.D., Ma, M., Tzamos, C.: Clustering with queries under semi-random noise. In: Proceedings of Thirty Fifth Conference on Learning Theory. Proceedings of Machine Learning Research, vol.\u00a0178, pp. 5278\u20135313. PMLR (2022)"},{"key":"16_CR20","unstructured":"Saha, B., Subramanian, S.: Correlation clustering with same-cluster queries bounded by optimal cost. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0144, pp. 81:1\u201381:17. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019)"},{"key":"16_CR21","unstructured":"Xia, J., Huang, Z.: Optimal clustering with noisy queries via multi-armed bandit. In: Proceedings of the 39th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol.\u00a0162, pp. 24315\u201324331. PMLR (2022)"}],"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-95-0215-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T09:34:50Z","timestamp":1757324090000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0215-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"ISBN":["9789819502141","9789819502158"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0215-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"1 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"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":"Chengdu","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}