Wikipedia

Martin Farach-Colton

Martin Farach-Coltonis an Americancomputer scientist,known for his work instreaming algorithms,suffix treeconstruction,pattern matchingincompressed data,cache-oblivious algorithms,andlowest common ancestordata structures.He is theLeonard J. ShustekProfessor of Computer Science and chair of the Department of Computer Science and Engineering atNew York University.[1]Formerly, he was a Distinguished Professor of Computer Science atRutgers University.[2]He co-founded the storage technology startup company Tokutek.[3]

Martin Farach-Colton
Farach-Colton at the 2013White House Office of Science and Technology PolicyBig Data Workshop
Alma materJohns Hopkins School of Medicine,MD (1988)
University of Maryland, College Park,PhD (1991)
Scientific career
FieldsComputer science
InstitutionsNew York University
ThesisString Algorithms for Template Matching(1991)
Doctoral advisorAmihood Amir

Early life and education

edit

Farach-Colton is ofArgentinedescent and grew up inSouth Carolina.While attendingmedical school,he met his future husband, with whom he now has twin children.[4]He obtained his M.D. in 1988 from theJohns Hopkins School of Medicine[5]and his Ph.D. in computer science in 1991 from theUniversity of Maryland, College Parkunder the supervision of Amihood Amir.[6]

Research contributions

edit

After completing his Ph.D., he went on to work atGoogleand co-founded Tokutek.[7]He was program chair of the 14th ACM-SIAMSymposium on Discrete Algorithms(SODA 2003).[8]Thecache-obliviousB-treedata structures studied by Bender, Demaine, and Farach-Colton beginning in 2000 became the basis for thefractal tree indexused by Tokutek's productsTokuDBand TokuMX.[3]

Awards and honors

edit

In 1996, Farach-Colton was awarded anAlfred P. Sloan Research Fellowship.[9]In 2021, he was inducted as aSIAM Fellow"for contributions to the design and analysis of algorithms and their use in storage systems andcomputational biology"[10]and as anACM Fellow"for contributions to data structures for biocomputing and big data"[11]In 2022, he was inducted as anIEEE Fellow"for contributions to data structures for storage systems".[12] In 2023, he was elected to the Argentine Academia Nacional de Ciencias Exactas, Fisicas y Naturales.[13]In 2024, he was inducted as anAAAS Fellow.[14]

In 2012, his paper "The LCA problem revisited" won the Simon Imre Test of Time award at LATIN.[15]In 2016, his paper "Optimizing Every Operation in a Write-optimized File System" won the Best Paper award at FAST.[16] In 2023, his paper "Mosaic Pages: Big TLB Reach with Small Pages" won a Distinguished Paper award as ASPLOS.[17]

Personal life

edit

Farach-Colton is an avidBrazilian jiu-jitsupractitioner and received a bronze medal at the 2015 World Master Jiu-Jitsu IBJJF Championship.[18]He received hisblack beltfrom Russell Kerr in 2018.[19]Farach-Colton has served on several charity boards including theAli Forney Center,Lambda Legal,[20]andThe Trevor Project.[21]

Selected publications

edit
  • Amir, Amihood; Benson, Gary; Farach, Martin (April 1996),"Let sleeping files lie: pattern matching in Z-compressed files"(PDF),Journal of Computer and System Sciences,52(2):299–307,CiteSeerX10.1.1.45.6476,doi:10.1006/jcss.1996.0023,MR1393996,S2CID14465635,archived fromthe original(PDF)on 2017-08-10,retrieved2017-09-08.
  • Farach, Martin (1997), "Optimal suffix tree construction with large alphabets",38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997,IEEE Computer Society, pp.137–143,CiteSeerX10.1.1.45.4336,doi:10.1109/SFCS.1997.646102,ISBN0-8186-8197-7,S2CID123355749.
  • Farach, M.;Thorup, M.(April 1998), "String matching in Lempel-Ziv compressed strings",Algorithmica,20(4):388–404,CiteSeerX10.1.1.45.5484,doi:10.1007/PL00009202,MR1600834,S2CID15395909.
  • Bender, Michael A.; Farach-Colton, Martin (2000),"The LCA problem revisited"(PDF),in Gonnet, Gaston H.; Panario, Daniel; Viola, Alfredo (eds.),LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings,Lecture Notes in Computer Science, vol. 1776, Springer, pp.88–94,doi:10.1007/10719839_9,ISBN978-3-540-67306-4.
  • Charikar, Moses;Chen, Kevin; Farach-Colton, Martin (2004),"Finding frequent items in data streams"(PDF),Theoretical Computer Science,312(1):3–15,CiteSeerX10.1.1.145.8413,doi:10.1016/S0304-3975(03)00400-6,MR2045483.Previously announced in ICALP 2002.
  • Bender, Michael A.;Demaine, Erik D.;Farach-Colton, Martin (2005),"Cache-oblivious B-trees",SIAM Journal on Computing,35(2):341–358,CiteSeerX10.1.1.32.4093,doi:10.1137/S0097539701389956,MR2191447.Previously announced at FOCS 2000.

References

edit
  1. ^News,Tandon School of Engineering, NYU, retrieved 2024-04-24.
  2. ^Professors,Computer Science, Rutgers, retrieved 2022-07-17.Archivedon 2022-08-17.
  3. ^abZicari, Roberto V. (October 8, 2012),"Scaling MySQL and MariaDB to TBs: Interview with Martín Farach-Colton",ODBMS Industry Watch.
  4. ^Farach-Colton, Martin (July 10, 2012),Trevisan, Luca(ed.),"Turing Centennial Post 5: Martin Farach-Colton",in theory.
  5. ^Usenix FAST
  6. ^Martin Farach-Coltonat theMathematics Genealogy Project
  7. ^"Alumni Hall Of Fame | UMD Department of Computer Science".www.cs.umd.edu.Retrieved2021-10-08.
  8. ^14th ACM-SIAM Symposium on Discrete Algorithms,SIAM, retrieved 2015-07-08.
  9. ^"Sloan Foundation, Past Fellows".Archived fromthe originalon 2016-11-06.Retrieved2021-03-31.
  10. ^SIAM Announces Class of 2021 Fellows,March 31, 2021,retrieved2021-04-03
  11. ^ACM Names 71 Fellows for Computing Advances that are Driving Innovation
  12. ^2022 NEWLY ELEVATED FELLOWS(PDF),November 22, 2022, archived fromthe original(PDF)on November 24, 2021,retrieved2021-11-24
  13. ^Incorporación del Dr. Martin Farach Colton,October 18, 2023,retrieved2023-11-28
  14. ^2023 AAAS FELLOWS,April 18, 2024,retrieved2024-04-19
  15. ^"LATIN".latintcs.org.Retrieved2021-10-08.
  16. ^"Best Papers".usenix.org.Retrieved2021-11-24.
  17. ^"ASPLOS 2023".asplos-conference.org.Retrieved2023-11-28.
  18. ^World Master Jiu-Jitsu IBJJF Championship 2015
  19. ^Clockwork Jiu Jitsu Instagram
  20. ^"Martin Farach-Colton".www.aliforneycenter.org.Retrieved2017-11-07.
  21. ^"Farach-Colton".www.thetrevorproject.org.Retrieved2020-09-04.
edit
Retrieved from "https://en.wikipedia.org/w/index.php?title=Martin_Farach-Colton&oldid=1254656456"