Martin Farach-Colton is an American

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

, known for his work in

streaming algorithm In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes (typically just one). In most models, these algorithms have access t ...

s, suffix tree construction,

pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be ...

in compressed data,

cache-oblivious algorithm In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An ...

s, and

lowest common ancestor In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where ...

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

s. He is a Distinguished Professor of computer science at

Rutgers University Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's ...

, and a co-founder of storage technology startup company Tokutek..

Early life and education

Farach-Colton is of Argentine descent, and grew up in

South Carolina )''Animis opibusque parati'' ( for, , Latin, Prepared in mind and resources, links=no) , anthem = " Carolina";" South Carolina On My Mind" , Former = Province of South Carolina , seat = Columbia , LargestCity = Charleston , LargestMetro = ...

. While attending

medical school A medical school is a tertiary educational institution, or part of such an institution, that teaches medicine, and awards a professional degree for physicians. Such medical degrees include the Bachelor of Medicine, Bachelor of Surgery (MBBS, M ...

, he met his future husband, with whom he now has twin children. He obtained his M.D. in 1988 from the

Johns Hopkins School of Medicine The Johns Hopkins University School of Medicine (JHUSOM) is the medical school of Johns Hopkins University, a private research university in Baltimore, Maryland. Founded in 1893, the School of Medicine shares a campus with the Johns Hopkins Hospi ...

and his Ph.D. in computer science in 1991 from the

University of Maryland, College Park The University of Maryland, College Park (University of Maryland, UMD, or simply Maryland) is a public land-grant research university in College Park, Maryland. Founded in 1856, UMD is the flagship institution of the University System of M ...

under the supervision of Amihood Amir.

Research contributions

After completing his Ph.D., he went on to work at

Google Google LLC () is an American multinational technology company focusing on search engine technology, online advertising, cloud computing, computer software, quantum computing, e-commerce, artificial intelligence, and consumer electronics. ...

and co-founded Tokutek. He was program chair of the 14th ACM-SIAM

Symposium on Discrete Algorithms The Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) is an academic conference in the fields of algorithm design and discrete mathematics. It is considered to be one of the top conferences for research in algorithms. SODA has been organized a ...

(SODA 2003). The

cache-oblivious In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An ...

B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for ...

data structures studied by Bender, Demaine, and Farach-Colton beginning in 2000 became the basis for the

fractal tree index In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. L ...

used by Tokutek's products

TokuDB TokuDB is an open-source, high-performance storage engine for MySQL and MariaDB. It achieves this by using a fractal tree index. It is scalable, ACID and MVCC compliant, provides indexing-based query improvements, offers online schema modifica ...

and

TokuMX TokuMX is an open-source distribution of MongoDB which, among other things, replaces the default B-tree data structure found in the basic MongoDB distribution with a fractal tree index. It is a drop-in replacement for MongoDB (applications will r ...

Awards and honors

In 1996, Farach-Colton was awarded an

Alfred P. Sloan Research Fellowship The Sloan Research Fellowships are awarded annually by the Alfred P. Sloan Foundation since 1955 to "provide support and recognition to early-career scientists and scholars". This program is one of the oldest of its kind in the United States. ...

. In 2021, he was inducted as a

SIAM Fellow The SIAM Fellowship is an award and fellowship that recognizes outstanding members of the Society for Industrial and Applied Mathematics (SIAM). The goal of the program is to: *honor SIAM members who are recognized by their peers as distinguished ...

"for contributions to the design and analysis of algorithms and their use in storage systems and computational biology" and as an

ACM Fellow ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * Arica Airport (Colombia) (IATA: ACM), in Arica, Amazonas, Colombia Computing * ...

"for contributions to data structures for biocomputing and big data" In 2022, he was inducted as an

IEEE Fellow As of 2019, the Institute of Electrical and Electronics Engineers (IEEE) has 5,082 members designated Fellow, each of whom is associated with one of the 41 societies under the IEEE. The Fellow grade of membership is the highest level of membershi ...

"for contributions to data structures for storage systems". In 2012 he won the Simon Imre Test of Time award at LATIN. In 2016, his paper "Optimizing Every Operation in a Write-optimized File System" won the Best Paper award at FAST.

Personal life

Farach-Colton is an avid

Brazilian jiu-jitsu Brazilian jiu-jitsu (BJJ; pt, jiu-jitsu brasileiro ) is a self-defence martial art and combat sport based on grappling, ground fighting (ne-waza) and submission holds. BJJ focuses on the skill of taking an opponent to the ground, control ...

practitioner and received a bronze medal at the 2015 World Master Jiu-Jitsu IBJJF Championship. He received his black belt from Russell Kerr in 2018. Farach-Colton has served on several charity boards including the

Ali Forney Center The Ali Forney Center (AFC), based in New York City, is the largest LGBT community center helping LGBTQ homeless youth in the United States. The AFC both manages and develops transitional housing for its clients. AFC helps approximately 2,000 y ...

and

Lambda Legal Lambda Legal Defense and Education Fund, better known as Lambda Legal, is an American civil rights organization that focuses on lesbian, gay, bisexual, and transgender (LGBT) communities as well as people living with HIV/AIDS ( PWAs) through imp ...

, and is currently on the board of

The Trevor Project The Trevor Project is an American nonprofit organization founded in 1998. Focused on suicide prevention efforts among lesbian, gay, bisexual, transgender, queer, and questioning (LGBTQ) youth, they offer a toll-free telephone number wher ...

Selected publications

*. *. *. *. *. Previously announced in ICALP 2002. *. Previously announced at FOCS 2000.

References

External links

Home pageGoogle scholar profile
{{DEFAULTSORT:Farach-Colton, Martin Year of birth missing (living people) Living people American people of Argentine descent American LGBT scientists American computer scientists Theoretical computer scientists University of Maryland, College Park alumni Rutgers University faculty LGBT people from South Carolina LGBT Hispanic and Latino American people LGBT academics Argentine computer scientists Fellows of the Society for Industrial and Applied Mathematics Fellow Members of the IEEE Fellows of the Association for Computing Machinery American practitioners of Brazilian jiu-jitsu People awarded a black belt in Brazilian jiu-jitsu