Mark S. Manasse

Work Mark S. Manasse photo Home
Salesforce.com
One Market Street, Landmark Building
San Francisco, CA 94125
+1 415 589 3263 (Voice)
+1 415 361 8514 (Mobile)
1270 Monterey Blvd.
San Francisco, CA 94127
+1 415 585 4263 (Voice)
+1 415 370 5714 (Mobile)
+1 270 682 7535 (Fax)
msm@std.org

Objective

I hope to continue doing what I like best: attempting to maintain perspective on research in computer science and the industry, and from that perspective, selecting high-impact problems amenable to solutions requiring more thinking than typing. Not that I refuse to or don't code, but I view my talents more in code obviation by finding hidden cross-disciplinary connections that allow some topological or graph-theory identity to substitute a formula for a search.

Employment

December 2014 - present   salesforce.com
San Francisco, California
Principal Architect, Infrastructure Security
2001 - November 2014   Microsoft Research - Silicon Valley
Mountain View, California
Principal Researcher
1985 - 2001   Systems Research Center, Compaq Computer Corporation
(Digital Equipment Corporation, 1985 - 1998)

Palo Alto, California
Principal Member of Technical Staff
1984   Department of Computer Science, University of Chicago
Chicago, Illinois
Visiting Assistant Professor
1982 - 1985   Computing Science Research Center, Bell Laboratories
Murray Hill, New Jersey
Member of Technical Staff

Education

 
1978 - 1982   University of Wisconsin
Madison, Wisconsin
Ph.D. in Mathematical Logic, 1982, M.S. in Computer Science, 1981
M.A. in Mathematics, 1979
1975 - 1978   Harvard College
Cambridge, Massachusetts
A.B. cum laude in Mathematics, 1978

Professional experience

I've worked on a wide variety of areas in computer science, and continue to look for systems problems where mathematical and theoretical techniques might be applied judiciously. Some previous successes have included: multiprocessor memory architectures, which led to work on competitive algorithms; window systems, which led to work on methodologies for concurrent programming, and to the studies behind low-bandwidth X; distributed computing, which afforded the opportunity to work on integer factorization; and, most recently, the Web, which has led to investigations into cryptographic protocols for exchanging very small quantities of money (the MilliCent project), and techniques and applications for discovering syntactic similarity among large collections of documents and applications for measuring the rate of evolution of web pages.

My most recent efforts have been focused on completing a long-standing but intermittent research agenda into similarity detection begun with Alta Vista, refreshed with Bing, and repurposed for network compression in the Windows Server distributed file system, the publication in 2012 of a textbook summarizing the above and advances designed to address deficiencies therein, and this year's work improving the performance by two orders of magnitude by employing techniques first found by Flajolet and Martin.

I have also been recently considering erasure coding techniques for extending the usable lifetime of emerging non-volatile memory technologies when used to replace DRAM. Additionally, I have been working on a data-mining project to detect urgency in the trail of browsing and search queries made by a user (often from a smart phone) to detect when an emergency medical situation might suggest a more streamlined and tailored search experience to quickly help a bystander learn how to perform basic CPR, say, while awaiting arrival of the emergency medical services whose summoning was assisted by the phone upon detection of the user's state of distress.

Recent and selected older publications

At Microsoft, I made investigations into applications of cryptography for spam reduction, into petabyte-scale reliable storage, into web evolution and the connection to web spam.

Bernhard Haeupler, Mark Manasse, Kunal Talwar. Consistent Weighted Sampling Made Fast, Small, and Easy. Unpublished: arXiv:1410.4266 [cs.DS].

Omar Alonso, Dennis Fetterly, and Mark Manasse. Duplicate News Story Detection Revisited. The Ninth Asia Information Retrieval Societies Conference, Springer Verlag, 9 December 2013.

Rodolfo Azevedo, John Davis, Karin Strauss, Parikshit Gopalan, Mark Manasse, and Sergey Yekhanin. Zombie Memory: Extending Memory Lifetime by Reviving Dead Blocks. 40th International Symposium on Computer Architecture, ACM, 27 June 2013.

Omar Alonso, Dennis Fetterly, and Mark Manasse. Duplicate News Story Detection Revisited. No. MSR-TR-2013-60, May 2013.

John D. Davis, Karin Strauss, Parikshit Gopalan, Mark Manasse, and Sergey Yekhanin. Supplement to Zombie Memory: Extending Memory Lifetime by Reviving Dead Blocks. No. MSR-TR-2013-47, April 2013.

Mark S. Manasse. My publisher insists on my not just giving open access to my book, so mail me to request a link, or shop for On the Efficient Determination of Most Near Neighbors: Horseshoes, Hand Grenades, Web Search and Other Situations When Close is Close Enough. Morgan & Claypool, 19 November 2012, second edition ISBN 9781627058087.

Mark Manasse, Frank McSherry, and Kunal Talwar. Consistent Weighted Sampling. no. MSR-TR-2010-73, June 2010.

Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. Design Tradeoffs for SSD Performance. Proceedings of the 2008 USENIX Technical Conference (USENIX'08), USENIX, June 2008.

Dan Teodosiu, Nikolaj Bjorner, Joe Porkka, Mark Manasse, and Y. Gurevich. Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression. No. MSR-TR-2006-157, November 2006.

Alexandros Ntoulas, Marc Najork, Mark Manasse, and Dennis Fetterly. Detecting Spam Web Pages Through Content Analysis. 15th International World Wide Web Conference (WWW), Association for Computing Machinery, Inc., Edinburgh, Scotland, May 2006.

Úlfar Erlingsson, Mark Manasse, and Frank McSherry. A cool and practical alternative to traditional hash tables. 7th Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, January 2006.

Dennis Fetterly, Mark Manasse, and Marc Najork. Detecting Phrase-Level Duplication on the World Wide Web. 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), Association for Computing Machinery, Inc., Salvador, Brazil, August 2005.

Martín Abadi, Mike Burrows, Mark Manasse, and Ted Wobber. Moderately Hard, Memory-bound Functions. ACM Transactions on Internet Technology, vol. 5, no. 2, pp. 299-327, Association for Computing Machinery, Inc., May 2005.

Mark Manasse, Danny Sleator, Victor K. Wei, and Nick Baxter. The Panex Puzzle. A Tribute to a Mathemagician, pp. 145-162, A. K. Peters, November 2004.

Dennis Fetterly, Mark Manasse, and Marc Najork. On the Evolution of Clusters of Near-Duplicate Web Pages. Journal of Web Engineering, vol. 2, no. 4, pp. 228-246, Institute of Electrical and Electronics Engineers, Inc., October 2004.

Dennis Fetterly, Mark Manasse, and Marc Najork. Spam, Damn Spam, and Statistics: Using statistical analysis to locate spam web pages. 7th International Workshop on the Web and Databases (WebDB), Association for Computing Machinery, Inc., June 2004.

Dennis Fetterly, Mark Manasse, Marc Najork, and Janet Wiener. A Large-Scale Study of the Evolution of Web Pages. Software: Practice & Experience, vol. 34, no. 2, pp. 213-237, Wiley, February 2004.

Dennis Fetterly, Mark Manasse, and Marc Najork. On the Evolution of Clusters of Near-Duplicate Web Pages. Proceedings of the 1st Latin American Web Congress (LA-WEB), IEEE Computer Society, Washington, DC, USA, November 2003.

Dennis Fetterly, Mark Manasse, Marc Najork, and Janet Wiener. A large-scale study of the evolution of web pages. Proceedings of the 12th International World Wide Web Conference (WWW), ACM, New York, NY, USA, May 2003.

Martín Abadi, Mike Burrows, Mark Manasse, and Ted Wobber. Moderately Hard, Memory-bound Functions. Proceedings of the 10th Annual Network and Distributed System Security Symposium (NDSS), Internet Society, February 2003.

Mark Manasse. Why Rights Management is Wrong (and What to Do Instead). Presented at the World Wide Web Consortium's workshop on digital rights management. Sophia-Antipolis, January 2001. (Also appeared as SRC Technical Note 2001-002.)

Andrei Broder, Mark Manasse, and Jim Saxe. Hypercube Routing with Limited Interconnections. SRC Technical Note 2000-001.

Steve Glassman, Mark Manasse, and Jeff Mogul. Y10K and Beyond. IETF RFC No. 2550, April 1999.

Andrei Broder, Steve Glassman, Mark Manasse, and Geoffrey Zweig. Syntactic clustering of the Web. Proceedings of the Sixth International World Wide Web Conference, pages 391-404. April 1997. (Also appeared as SRC Technical Note 1997-015.)

Steve Glassman, Mark Manasse, Martín Abadi, Paul Gauthier, and Patrick Sobalvarro. The Millicent protocol for inexpensive electronic commerce. In World Wide Web Journal, Fourth International World Wide Web Conference Proceedings, pages 603-618. O'Reilly, December 1995.

Mark Manasse. The Millicent protocols for electronic commerce. In Proceedings of the First USENIX workshop on electronic commerce, New York, August 1995.

Peter K. Rathmann, Marianne Winslett, and Mark Manasse. Circumscription with homomorphisms: Solving the Equality and Counterexample Problems. Journal of the A.C.M., 41(5):819-873, 1994.

Hania Gajewska, James J. Kistler, Mark Manasse, and Dave Redell. Argo: A system for distributed collaboration. In Proceedings of the ACM Multimedia '94 Conference, October 1994.

Yossi Azar, Andrei Broder, and Mark Manasse. On-line choice of on-line algorithms. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 432-440, 1993.

Arjen K. Lenstra, H.W. Lenstra, Mark Manasse, and J.M. Pollard. The factorization of the ninth Fermat number. Math Comp., 61:318-349, 1993.

Mark Manasse and Greg Nelson. Trestle reference manual. Research Report 68, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, December 1991.

Anna Karlin, Kai Li, Mark Manasse, and Susan Owicki. Empirical studies of competitive spinning for shared-memory multiprocessors. In Proceedings of the 13th ACM Symposium on Operating System Principles, October 1991.

Hania Gajewska, Mark Manasse, and Joel McCormack. Why X is not our ideal window system. Software Practice and Experience, June 1991.

Mark Manasse, Lyle McGeoch, and Daniel Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208-230, 1990.

Arjen K. Lenstra and Mark Manasse. Factoring by electronic mail. Advances in Cryptology ("EUROCRYPT 1989"), number 434 in Lecture Notes in Computer Science. Springer-Verlag, 1990.

Arjen K. Lenstra, H.W. Lenstra, Mark Manasse, and J.M. Pollard. The number field sieve. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 564-572, 1990.

Chris Ash, Julia Knight, Mark Manasse, and Theodore Slaman. Generic copies of countable structures. Annals of Pure and Applied Logic, 42:195-205, 1989.

Anna Karlin, Mark Manasse, Larry Rudolph, and Daniel Sleator. Competitive snoopy caching. Algorithmica, 3(1):79-119, 1988. Expanded from a paper in Proceedings of Annual IEEE Symposium on Foundations of Computer Science (1986).

Patents allowed and issued

Mark Manasse, Sergey Yekhanin, Parkshit Gopalan, Karin Strauss, and John Davis. Extended lifetine memory. U.S. Patent 9,422,799, September 2016.

John Davis, Parkshit Gopalan, Mark Manasse, Karin Strauss, and Sergey Yekhanin. Writing memory blocks using codewords. U.S. Patent 9,280,417, March 2016.

Mark Manasse, Chris Koenig, and Paul Oltean. Determination of landmarks. U.S. Patent 9,189,488, November 2015.

John Davis, Parkshit Gopalan, Mark Manasse, Karin Strauss, and Sergey Yekhanin. Writing memory blocks using codewords. U.S. Patent 8,972,640, March 2015.

Mark Manasse and Chris Koenig. Estimating document similarity using bit-strings. U.S. Patent 8,594,239, November, 2013.

Mark Manasse, Dan Teodosiu, and Akhil Walbe. Efficient algorithm for finding candidate objects for remote differential compression. U.S. Patent 8,112,496, Feb 2013.

Marc Najork, Dennis Fetterly, Mark Manasse, and Alex Ntoulas. Using content analysis to detect spam web pages. U.S. Patent 7,962,510, June 2011.

Guarav Sareen, Mark Manasse, Martin Abadi, and Michael Isard. Searching For Information Utilizing A Probabalistic Detector. U.S. Patent 7,730,058, June 2010.

Mark Manasse, Alice Silverberg, and Chandu Thekkath. Erasure coding and group computations using rooted binary and ternary trees. U.S. Patent, 7,716,250, May 2010.

Frank McSherry, Kunal Talwar, and Mark Manasse. Consistent weighted sampling of multisets and distributions. U.S. Patent, 7,716,144, May 2010.

Ulfar Erlingsson, Mark Manasse, Frank McSherry, and Abraham Flaxman. Hash Tables. U.S. Patent, 7,664,927, February 2010.

Nikolaj Bjorner, Mark Manasse, Guilherme Fujiwara. Scalable differential compression of network data. U.S. Patent 7,640,354, December 2009.

Mark Manasse, Dan Teodosiu, and Akhil Wable. Efficient algorithm for finding candidate objects for remote differential compression. U.S. Patent 7,613,787, November 2009.

Mark Manasse. Method for duplicate detection and suppression. U.S. Patent 7,603,370, October 2009.

Mark Manasse. Systems and methods for providing improved encoding and reconstruction of data. U.S. Patent 7,581,156, August 2009.

Mark Manasse, Alice Silverberg, and Chandu Thekkath. Nodal pattern configuration. U.S. Patent 7,542,431, June 2009.

Mark Manasse. Method and apparatus for improving the performance of a disk drive. U.S. Patent 7,430,091, September 2008.

Steve Glassman and Mark Manasse. System and method for providing multi-class processing of login requests. U.S. Patent 7,421,733, September 2008.

Steve Glassman, Mark Manasse, John Court, Jim Grohn, Andrew Palka, and Nigel Norris. Anonymous purchases while allowing verifiable identities for refunds returned along the paths taken to make the purchases U.S. Patent 7,257,554, August 2007.

Andrei Broder and Mark Manasse. System and method for determining likely identity in a biometric database. U.S. Patent 7,203,343, April 2007.

Mike Burrows, Martin Abadi, Mark Manasse, Ted Wobber, and Ron Daniel. Memory bound functions for spam deterrence and the like. U.S. Patent 7,149,801, February 2003.

Steve Glassman and Mark Manasse. Delegation of permissions in an electronic commerce system. U.S. Patent 6,523,012, February 2003.

Steve Glassman and Mark Manasse. Method and system for enforcing licenses on an open network. U.S. Patent 6,453,305, September 2002.

Steve Glassman and Mark Manasse. Encrypting secrets in a file for an electronic micro-commerce system. U.S. Patent 6,424,953, July 2002.

Andrei Broder, Steve Glassman, Greg Nelson, Mark Manasse, and Geoffrey Zweig. Method for clustering closely resembling data objects. U.S. Patent 6,349,296, February 2002.

Andrei Broder, Steve Glassman, and Mark Manasse. System and method for monitoring web pages by comparing generated abstracts. U.S. Patent 6,269,362, July 2001.

Andrei Broder, Steve Glassman, Greg Nelson, Mark Manasse, and Geoffrey Zweig. Method for clustering closely resembling data objects. U.S. Patent 6,119,124, September 2000.

Mark Manasse. A mechanism for low-priced electronic commerce. U.S. and international patents filed. U.S. Patent 5,802,497, September 1998.

Mark Manasse. Competitive snoopy caching for large-scale multiprocessors. U.S. Patent 5,345,578, October 1994.

Pending or abandoned patent applications

Extracurricular activities

I relish playing bass guitar for Severe Tire Damage, the first band on the MBone, and the only band that really cares.