{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T17:03:49Z","timestamp":1790010229624,"version":"4.0.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>\n            We present a divide-and-merge methodology for clustering a set of objects that combines a top-down \u201cdivide\u201d phase with a bottom-up \u201cmerge\u201d phase. In contrast, previous algorithms use either top-down or bottom-up methods to construct a hierarchical clustering or produce a flat clustering using local search (e.g.,\n            <jats:italic>k<\/jats:italic>\n            -means). For the divide phase, which produces a tree whose leaves are the elements of the set, we suggest an efficient spectral algorithm. When the data is in the form of a sparse document-term matrix, we show how to modify the algorithm so that it maintains sparsity and runs in linear space. The merge phase quickly finds the optimal partition that respects the tree for many natural objective functions, for example,\n            <jats:italic>k<\/jats:italic>\n            -means, min-diameter, min-sum, correlation clustering, etc. We present a thorough experimental evaluation of the methodology. We describe the implementation of a meta-search engine that uses this methodology to cluster results from web searches. We also give comparative empirical results on several real datasets.\n          <\/jats:p>","DOI":"10.1145\/1189769.1189779","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1499-1525","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["A divide-and-merge methodology for clustering"],"prefix":"10.1145","volume":"31","author":[{"given":"David","family":"Cheng","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ravi","family":"Kannan","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, CT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Grant","family":"Wang","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Cluster Analysis for Applications","author":"Anderberg M.","unstructured":"Anderberg , M. 1973. Cluster Analysis for Applications . Academic Press , New York, NY . Anderberg, M. 1973. Cluster Analysis for Applications. Academic Press, New York, NY."},{"key":"e_1_2_1_2_1","volume-title":"Procedings of the International Conference on Extending Database Technology.","author":"Andritsos P.","unstructured":"Andritsos , P. , Tsaparas , P. , Miller , R. J. , and Sevcik , K. C . 2004. Limbo: Scalable clustering of categorical data . In Procedings of the International Conference on Extending Database Technology. Andritsos, P., Tsaparas, P., Miller, R. J., and Sevcik, K. C. 2004. Limbo: Scalable clustering of categorical data. In Procedings of the International Conference on Extending Database Technology."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. 238--247","author":"Bansal N.","unstructured":"Bansal , N. , Blum , A. , and Chawla , S . 2002. Correlation clustering . In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. 238--247 . Bansal, N., Blum, A., and Chawla, S. 2002. Correlation clustering. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. 238--247."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584888"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775110"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009740529316"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. 524--533","author":"Charikar M.","unstructured":"Charikar , M. , Guruswami , V. , and Wirth , A . 2003. Clustering with qualitative information . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. 524--533 . Charikar, M., Guruswami, V., and Wirth, A. 2003. Clustering with qualitative information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. 524--533."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258657"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/133160.133214"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780550"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 1--13","author":"Demaine E. D.","unstructured":"Demaine , E. D. and Immorlica , N . 2003. Correlation clustering with partial information . In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 1--13 . Demaine, E. D. and Immorlica, N. 2003. Correlation clustering with partial information. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 1--13."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502550"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 11th European Symposium on Algorithms. 208--220","author":"Emanuel D.","unstructured":"Emanuel , D. and Fiat , A . 2003. Correlation clustering---minimizing disagreements on arbitrary weighted graphs . In Proceedings of the 11th European Symposium on Algorithms. 208--220 . Emanuel, D. and Fiat, A. 2003. Correlation clustering---minimizing disagreements on arbitrary weighted graphs. In Proceedings of the 11th European Symposium on Algorithms. 208--220."},{"key":"e_1_2_1_14_1","unstructured":"Golub G. H. and Loan C. F. 1996. Matrix Computations 3rd ed. Johns Hopkins Baltimore MD.   Golub G. H. and Loan C. F. 1996. Matrix Computations 3rd ed. Johns Hopkins Baltimore MD."},{"key":"e_1_2_1_15_1","unstructured":"Golub T. R. Golub leukemia data. http:\/\/www.broad.mit.edu\/cgi-bin\/cancer\/publications\/pub_paper.cgi?mode=view&paper_id=43.  Golub T. R. Golub leukemia data. http:\/\/www.broad.mit.edu\/cgi-bin\/cancer\/publications\/pub_paper.cgi?mode=view&paper_id=43."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.531"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(00)00022-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/540298"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence. 682--687","author":"Hofmann T.","year":"1999","unstructured":"Hofmann , T. 1999 . The cluster-abstraction model: Unsupervised learning of topic hierarchies from text data . In Proceedings of the International Joint Conference on Artificial Intelligence. 682--687 . Hofmann, T. 1999. The cluster-abstraction model: Unsupervised learning of topic hierarchies from text data. In Proceedings of the International Joint Conference on Artificial Intelligence. 682--687."},{"key":"e_1_2_1_20_1","unstructured":"Jain A. and Dubes R. 1988. Algorithms for Clustering Data. Prentice Hall Englewood Cliffs NJ.   Jain A. and Dubes R. 1988. Algorithms for Clustering Data. Prentice Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312186"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 8th International Workshop on AI and Statistics. 261--265","author":"Nickerson A.","unstructured":"Nickerson , A. , Japkowicz , N. , and Milios , E . 2001. Using unsupervised learning to guide re-sampling in imbalanced data sets . In Proceedings of the 8th International Workshop on AI and Statistics. 261--265 . Nickerson, A., Japkowicz, N., and Milios, E. 2001. Using unsupervised learning to guide re-sampling in imbalanced data sets. In Proceedings of the 8th International Workshop on AI and Statistics. 261--265."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792251730"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/345508.345578"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the KDD Workshop on Text Mining.","author":"Steinbach M.","unstructured":"Steinbach , M. , Karypis , G. , and Kumar , V . 2000. A comparison of document clustering techniques . In Proceedings of the KDD Workshop on Text Mining. Steinbach, M., Karypis, G., and Kumar, V. 2000. A comparison of document clustering techniques. In Proceedings of the KDD Workshop on Text Mining."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 519--520","author":"Swamy C.","year":"2004","unstructured":"Swamy , C. 2004 . Correlation clustering: Maximizing agreements via semidefinite programming . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 519--520 . Swamy, C. 2004. Correlation clustering: Maximizing agreements via semidefinite programming. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 519--520."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.96.6.2907"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Society of Optical Engineering. 108--111","author":"Theiler J.","unstructured":"Theiler , J. and Gisler , G . 1997. A contiguity-enhanced k-means clustering algorithm for unsupervised multispectral image segmentation . In Proceedings of the Society of Optical Engineering. 108--111 . Theiler, J. and Gisler, G. 1997. A contiguity-enhanced k-means clustering algorithm for unsupervised multispectral image segmentation. In Proceedings of the Society of Optical Engineering. 108--111."},{"key":"e_1_2_1_35_1","volume-title":"Information Retrieval","author":"Van Rijsbergen C. J.","unstructured":"Van Rijsbergen , C. J. 1979. Information Retrieval , 2 nd ed. Department of Computer Science , University of Glasgow, Glasgow, Scotland. Van Rijsbergen, C. J. 1979. Information Retrieval, 2nd ed. Department of Computer Science, University of Glasgow, Glasgow, Scotland.","edition":"2"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the IEEE International Conference on Information Society in the 21st Century: Emerging Technologies and New Challenges.","author":"Wong W.","unstructured":"Wong , W. and Fu , A . 2000. Incremental document clustering for Web page classification . In Proceedings of the IEEE International Conference on Information Society in the 21st Century: Emerging Technologies and New Challenges. Wong, W. and Fu, A. 2000. Incremental document clustering for Web page classification. In Proceedings of the IEEE International Conference on Information Society in the 21st Century: Emerging Technologies and New Challenges."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. 287--290","author":"Zamir O.","unstructured":"Zamir , O. , Etzioni , O. , Madani , O. , and Karp , R. M . 1997. Fast and intuitive clustering of Web documents . In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. 287--290 . Zamir, O., Etzioni, O., Madani, O., and Karp, R. M. 1997. Fast and intuitive clustering of Web documents. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. 287--290."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Conference on Neural Information Processing Systems. 1057--1064","author":"Zha H.","unstructured":"Zha , H. , Ding , C. , Gu , M. , He , X. , and Simon , H . 2001. Spectral relaxation for k-means clustering . In Proceedings of the Conference on Neural Information Processing Systems. 1057--1064 . Zha, H., Ding, C., Gu, M., He, X., and Simon, H. 2001. Spectral relaxation for k-means clustering. In Proceedings of the Conference on Neural Information Processing Systems. 1057--1064."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584877"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:09:11Z","timestamp":1672261751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189779"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189779","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}