Min-wise independent permutations (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Min-wise independent permutations (extended abstract)

Full text

Pdf (163 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 327 - 336

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Andrei Z. Broder	Digital SRC, 130 Lytton Avenue, Palo Alto, CA
Moses Charikar	Computer Science Department, Stanford University, CA
Alan M. Frieze	Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania
Michael Mitzenmacher	Digital SRC, 130 Lytton Avenue, Palo Alto, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 99, Citation Count: 35

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/276698.276781 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	Noga Alon , Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos, Is linear hashing good?, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.465-474, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258639]
	2	N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley and Sons, 1992.
	3	T. M. Apostol. Introduction to Analytic Number Theor3'. Springer-Vefiag, 1976.
	4	Tim Berners-Lee , Robert Cailliau , Ari Luotonen , Henrik Frystyk Nielsen , Arthur Secret, The World-Wide Web, Communications of the ACM, v.37 n.8, p.76-82, Aug. 1994 [doi>10.1145/179606.179671]
	5	A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
	6	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
	7	Andrei Z. Broder , Anna R. Karlin, Multilevel adaptive hashing, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.43-53, January 22-24, 1990, San Francisco, California, United States
	8	J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, Apr. 1979.
	9	Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
	10	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	11	Michael Luby , Avi Wigderson, Pairwise Independence and Derandomization, University of California at Berkeley, Berkeley, CA, 1995
	12	Richard Seltzer , Deborah S. Ray , Eric J. Ray, The AltaVista Revolution: How to Find Anything on the Internet, Osborne/McGraw-Hill, Berkeley, CA, 1996
	13	Robert J. Souza , P. G. Krishnakumar , Cüneyt M. Özveren , Robert J. Simcoe , Barry A. Spinney , Robert E. Thomas , Robert J. Walsh, GIGAswitch system: a high-performance packet-switching platform, Digital Technical Journal, v.6 n.1, p.9-22, Winter 1994

CITED BY 35

	Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
	Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece
	Andrei Z. Broder , Uriel Feige, Min-Wise versus linear independence (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.147-154, January 09-11, 2000, San Francisco, California, United States
	Aristides Gionis , Dimitrios Gunopulos , Nick Koudas, Efficient and tumble similar set retrieval, ACM SIGMOD Record, v.30 n.2, p.247-258, June 2001
	Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States
	Hadas Shachnai , Aravind Srinivasan, Finding large independent sets of hypergraphs in parallel, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.163-168, July 2001, Crete Island, Greece
	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
	Andrei Broder , Monika Henzinger, Algorithmic aspects of information retrieval on the web, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Toshiya Itoh , Yoshinori Takei , Jun Tarui, On the sample size of k-restricted min-wise independent permutations and other k-wise distributions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Toshiya Itoh , Yoshinori Takei , Jun Tarui, On permutations with limited independence, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 09-11, 2000, San Francisco, California, United States
	Zhiyuan Chen , Flip Korn , Nick Koudas , S. Muthukrishnan, Generalized substring selectivity estimation, Journal of Computer and System Sciences, v.66 n.1, p.98-132, 01 February 2003
	Andrei Z. Broder , Moses Charikar , Michael Mitzenmacher, A derandomization using min-wise independent permutations, Journal of Discrete Algorithms, v.1 n.1, p.11-20, February 2003
	Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece
	Piotr Indyk, A small approximately min-wise independent family of hash functions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.454-456, January 17-19, 1999, Baltimore, Maryland, United States
	Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
	Josiane Xavier Parreira , Sebastian Michel , Gerhard Weikum, p2pDating: Real life inspired semantic overlay networks for Web search, Information Processing and Management: an International Journal, v.43 n.3, p.643-664, May, 2007
	Ludmila Cherkasova , Kave Eshghi , Charles B. Morrey , Joseph Tucek , Alistair Veitch, Applying syntactic similarity algorithms for enterprise information management, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Detectives: detecting coalition hit inflation attacks in advertising networks streams, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Sumit Ganguly, Counting distinct items over update streams, Theoretical Computer Science, v.378 n.3, p.211-222, June, 2007
	Gurmeet Singh Manku , Arvind Jain , Anish Das Sarma, Detecting near-duplicates for web crawling, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007
	Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Tracking set-expression cardinalities over continuous update streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.354-369, December 2004
	Navin Goyal , Yury Lifshits , Hinrich Schütze, Disorder inequality: a combinatorial approach to nearest neighbor search, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
	Graham Cormode , Srikanta Tirthapura , Bojian Xu, Time-decaying sketches for sensor data aggregation, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Ping Li, Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 20-22, 2008, San Francisco, California
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Luca Becchetti , Paolo Boldi , Carlos Castillo , Aristides Gionis, Efficient semi-streaming algorithms for local triangle counting in massive graphs, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Wei Dong , Zhe Wang , Moses Charikar , Kai Li, Efficiently matching sets of features with random histograms, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada
	Yury Lifshits , Shengyu Zhang, Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.318-326, January 04-06, 2009, New York, New York
	Itay Dar , Tova Milo , Elad Verbin, Optimized union of non-disjoint distributed data sets, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Noga Alon, Perturbed identity matrices have high rank: Proof and applications, Combinatorics, Probability and Computing, v.18 n.1-2, p.3-15, March 2009
	Lior Aronovich , Ron Asher , Eitan Bachmat , Haim Bitner , Michael Hirsch , Shmuel T. Klein, The design of a similarity based deduplication system, Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, May 04-April 06, 2009, Haifa, Israel
	Graham Cormode , Lukasz Golab , Korn Flip , Andrew McGregor , Divesh Srivastava , Xi Zhang, Estimating the confidence of conditional functional dependencies, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA