Sublinear time algorithms for metric space problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sublinear time algorithms for metric space problems

Full text

Pdf (520 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: 428 - 434

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Piotr Indyk

Computer Science Department, Stanford University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 46, Citation Count: 28

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.301366 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	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Subquadratic approximation algorithms for clustering problems in high dimensional spaces, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.435-444, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301367]
	2	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
	3	Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
	4	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
	5	Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276757]
	6	O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
	7	William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	8	D. Gusfield, "Efficient methods for multiple sequence alignments with guaranteed error bounds", Bulletin of Mathematical Biology, 55 (1993), pp. 141-154.
	9	P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.148, November 08-11, 1998
	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	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]
	12	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]
	13	Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
	14	S.R. Kosaraju, J.K. Park, C. Stein, "Long Tours and Short Supers~rings~, FOCS'94.
	15	Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
	16	Jyh-Han Lin , Jeffrey Scott Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, v.44 n.5, p.245-249, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90208-D]
	17	R.L. Rivest, J. Vuillemin, "On recognizing graph properties from adjacency matrices", Theoretical Computer Science 3 (1976), pp. 371-384.
	18	Bang Ye Wu , Giuseppe Lancia , Vineet Bafna , Kun-Mao Chao , R. Ravi , Chuan Yi Tang, A polynomial time approximation scheme for minimum routing cost spanning trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.21-32, January 25-27, 1998, San Francisco, California, United States
	19	R. Wong, "Worst-case Analysis of Network Design Problem Heuristics~,.SIAM J. Alg..Discr. Meth. 1 (1980), pp. 51-63.

CITED BY 28

	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece
	Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
	Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	Mikkel Thorup, Quick and good facility location, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Prosenjit Bose , Anil Maheshwari , Pat Morin, Fast approximations for sums of distances, clustering and the Fermat--Weber problem, Computational Geometry: Theory and Applications, v.24 n.3, p.135-146, April 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
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ramgopal R. Mettu , C. Greg Plaxton, Optimal Time Bounds for Approximate Clustering, Machine Learning, v.56 n.1-3, p.35-60
	Adam Meyerson , Liadan O'Callaghan , Serge Plotkin, A k-Median Algorithm with Running Time Independent of Data Size, Machine Learning, v.56 n.1-3, p.61-87
	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005
	Artur Czumaj , Christian Sohler, Estimating the weight of metric minimum spanning trees in sublinear-time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California
	Ke Chen, On k-Median clustering in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1177-1185, January 22-26, 2006, Miami, Florida
	Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004
	Bernard Chazelle , C. Seshadhri, Online geometric reconstruction, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Dan Feldman , Amos Fiat , Micha Sharir , Danny Segev, Bi-criteria linear-time approximations for generalized k-mean/median/center, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Marco Furini , Filippo Geraci , Manuela Montangero , Marco Pellegrini, VISTO: visual storyboard for web video browsing, Proceedings of the 6th ACM international conference on Image and video retrieval, p.635-642, July 09-11, 2007, Amsterdam, The Netherlands
	Ming Hua , Jian Pei , Ada W. C. Fu , Xuemin Lin , Ho-Fung Leung, Efficiently answering top-k typicality queries on large databases, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Filippo Geraci , Marco Pellegrini, Dynamic user-defined similarity searching in semi-structured text retrieval, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy
	Maria-Florina Balcan , Avrim Blum , Anupam Gupta, Approximate clustering without the approximation, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1068-1077, January 04-06, 2009, New York, New York
	Stephane Durocher , David Kirkpatrick, The projection median of a set of points, Computational Geometry: Theory and Applications, v.42 n.5, p.364-375, July, 2009
	Sergio Cabello , Christian Knauer, Algorithms for graphs of bounded treewidth via orthogonal range searching, Computational Geometry: Theory and Applications, v.42 n.9, p.815-824, November, 2009
	Yuichi Yoshida , Masaki Yamamoto , Hiro Ito, An improved constant-time approximation algorithm for maximum~matchings, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Ming Hua , Jian Pei , Ada W. Fu , Xuemin Lin , Ho-Fung Leung, Top-k typicality queries and efficient query answering methods on large databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.3, p.809-835, June 2009
	Sébastien Bubeck , Ulrike von Luxburg, Nearest Neighbor Clustering: A Baseline Method for Consistent Clustering with Arbitrary Objective Functions, The Journal of Machine Learning Research, 10, p.657-698, June 2009