{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T23:39:26Z","timestamp":1781134766410,"version":"3.54.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["ERC-2014-CoG 647557"],"award-info":[{"award-number":["ERC-2014-CoG 647557"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"crossref","award":["Wolfson Research Merit"],"award-info":[{"award-number":["Wolfson Research Merit"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Yahoo","award":["Faculty Research Engagement"],"award-info":[{"award-number":["Faculty Research Engagement"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1546141"],"award-info":[{"award-number":["CCF-1546141"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1637536"],"award-info":[{"award-number":["CCF-1637536"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["FT120100307"],"award-info":[{"award-number":["FT120100307"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as <jats:italic>k<\/jats:italic>-center, <jats:italic>k<\/jats:italic>-median, and <jats:italic>k<\/jats:italic>-means. Such algorithms need to be both time and and space efficient. In this paper, we address the problem of <jats:italic>correlation clustering<\/jats:italic> in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on\u00a0<jats:italic>n<\/jats:italic> nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\cdot {{\\,\\mathrm{polylog}\\,}}n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mi>polylog<\/mml:mi>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the \u201cquality\u201d of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. Unfortunately, the standard LP and SDP formulations are not obviously solvable in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\cdot {{\\,\\mathrm{polylog}\\,}}n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mi>polylog<\/mml:mi>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling.<\/jats:p>","DOI":"10.1007\/s00453-021-00816-9","type":"journal-article","created":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T19:02:17Z","timestamp":1615662137000},"page":"1980-2017","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Correlation Clustering in Data Streams"],"prefix":"10.1007","volume":"83","author":[{"given":"Kook Jin","family":"Ahn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0698-0922","authenticated-orcid":false,"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3746-6704","authenticated-orcid":false,"given":"Anthony","family":"Wirth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,3,13]]},"reference":[{"issue":"2","key":"816_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"157","author":"FM Ablayev","year":"1996","unstructured":"Ablayev, F.M.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci. 157(2), 139\u2013159 (1996). https:\/\/doi.org\/10.1016\/0304-3975(95)00157-3","journal-title":"Theor. Comput. Sci."},{"key":"816_CR2","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput. (ICALP 2011 Special Issue) 222, 59\u201379 (2013). https:\/\/doi.org\/10.1016\/j.ic.2012.10.006","DOI":"10.1016\/j.ic.2012.10.006"},{"key":"816_CR3","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S.: Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In: Transactions in Parallel Computing (TOPC), special issue for Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015, vol.\u00a04 (2018). https:\/\/doi.org\/10.1145\/2755573.3154855","DOI":"10.1145\/2755573.3154855"},{"key":"816_CR4","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Symposium on Discrete Algorithms: SODA, pp. 459\u2013467 (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.40","DOI":"10.1137\/1.9781611973099.40"},{"key":"816_CR5","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Principles of Database Systems: PODS, pp. 5\u201314 (2012). https:\/\/doi.org\/10.1145\/2213556.2213560","DOI":"10.1145\/2213556.2213560"},{"key":"816_CR6","doi-asserted-by":"publisher","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5) (2008). https:\/\/doi.org\/10.1145\/1411509.1411513","DOI":"10.1145\/1411509.1411513"},{"key":"816_CR7","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming $$k$$-means approximation. In: Conference on Neural Information Processing Systems: NIPS, pp. 10\u201318 (2009). http:\/\/books.nips.cc\/papers\/files\/nips22\/NIPS2009_1085.pdf"},{"key":"816_CR8","unstructured":"Ailon, N., Karnin, Z.S.: A note on: No need to choose: How to get both a PTAS and sublinear query complexity. CoRR abs\/1204.6588 (2012)"},{"issue":"6","key":"816_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta algorithm and applications. Theory Comput. 8(6), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"816_CR10","doi-asserted-by":"publisher","unstructured":"Arora, S., Kale, S.: A combinatorial, primal-dual approach to semidefinite programs. In: ACM Symposium on Theory of Computing: STOC, pp. 227\u2013236 (2007). https:\/\/doi.org\/10.1145\/1250790.1250823","DOI":"10.1145\/1250790.1250823"},{"key":"816_CR11","unstructured":"Bagon, S., Galun, M.: Large scale correlation clustering optimization. arXiv:1112.2903v1 (2011)"},{"issue":"1\u20133","key":"816_CR12","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\u20133), 89\u2013113 (2004). https:\/\/doi.org\/10.1023\/B:MACH.0000033116.57574.95","journal-title":"Mach. Learn."},{"key":"816_CR13","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating $$s-t$$ minimum cuts in $$\\tilde{O}(n^2)$$ time. In: Symposium on Theory of Computing: STOC, pp. 47\u201355 (1996)","DOI":"10.1145\/237814.237827"},{"key":"816_CR14","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Garcia-Soriano, D., Liberty, E.: Correlation clustering: From theory to practice. In: International Conference on Knowledge Discovery and Data Mining: KDD, pp. 1972. ACM, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2623330.2630808","DOI":"10.1145\/2623330.2630808"},{"key":"816_CR15","doi-asserted-by":"publisher","unstructured":"Braverman, V., Chung, K., Liu, Z., Mitzenmacher, M., Ostrovsky, R.: AMS without 4-wise independence on product domains. In: International Symposium on Theoretical Aspects of Computer Science: STACS, pp. 119\u2013130 (2010). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2449","DOI":"10.4230\/LIPIcs.STACS.2010.2449"},{"issue":"6","key":"816_CR16","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004). https:\/\/doi.org\/10.1137\/S0097539702418498","journal-title":"SIAM J. Comput."},{"issue":"3","key":"816_CR17","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.jcss.2004.10.012","volume":"71","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360\u2013383 (2005). https:\/\/doi.org\/10.1016\/j.jcss.2004.10.012","journal-title":"J. Comput. Syst. Sci."},{"key":"816_CR18","doi-asserted-by":"publisher","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Symposium on Theory of Computing: STOC, pp. 30\u201339 (2003). https:\/\/doi.org\/10.1145\/780542.780548","DOI":"10.1145\/780542.780548"},{"key":"816_CR19","doi-asserted-by":"crossref","unstructured":"Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: Near optimal LP rounding algorithm for correlation clustering on complete and complete $$k$$-partite graphs. In: Symposium on Theory of Computing: STOC (2015)","DOI":"10.1145\/2746539.2746604"},{"key":"816_CR20","doi-asserted-by":"publisher","unstructured":"Chierichetti, F., Dalvi, N.N., Kumar, R.: Correlation clustering in mapreduce. In: International Conference on Knowledge Discovery and Data Mining: KDD, pp. 641\u2013650 (2014). https:\/\/doi.org\/10.1145\/2623330.2623743","DOI":"10.1145\/2623330.2623743"},{"key":"816_CR21","doi-asserted-by":"publisher","unstructured":"Coleman, T., Saunderson, J., Wirth, A.: A local-search 2-approximation for 2-correlation-clustering. In: European Symposium on Algorithms: ESA, pp. 308\u2013319 (2008). https:\/\/doi.org\/10.1007\/978-3-540-87744-8_26","DOI":"10.1007\/978-3-540-87744-8_26"},{"key":"816_CR22","doi-asserted-by":"crossref","unstructured":"Cormode, G., Yi, K.: Small Summaries for Big Data. CUP (2020)","DOI":"10.1017\/9781108769938"},{"issue":"2\u20133","key":"816_CR23","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N.: Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2\u20133), 172\u2013187 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.05.008","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"816_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TKDE.2007.250581","volume":"19","author":"AK Elmagarmid","year":"2006","unstructured":"Elmagarmid, A.K., Ipeirotis, P.G., Verykios, V.S.: Duplicate record detection: a survey. IEEE Trans. Knowl. Data Eng. 19(1), 1\u201316 (2006)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"816_CR25","doi-asserted-by":"crossref","unstructured":"Elsner, M., Schudy, W.: Bounding and comparing methods for correlation clustering beyond ILP. In: Workshop on Integer Linear Programming for Natural Langauge Processing: ILP, pp. 19\u201327. Association for Computational Linguistics, Stroudsburg, PA, USA (2009). http:\/\/www.anthology.aclweb.org\/W\/W09\/W09-1803.pdf","DOI":"10.3115\/1611638.1611641"},{"issue":"2\u20133","key":"816_CR26","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2\u20133), 207\u2013216 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.013","journal-title":"Theor. Comput. Sci."},{"key":"816_CR27","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX k-cut and MAX BISECTION. Algorithmica 18, 67 (1997)","journal-title":"Algorithmica"},{"key":"816_CR28","doi-asserted-by":"publisher","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. In: ACM Symposium on Theory of Computing: STOC, pp. 698\u2013707 (1993). https:\/\/doi.org\/10.1145\/167088.167266","DOI":"10.1145\/167088.167266"},{"issue":"1","key":"816_CR29","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1217299.1217303","volume":"1","author":"A Gionis","year":"2007","unstructured":"Gionis, A., Mannila, H., Tsaparas, P.: Clustering aggregation. ACM Trans. Knowl. Disc. Data (TKDD) 1(1), 4 (2007)","journal-title":"ACM Trans. Knowl. Disc. Data (TKDD)"},{"issue":"1","key":"816_CR30","doi-asserted-by":"publisher","first-page":"249","DOI":"10.4086\/toc.2006.v002a013","volume":"2","author":"I Giotis","year":"2006","unstructured":"Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. Theory Comput. 2(1), 249\u2013266 (2006). https:\/\/doi.org\/10.4086\/toc.2006.v002a013","journal-title":"Theory Comput."},{"key":"816_CR31","unstructured":"Goel, A., Kapralov, M., Post, I.: Single pass sparsification in the streaming model with edge deletions. CoRR abs\/1203.4900 (2012). http:\/\/arxiv.org\/abs\/1203.4900"},{"issue":"4","key":"816_CR32","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373\u2013392 (2005). https:\/\/doi.org\/10.1007\/s00224-004-1178-y","journal-title":"Theory Comput. Syst."},{"issue":"9","key":"816_CR33","doi-asserted-by":"publisher","first-page":"697","DOI":"10.14778\/2732939.2732943","volume":"7","author":"A Gruenheid","year":"2014","unstructured":"Gruenheid, A., Dong, X.L., Srivastava, D.: Incremental record linkage. Proc. VLDB Endow. 7(9), 697\u2013708 (2014)","journal-title":"Proc. VLDB Endow."},{"key":"816_CR34","doi-asserted-by":"publisher","unstructured":"Guha, S.: Tight results for clustering and summarizing data streams. In: International Conference on Database Theory: ICDT, pp. 268\u2013275 (2009). https:\/\/doi.org\/10.1145\/1514894.1514926","DOI":"10.1145\/1514894.1514926"},{"key":"816_CR35","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems (PODS), pp. 241\u2013247 (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"816_CR36","unstructured":"Guha, S., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams. In: IEEE Foundations of Computer Science: FOCS, pp. 359\u2013366 (2000). http:\/\/doi.ieeecomputersociety.org\/10.1109\/SFCS.2000.892124"},{"issue":"1","key":"816_CR37","doi-asserted-by":"publisher","first-page":"1282","DOI":"10.14778\/1687627.1687771","volume":"2","author":"O Hassanzadeh","year":"2009","unstructured":"Hassanzadeh, O., Chiang, F., Lee, H.C., Miller, R.J.: Framework for evaluating clustering algorithms in duplicate detection. Proc. VLDB Endow. 2(1), 1282\u20131293 (2009)","journal-title":"Proc. VLDB Endow."},{"key":"816_CR38","unstructured":"Indyk, P., McGregor, A.: Declaring independence via the sketching of sketches. In: Symposium on Discrete Algorithms: SODA, pp. 737\u2013745 (2008). http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347163"},{"issue":"4","key":"816_CR39","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5(4), 545\u2013557 (1992). https:\/\/doi.org\/10.1137\/0405044","journal-title":"SIAM J. Discrete Math."},{"key":"816_CR40","doi-asserted-by":"publisher","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: On the exact space complexity of sketching and streaming small norms. In: ACM-SIAM Symposium on Discrete Algorithms: SODA, pp. 1161\u20131178 (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.93","DOI":"10.1137\/1.9781611973075.93"},{"key":"816_CR41","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. CoRR abs\/1407.1289 (2014). http:\/\/arxiv.org\/abs\/1407.1289","DOI":"10.1109\/FOCS.2014.66"},{"key":"816_CR42","doi-asserted-by":"publisher","unstructured":"McCutchen, R.M., Khuller, S.: Streaming algorithms for $$k$$-center clustering with outliers and with anonymity. International Workshop on Approximation Algorithms for Combinatorial Optimization: APPROX pp. 165\u2013178 (2008). https:\/\/doi.org\/10.1007\/978-3-540-85363-3_14","DOI":"10.1007\/978-3-540-85363-3_14"},{"issue":"1","key":"816_CR43","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Record 43(1), 9\u201320 (2014). https:\/\/doi.org\/10.1145\/2627692.2627694","journal-title":"SIGMOD Record"},{"key":"816_CR44","unstructured":"Pan, X., Papailiopoulos, D.S., Oymak, S., Recht, B., Ramchandran, K., Jordan, M.I.: Parallel correlation clustering on big graphs. In: Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 82\u201390 (2015). http:\/\/papers.nips.cc\/paper\/5814-parallel-correlation-clustering-on-big-graphs"},{"issue":"1","key":"816_CR45","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1), 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"816_CR46","doi-asserted-by":"publisher","unstructured":"Silva, J.A., Faria, E.R., Barros, R.C., Hruschka, E.R., Carvalho, A.C.P.L.F.d., Gama, J.a.: Data stream clustering: A survey. ACM Comput. Surv 46(1), 13:1-13:31 (2013). https:\/\/doi.org\/10.1145\/2522968.2522981","DOI":"10.1145\/2522968.2522981"},{"key":"816_CR47","doi-asserted-by":"crossref","unstructured":"Steurer, D.: Fast SDP algorithms for constraint satisfaction problems. In: Symposium on Discrete Algorithms: SODA, pp. 684\u2013697 (2010)","DOI":"10.1137\/1.9781611973075.56"},{"key":"816_CR48","doi-asserted-by":"publisher","unstructured":"Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Symposium on Discrete Algorithms: SODA, pp. 526\u2013527 (2004). https:\/\/doi.org\/10.1145\/982792.982866","DOI":"10.1145\/982792.982866"},{"key":"816_CR49","doi-asserted-by":"crossref","unstructured":"Verroios, V., Garcia-Molina, H.: Entity resolution with crowd errors. In: 2015 IEEE 31st International Conference on Data Engineering, pp. 219\u2013230. IEEE (2015)","DOI":"10.1109\/ICDE.2015.7113286"},{"issue":"12","key":"816_CR50","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.14778\/2732977.2732982","volume":"7","author":"N Vesdapunt","year":"2014","unstructured":"Vesdapunt, N., Bellare, K., Dalvi, N.: Crowdsourcing algorithms for entity resolution. Proc. VLDB Endow. 7(12), 1071\u20131082 (2014)","journal-title":"Proc. VLDB Endow."},{"key":"816_CR51","unstructured":"Wirth, A.I.: Approximation algorithms for clustering. Ph.D. thesis, Princeton University (2004). ftp:\/\/ftp.cs.princeton.edu\/reports\/2004\/716.pdf"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00816-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00816-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00816-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T09:07:54Z","timestamp":1624352874000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00816-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,13]]},"references-count":51,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["816"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00816-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,13]]},"assertion":[{"value":"9 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}