Subquadratic approximation algorithms for clustering problems in high dimensional spaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Subquadratic approximation algorithms for clustering problems in high dimensional spaces

Full text

Pdf (699 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 435 - 444

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Allan Borodin	Computer Science Department, University of Toronto
Rafail Ostrovsky	Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, NJ
Yuval Rabani	Computer Science Department, Technion - IIT, Haifa 32000, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301367 What is a DOI?

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	B. Awerbuch and D. Peleg. Sparse partitions. In Proc. of ~1st FOC$ pp. 503-513, t990.
	2	B. Awerbuch, B. Berger, L. Cowen, and D. Pcleg. Near-linear cost sequental and distributed constructions of sparse neighborhood covers. In Proc. of 3dth FOCS pp. 639-647, 1993.
	3	C. Berge and A. Ghouila-Houri. Programming, Games, and Transportation Networks. John Wiley, 1965.
	4	Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
	5	Edith Cohen , David D. Lewis, Approximating matrix multiplication for pattern recognition tasks, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.682-691, January 05-07, 1997, New Orleans, Louisiana, United States
	6	Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
	7	David Eppstein, Fast hiearchical clustering and other applications of dynamic closet pairs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 25-27, 1998, San Francisco, California, United States
	8	P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
	9	Jacob E. Goodman , Joseph O'Rourke, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	10	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	11	P. Indyk and R. Motwani. Private communication, 1998 (including a complete version of {10}).
	12	W.B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into Hilbert space. Contemporary Mathematics, 26:189-206, 1984.
	13	J. Jaromczyk, and G. Toussaint. Relative neighborhood graphs and their relatives. Proc. IEEE, 90:1502-1517, 1992.
	14	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
	15	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
	16	N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995.
	17	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	18	Joseph O'Rourke , Godfried T. Toussaint, Pattern recognition, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	19	A.C. Yao. On constructing minimum spannning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721-736, November 1982.

CITED BY 11

	Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
	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
	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
	Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Daniele V. Finocchiaro , Marco Pellegrini, On computing the diameter of a point set in high dimensional Euclidean space, Theoretical Computer Science, v.287 n.2, p.501-514, 28 September 2002
	Piotr Indyk, Better algorithms for high-dimensional proximity problems via asymmetric embeddings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	George Kollios , Dimitrios Gunopulos , Nick Koudas , Stefan Berchtold, Efficient Biased Sampling for Approximate Clustering and Outlier Detection in Large Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1170-1187, September 2003
	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States
	Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
	Sanjoy Dasgupta , Philip M. Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences, v.70 n.4, p.555-569, June 2005