{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:37:39Z","timestamp":1791149859662,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2009,6,28]],"date-time":"2009-06-28T00:00:00Z","timestamp":1246147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2009,6,28]]},"DOI":"10.1145\/1557019.1557118","type":"proceedings-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:54Z","timestamp":1246367454000},"page":"907-916","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":320,"title":["Fast approximate spectral clustering"],"prefix":"10.1145","author":[{"given":"Donghui","family":"Yan","sequence":"first","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ling","family":"Huang","sequence":"additional","affiliation":[{"name":"Intel, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael I.","family":"Jordan","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,6,28]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Proceedings of the 18th Annual ACM SIAM Symposium on Discrete algorithms (SODA)","author":"Arthur D.","year":"2007","unstructured":"D. Arthur and S. Vassilvitskii . k-means++: The advantages of careful seeding . In Proceedings of the 18th Annual ACM SIAM Symposium on Discrete algorithms (SODA) , 2007 . D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the 18th Annual ACM SIAM Symposium on Discrete algorithms (SODA), 2007."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_3_2_2_3_1","unstructured":"A. Asuncion and D. Newman. UCI Machine Learning Repository Department of Information and Computer Science. http:\/\/www.ics.uci.edu\/ mlearn\/MLRepository.html 2007.  A. Asuncion and D. Newman. UCI Machine Learning Repository Department of Information and Computer Science. http:\/\/www.ics.uci.edu\/ mlearn\/MLRepository.html 2007."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248618"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"e_1_3_2_2_6_1","volume-title":"Proceedings of the 15th International Conference on Machine Learning (ICML)","author":"Bradley P. S.","year":"1998","unstructured":"P. S. Bradley and U. M. Fayyad . Refining initial points for k-means clustering . In Proceedings of the 15th International Conference on Machine Learning (ICML) , 1998 . P. S. Bradley and U. M. Fayyad. Refining initial points for k-means clustering. In Proceedings of the 15th International Conference on Machine Learning (ICML), 1998."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010933404324"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374452"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1115"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_22"},{"key":"e_1_3_2_2_11_1","first-page":"243","article-title":"Efficient SVM training using low-rank kernel representations","volume":"2","author":"Fine S.","year":"2001","unstructured":"S. Fine and K. Scheinberg . Efficient SVM training using low-rank kernel representations . Journal of Machine Learning Research , 2 : 243 -- 264 , 2001 . S. Fine and K. Scheinberg. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2:243--264, 2001.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262185"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720541"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1314498.1314562"},{"key":"e_1_3_2_2_15_1","volume-title":"Clustering Algorithms","author":"Hartigan J. A.","year":"1975","unstructured":"J. A. Hartigan . Clustering Algorithms . Wiley , New York , 1975 . J. A. Hartigan. Clustering Algorithms. Wiley, New York, 1975."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346830"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224228"},{"key":"e_1_3_2_2_18_1","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Huang L.","year":"2008","unstructured":"L. Huang , D. Yan , M. I. Jordan , and N. Taft . Spectral clustering with perturbed data . In Advances in Neural Information Processing Systems (NIPS) , December 2008 . L. Huang, D. Yan, M. I. Jordan, and N. Taft. Spectral clustering with perturbed data. In Advances in Neural Information Processing Systems (NIPS), December 2008."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1017616"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2007.12.009"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014095614948"},{"key":"e_1_3_2_2_26_1","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Meila M.","year":"2001","unstructured":"M. Meila and J. Shi . Learning segmentation with random walk . In Advances in Neural Information Processing Systems (NIPS) , 2001 . M. Meila and J. Shi. Learning segmentation with random walk. In Advances in Neural Information Processing Systems (NIPS), 2001."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1008381"},{"key":"e_1_3_2_2_28_1","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Ng A. Y.","year":"2002","unstructured":"A. Y. Ng , M. Jordan , and Y. Weiss . On spectral clustering: Analysis and an algorithm . In Advances in Neural Information Processing Systems (NIPS) , 2002 . A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems (NIPS), 2002."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(99)00069-0"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2007.01.001"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_2_32_1","volume-title":"Proceedings of the 17th International Conference on Machine Learning","author":"Smola A.","year":"2000","unstructured":"A. Smola and B. Scholkopf . Sparse greedy matrix approximation for machine learning . In Proceedings of the 17th International Conference on Machine Learning , 2000 . A. Smola and B. Scholkopf. Sparse greedy matrix approximation for machine learning. In Proceedings of the 17th International Conference on Machine Learning, 2000."},{"key":"e_1_3_2_2_33_1","volume-title":"Academic Press","author":"Stewart G.","year":"1973","unstructured":"G. Stewart . Introduction to Matrix Computation . Academic Press , 1973 . G. Stewart. Introduction to Matrix Computation. Academic Press, 1973."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053607000000640"},{"key":"e_1_3_2_2_35_1","volume-title":"Advances in Neural Information Processing Systems","author":"Williams C.","year":"2001","unstructured":"C. Williams and M. Seeger . Using the Nystr\u00f6m method to speed up kernel machines . In Advances in Neural Information Processing Systems , 2001 . C. Williams and M. Seeger. Using the Nystr\u00f6m method to speed up kernel machines. In Advances in Neural Information Processing Systems, 2001."},{"key":"e_1_3_2_2_36_1","volume-title":"Department of Statistics","author":"Yan D.","year":"2009","unstructured":"D. Yan , L. Huang , and M. I. Jordan . Fast approximate spectral clustering. Technical report , Department of Statistics , UC Berkeley , 2009 . D. Yan, L. Huang, and M. I. Jordan. Fast approximate spectral clustering. Technical report, Department of Statistics, UC Berkeley, 2009."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/946247.946658"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056490"}],"event":{"name":"KDD09: The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","location":"Paris France","acronym":"KDD09","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","ACM Association for Computing Machinery"]},"container-title":["Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1557019.1557118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1557019.1557118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:42Z","timestamp":1750253922000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1557019.1557118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,28]]},"references-count":38,"alternative-id":["10.1145\/1557019.1557118","10.1145\/1557019"],"URL":"https:\/\/doi.org\/10.1145\/1557019.1557118","relation":{},"subject":[],"published":{"date-parts":[[2009,6,28]]},"assertion":[{"value":"2009-06-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}