Clustering in large graphs and matrices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Clustering in large graphs and matrices

Full text

Pdf (928 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 291 - 299

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

P. Drineas	Computer Science Department, Yale University, New Haven, CT
Alan Frieze	Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA
Ravi Kannan	Computer Science Department, Yale University, New Haven, CT
Santosh Vempala	Department of Mathematics, M.I.T., Cambridge, MA and University of California, Berkeley
V. Vinay	Indian Institute of Science, Bangalore, India

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 98, Citation Count: 35

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P.Agarwal and M.Sharir, Planar geometric location problems, DIMACS 1990.
	2	Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
	3	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	4	Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
	5	Z.Drezner, Facility location : a survey of applications and methods, Springer, 1995.
	6	M.E.Dyer and A.M.Frieze, A simple heuristic for the p-centre problem, Operations Research Letters 3 (1985) 285-288.
	7	B.Everitt, Cluster analysis, published on behalf of the Social Science Research Council by Heinemann Educational Books; New York, Halsted Press, 1980.
	8	Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
	9	G.H.Golub and C.F.Van Loan, Matrix Computations, Johns Hopkins University Press, London, 1989.
	10	David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
	11	D.S.Hochbaum and D.B.Shmoys, A best possible heuristic for the k-center problem, Mathematics o.f Operations Research (1985) 180-184.
	12	M.Jambu and M-O.Lebeaux, Cluster analysis and data analysis, North-Holland, 1983.
	13	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
	14	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
	15	M.Lorr, Cluster analysis for social scientists, Jossey- Bass, 1983.
	16	G.W. Stewart, The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. of Numerical Analysis, Vol. 17, No. 3, June 1980, pp. 403-409.
	17	R.C.Tryon and D.E.Bailey, Cluster analysis, McGraw- Hill, 1970.

CITED BY 35

	Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001
	Jon Kleinberg , Andrew Tomkins, Applications of linear algebra in information retrieval and hypertext analysis, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.185-193, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002
	Leonard J. Schulman, Clustering for edge-cost minimization (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.547-555, May 21-23, 2000, Portland, Oregon, United States
	Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece
	W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Artur Czumaj , Christian Sohler, Soft kinetic data structures, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.865-872, January 07-09, 2001, Washington, D.C., United States
	Ziv Bar-Yossef, Sampling lower bounds via information theory, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Greg Hamerly , Charles Elkan, Alternatives to the k-means algorithm that find better clusterings, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Volker Roth , Julian Laub , Motoaki Kawanabe , Joachim M. Buhmann, Optimal Cluster Preserving Embedding of Nonmetric Proximity Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1540-1551, December 2003
	Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
	Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004
	Sudipto Guha , D. Gunopulos , Nick Koudas, Correlating synchronous and asynchronous data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Santosh Vempala , Grant Wang, A spectral algorithm for learning mixture models, Journal of Computer and System Sciences, v.68 n.4, p.841-860, June 2004
	Jieping Ye, Generalized low rank approximations of matrices, Proceedings of the twenty-first international conference on Machine learning, p.112, July 04-08, 2004, Banff, Alberta, Canada
	Christoph Best , Hans-Christian Hege, Visualizing and Identifying Conformational Ensembles in Molecular Dynamics Trajectories, Computing in Science and Engineering, v.4 n.3, p.68-75, May 2002
	Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Hanson Zhou , David Woodruff, Clustering via matrix powering, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Link analysis ranking: algorithms, theory, and experiments, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.231-297, February 2005
	Panayiotis Tsaparas, Using non-linear dynamical systems for web searching and ranking, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Hui Han , Hongyuan Zha , C. Lee Giles, Name disambiguation in author citations using a K-way spectral clustering method, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA
	Lakshmish Ramaswamy , Bugra Gedik , Ling Liu, A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.9, p.814-829, September 2005
	Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida
	Jieping Ye , Ravi Janardan , Qi Li, GPCA: an efficient dimension reduction scheme for image compression and retrieval, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Jieping Ye, Generalized Low Rank Approximations of Matrices, Machine Learning, v.61 n.1-3, p.167-191, November 2005
	Yogish Sabharwal , Sandeep Sen, A linear time algorithm for approximate 2-means clustering, Computational Geometry: Theory and Applications, v.32 n.2, p.159-172, October 2005
	Alina Beygelzimer , Chang-Shing Perng , Sheng Ma, Fast ordering of large categorical datasets for visualization, Intelligent Data Analysis, v.6 n.4, p.379-395, September 2002
	Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006
	Alina Beygelzimer , Chang-Shing Perng , Sheng Ma, Fast ordering of large categorical datasets for better visualization, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.239-244, August 26-29, 2001, San Francisco, California
	Julian Laub , Volker Roth , Joachim M. Buhmann , Klaus-Robert Müller, On the information and representation of non-Euclidean pairwise data, Pattern Recognition, v.39 n.10, p.1815-1826, October, 2006
	Pasquale De Meo , Giovanni Quattrone , Domenico Ursino, Exploitation of semantic relationships and hierarchical data structures to support a user in his annotation and browsing activities in folksonomies, Information Systems, v.34 n.6, p.511-535, September, 2009
	Petros Drineas , Michael W. Mahoney, On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning, The Journal of Machine Learning Research, 6, p.2153-2175, 12/1/2005
	Dimitris K. Tasoulis , Panagiota Spyridonos , Nicos G. Pavlidis , Vassilis P. Plagianakos , Panagiota Ravazoula , Georgios Nikiforidis , Michael N. Vrahatis, Cell-nuclear data reduction and prognostic model selection in bladder tumor recurrence, Arificial Intelligence in Medicine, v.38 n.3, p.291-303, November, 2006
	Petros Drineas , Ravi Kannan , Michael W. Mahoney, Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms, Random Structures & Algorithms, v.32 n.3, p.307-333, May 2008