The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
Parallel Spectral Clustering in Distributed Systems
Abstract
Spectral clustering algorithms have been shown to be more effective in finding clusters than some traditional algorithms, such as k-means. However, spectral clustering suffers from a scalability problem in both memory use and computational time when the size of a data set is large. To perform clustering on large data sets, we investigate two representative ways of approximating the dense similarity matrix. We compare one approach by sparsifying the matrix with another by the Nyström method. We then pick the strategy of sparsifying the matrix via retaining nearest neighbors and investigate its parallelization. We parallelize both memory use and computation on distributed computers. Through an empirical study on a document data set of 193,844 instances and a photo data set of 2,121,863, we show that our parallel algorithm can effectively handle large problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Ghemawat, S., Gobioff, H., & Leung, S.-T. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945450 · Cited by 4,984
Combinatorial optimization:Algorithms and complexity
Rabiner, L. (1984) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1984.1164450 · Cited by 3,576
Bigtable: A Distributed Storage System for Structured Data
Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., & Gruber, R. E. (2008) · ACM Transactions on Computer Systems · doi:10.1145/1365815.1365816 · Cited by 3,460
(1999) · Cited by 3,186
Lehoucq, R. B., Sorensen, D. C., & Yang, C. (1998) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719628 · Cited by 2,936
RCV1: A New Benchmark Collection for Text Categorization Research
Lewis, D., Yang, Y., Rose, T. G., & Li, F. (2004) · Goldsmiths (University of London) · doi:10.5555/1005332.1005345 · Cited by 2,503
Self-Tuning Spectral Clustering
Zelnik‐Manor, L., & Perona, P. (2004) · CaltechAUTHORS (California Institute of Technology) · Cited by 1,942
Bigtable: a distributed storage system for structured data
Chang, F. W., Dean, J. B., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., & Gruber, R. E. (2006) · doi:10.5555/1298455.1298475 · Cited by 1,928
Document clustering based on non-negative matrix factorization
Xu, W., Liu, X., & Gong, Y. (2003) · Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval · doi:10.1145/860435.860485 · Cited by 1,860
Introduction to parallel computing
(2004) · Choice Reviews Online · doi:10.5860/choice.42-0990 · Cited by 1,843
Co-clustering documents and words using bipartite spectral graph partitioning
Dhillon, I. S. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502550 · Cited by 1,697
Using the Nyström Method to Speed Up Kernel Machines
Williams, C. K. I., & Seeger, M. (2000) · Cited by 1,646
Ghemawat, S., Gobioff, H., & Leung, S.-T. (2003) · Proceedings of the nineteenth ACM symposium on Operating systems principles · doi:10.1145/945445.945450 · Cited by 1,423
Ghemawat, S., Gobioff, H., & Leung, S.-T. A. (2003) · doi:10.1145/945449.945450 · Cited by 1,347
Spectral grouping using the nystrom method
Fowlkes, C., Belongie, S., Chung, F., & Malik, J. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262185 · Cited by 1,328
Support vector machine active learning for image retrieval
Tong, S., & Chang, E. (2001) · Proceedings of the ninth ACM international conference on Multimedia · doi:10.1145/500141.500159 · Cited by 1,328
Self-citationNew spectral methods for ratio cut partitioning and clustering
Hagen, L., & Kahng, A. B. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.159993 · Cited by 1,288
Map-Reduce for Machine Learning on Multicore
Chu, C.-T., Kim, S. K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A. Y., & Olukotun, K. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0040 · Cited by 1,229
SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems
Hernandez, V., Roman, J. E., & Vidal, V. (2005) · ACM Transactions on Mathematical Software · doi:10.1145/1089014.1089019 · Cited by 1,033
Weighted Graph Cuts without Eigenvectors A Multilevel Approach
Dhillon, I. S., Guan, Y., & Kulis, B. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1115 · Cited by 1,003
Multiclass spectral clustering
Yu, & Shi (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238361 · Cited by 947
Optimization of Collective Communication Operations in MPICH
Thakur, R., Rabenseifner, R., & Gropp, W. (2005) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342005051521 · Cited by 911
A min-max cut algorithm for graph partitioning and data clustering
Ding, C. H. Q., He, X., Zha, H., Gu, M., & Simon, H. D. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989507 · Cited by 829
Satisfying general proximity / similarity queries with metric trees
Uhlmann, J. K. (1991) · Information Processing Letters · doi:10.1016/0020-0190(91)90074-r · Cited by 690
Spectral Relaxation for K-means Clustering
Hongyuan Zha, B., He, X., Ding, C. H. Q., Gu, M., & Simon, H. D. (2001) · Cited by 585
Support vector machine active learning for image retrieval
Tong, S., & Chang, E. (2001) · Proceedings of the ninth ACM international conference on Multimedia - MULTIMEDIA '01 · doi:10.1145/500156.500159 · Cited by 484
Self-citationBach, F. R., & Jordan, M. I. (2003) · Cited by 426
A Data-Clustering Algorithm on Distributed Memory Multiprocessors
Dhillon, I. S., & Modha, D. S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-46502-2_13 · Cited by 386
An Investigation of Practical Approximate Nearest Neighbor Algorithms
Liu, T., Moore, A., Yang, K., & Gray, A. (2004) · Cited by 375
Learning Segmentation by Random Walks
Meilă, M., & Shi, J. (2000) · neural information processing systems · Cited by 365
Improved Nyström low-rank approximation and error analysis
Zhang, K., Tsang, I. W., & Kwok, J. T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390311 · Cited by 299
A Local Learning Approach for Clustering
Wu, M., & Schölkopf, B. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0196 · Cited by 284
Segmentation of 3D meshes through spectral clustering
Liu, R., & Zhang, H. (2004) · 12th Pacific Conference on Computer Graphics and Applications, 2004. PG 2004. Proceedings. · doi:10.1109/pccga.2004.1348360 · Cited by 213
Talwalkar, A., Kumar, S., & Rowley, H. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587670 · Cited by 207
Large-Scale Parallel Data Mining
(2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46502-2 · Cited by 158
Sampling Techniques for Kernel Methods
Achlioptas, D., McSherry, F., & Schölkopf, B. (2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.003.0048 · Cited by 156
Interprocessor collective communication library (InterCom)
Barnett, M., Shuler, L., Geijn, R. A., Gupta, S., Payne, D. G., & Watts, J. (2002) · IEEE Scalable High Performance Computing Conference (SHPCC) · doi:10.1109/shpcc.1994.296665 · Cited by 142
A unified framework for model-based clustering
ZhongShi, & GhoshJoydeep (2003) · Journal of Machine Learning Research · doi:10.5555/945365.964287 · Cited by 126
Song, Y., Chen, W.-Y., Bai, H., Lin, C., & Chang, E. Y. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87481-2_25 · Cited by 83
Self-citationDiscovery of a perceptual distance function for measuring image similarity
Li, B., Chang, E. Y., & Wu, Y. (2003) · Multimedia Systems · doi:10.1007/s00530-002-0069-9 · Cited by 77
Self-citation(2000) · Applied Physics Letters · doi:10.1162/jmlr.2003.4.6.1001 · Cited by 55
A parallel Lanczos method for symmetric generalized eigenvalue problems
Wu, K. J., & Simon, H. D. (1999) · Computing and Visualization in Science · doi:10.1007/s007910050025 · Cited by 36
Observations on the Nyström Method for Gaussian Process Prediction
Williams, C. S. J., Rasmussen, C. E., Scwaighofer, A., et al. (2002) · Cambridge University Engineering Department Publications Database · Cited by 24
Lab., C. (. S. L. B. N., Wu, K., USDOE Office of Science (US), et al. (1999) · doi:10.2172/6539 · Cited by 15
Cited by
A Comprehensive Survey of Clustering Algorithms
Xu, D., & Tian, Y. (2015) · Annals of Data Science · doi:10.1007/s40745-015-0040-1 · Cited by 1,939
A comparative study of efficient initialization methods for the k-means clustering algorithm
Celebi, M. E., Kingravi, H. A., & Vela, P. A. (2013) · Expert Systems with Applications · doi:10.1016/j.eswa.2012.07.021 · Cited by 1,214
Social big data: recent achievements and new challenges
Bello-Orgaz, G., Jung, J. J., & Camacho, D. (2016) · Information Fusion · doi:10.1016/j.inffus.2015.08.005 · Cited by 846
“Some new developments related to traditional clustering algorithms, such as the K-mean [137] , EM [138] , which has been modified to work with the MapReduce paradigm, and more sophisticated approaches based on graph computing (such as spectral clustering), are currently being developed [139] [140] [141] into more effi…”
Learning Deep Representations for Graph Clustering
Tian, F., Gao, B., Cui, Q., Chen, E., & Liu, T.-Y. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8916 · Cited by 657
Large-Scale Multi-View Spectral Clustering via Bipartite Graph
Li, Y., Nie, F., Huang, H., & Huang, J. (2015) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v29i1.9598 · Cited by 585
Metadata
- Authors
- Chen, W.-Y., Song, Y., Bai, H., Lin, C.-J., & Chang, E. Y.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2011-03
- Volume
- 33
- Issue
- 3
- Pages
- 568-586
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- 1939-3539
- OpenAlex
- W2126337883
- Cited by
- 603
- References
- 51
- FWCI
- 35.03
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.