Martin Farach-Colton

Orcid: 0000-0003-3616-7788

Affiliations:
  • New York University, NY, USA
  • Rutgers University, USA (former)


According to our database1, Martin Farach-Colton authored at least 171 papers between 1989 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2021, "For contributions to data structures for biocomputing and big data".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
File System Aging.
CoRR, 2024

2023
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once.
J. ACM, December, 2023

From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071).
Dagstuhl Reports, February, 2023

SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy.
Proc. ACM Manag. Data, 2023

IcebergHT: High Performance Hash Tables Through Stability and Low Associativity.
Proc. ACM Manag. Data, 2023

An Associativity Threshold Phenomenon in Set-Associative Caches.
Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Tiny Pointers.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Tight Bounds for Monotone Minimal Perfect Hashing.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Graph Ranking and the Cost of Sybil Defense.
Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Optimal Uncoordinated Unique IDs.
Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

Mosaic Pages: Big TLB Reach with Small Pages.
Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, 2023

Analyzing and Implementing GPU Hash Tables.
Proceedings of the 2023 Symposium on Algorithmic Principles of Computer Systems, 2023

2022
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity.
CoRR, 2022

Using advanced data structures to enable responsive security monitoring.
Clust. Comput., 2022

On the optimal time/space tradeoff for hash tables.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams.
Proceedings of the SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

What Does Dynamic Optimality Mean in External Memory?
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Online List Labeling: Breaking the log<sup>2</sup>n Barrier.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

BetrFS: a compleat file system for commodity SSDs.
Proceedings of the EuroSys '22: Seventeenth European Conference on Computer Systems, Rennes, France, April 5, 2022

2021
Copy-on-Abundant-Write for Nimble File System Clones.
ACM Trans. Storage, 2021

External-memory Dictionaries in the Affine and PDAM Models.
ACM Trans. Parallel Comput., 2021

Timely Reporting of Heavy Hitters Using External Memory.
ACM Trans. Database Syst., 2021

Dynamic Windows Scheduling with Reallocation.
ACM J. Exp. Algorithmics, 2021

All-Purpose Hashing.
CoRR, 2021

Better GPU Hash Tables.
CoRR, 2021

Paging and the Address-Translation Problem.
Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design.
Proceedings of the SIGMOD '21: International Conference on Management of Data, 2021

Mitigating False Positives in Filters: to Adapt or to Cache?
Proceedings of the 2nd Symposium on Algorithmic Principles of Computer Systems, 2021

2020
How to Not Copy Files.
login Usenix Mag., 2020

SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores.
Proceedings of the 2020 USENIX Annual Technical Conference, 2020

Streaming Complexity of Spanning Tree Computation.
Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Flushing Without Cascades.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

How to Copy Files.
Proceedings of the 18th USENIX Conference on File and Storage Technologies, 2020

2019
Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111).
Dagstuhl Reports, 2019

Achieving optimal backlog in multi-processor cup games.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Small Refinements to the DAM Can Have Big Consequences for Data-Structure Design.
Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Optimal Ball Recycling.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Engineering a high-performance GPU B-Tree.
Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2019

Filesystem Aging: It's more Usage than Fullness.
Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems, 2019

Syntactic Separation of Subset Satisfiability Problems.
Proceedings of the Approximation, 2019

2018
Efficient Directory Mutations in a Full-Path-Indexed File System.
ACM Trans. Storage, 2018

The Online Event-Detection Problem.
CoRR, 2018

Closure Operators and Spam Resistance for PageRank.
CoRR, 2018

Streaming Algorithms for Planar Convex Hulls.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Quotient Filters: Approximate Membership Queries on the GPU.
Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium, 2018

GPU LSM: A Dynamic Dictionary Data Structure for the GPU.
Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium, 2018

A Dynamic Hash Table for the GPU.
Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium, 2018

Optimal Hashing in External Memory.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Mind the Gap (Invited Paper).
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Bloom Filters, Adaptivity, and the Dictionary Problem.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

The Full Path to Full-Path Indexing.
Proceedings of the 16th USENIX Conference on File and Storage Technologies, 2018

2017
How to Fragment Your File System.
login Usenix Mag., 2017

Writes Wrought Right, and Other Adventures in File System Optimization.
ACM Trans. Storage, 2017

Cost-Oblivious Storage Reallocation.
ACM Trans. Algorithms, 2017

Fault-tolerant aggregation: Flow-Updating meets Mass-Distribution.
Distributed Comput., 2017

Dictionaries Revisited.
Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

Cross-Referenced Dictionaries and the Limits of Write Optimization.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Write-Optimized Skip Lists.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

File Systems Fated for Senescence? Nonsense, Says Science!
Proceedings of the 15th USENIX Conference on File and Storage Technologies, 2017

2016
Lowest Common Ancestors in Trees.
Encyclopedia of Algorithms, 2016

Special issue in honor of the 60th birthday of Amihood Amir.
Theor. Comput. Sci., 2016

40 years of suffix trees.
Commun. ACM, 2016

Parallel Lookups in String Indexes.
Proceedings of the String Processing and Information Retrieval, 2016

Tight Approximations of Degeneracy in Large Graphs.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

The I/O Complexity of Computing Prime Tables.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Lazy Analytics: Let Other Queries Do the Work For You.
Proceedings of the 8th USENIX Workshop on Hot Topics in Storage and File Systems, 2016

Optimizing Every Operation in a Write-optimized File System.
Proceedings of the 14th USENIX Conference on File and Storage Technologies, 2016

2015
An Introduction to Bε-trees and Write-Optimization.
login Usenix Mag., 2015

BetrFS: Write-Optimization in a Kernel File System.
ACM Trans. Storage, 2015

Exact Sublinear Binomial Sampling.
Algorithmica, 2015

Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model.
Algorithmica, 2015

Reallocation Problems in Scheduling.
Algorithmica, 2015

Finding Articulation Points of Large Graphs in Linear Time.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Cost-Oblivious Reallocation for Scheduling and Planning.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

On the Complexity of Computing Prime Tables.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

BetrFS: A Right-Optimized Write-Optimized File System.
Proceedings of the 13th USENIX Conference on File and Storage Technologies, 2015

2014
Computing the Degeneracy of Large Graphs.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

The Batched Predecessor Problem in External Memory.
Proceedings of the Algorithms - ESA 2014, 2014

2013
Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound).
Theor. Comput. Sci., 2013

Forty Years of Text Indexing.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012
Don't Thrash: How to Cache Your Hash on Flash.
Proc. VLDB Endow., 2012

Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

The TokuFS Streaming File System.
Proceedings of the 4th USENIX Workshop on Hot Topics in Storage and File Systems, 2012

2011
Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: - Adaptiveness vs. Obliviousness and Randomization vs. Determinism.
Proceedings of the Distributed Computing - 25th International Symposium, 2011

Don't Thrash: How to Cache Your Hash on Flash.
Proceedings of the 3rd USENIX Workshop on Hot Topics in Storage and File Systems, 2011

2009
Bootstrapping a hop-optimal network in the weak sensor model.
ACM Trans. Algorithms, 2009

Efficient and Robust Prediction Algorithms for Protein Complexes Using Gomory-Hu Trees.
Proceedings of the Biocomputing 2009: Proceedings of the Pacific Symposium, 2009

2008
Fast and compact regular expression matching.
Theor. Comput. Sci., 2008

Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
ACM Trans. Algorithms, 2008

A Linear Delay Algorithm for Building Concept Lattices.
Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2007
Preface.
Theor. Comput. Sci., 2007

Introduction to SODA 2002 and 2003 special issue.
ACM Trans. Algorithms, 2007

Optimal spaced seeds for faster approximate string matching.
J. Comput. Syst. Sci., 2007

Cache-oblivious streaming B-trees.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Lattice based Clustering of Temporal Gene-Expression Matrices.
Proceedings of the Seventh SIAM International Conference on Data Mining, 2007

Sensor Network Gossiping or How to Break the Broadcast Lower Bound.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006
Insertion Sort is O(n log n).
Theory Comput. Syst., 2006

On the Complexity of Ordinal Clustering.
J. Classif., 2006

Cache-oblivious string B-trees.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Lower Bounds for Clear Transmissions in Radio Networks.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005
Cache-Oblivious B-Trees.
SIAM J. Comput., 2005

Lowest common ancestors in trees and directed acyclic graphs.
J. Algorithms, 2005

Adversarial contention resolution for simple channels.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

2004
Finding frequent items in data streams.
Theor. Comput. Sci., 2004

The Level Ancestor Problem simplified.
Theor. Comput. Sci., 2004

Discovering temporal relations in molecular pathways using protein-protein interactions.
Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, 2004

Adversarial Analyses of Window Backoff Strategies.
Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 2004

2003
Randomization, Persuasiveness and Rigor in Proofs.
Synth., 2003

Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes
CoRR, 2003

Adventures at Google.
Proceedings of the 4th Mexican International Conference on Computer Science (ENC 2003), 2003

2002
Efficient Tree Layout in a Multilevel Memory Hierarchy
CoRR, 2002

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks.
Algorithmica, 2002

Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Efficient Tree Layout in a Multilevel Memory Hierarchy.
Proceedings of the Algorithms, 2002

Two Simplified Algorithms for Maintaining Order in a List.
Proceedings of the Algorithms, 2002

Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy.
Proceedings of the Algorithms, 2002

2001
On the midpath tree conjuncture: a counter-example.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
An <i>O</i>(<i>n</i>log <i>n</i>) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
SIAM J. Comput., 2000

NOTUNG: A Program for Dating Gene Duplications and Optimizing Gene Family Trees.
J. Comput. Biol., 2000

On Local Register Allocation.
J. Algorithms, 2000

On the sorting-complexity of suffix tree construction.
J. ACM, 2000

Notung: dating gene duplications using gene family trees.
Proceedings of the Fourth Annual International Conference on Computational Molecular Biology, 2000

The LCA Problem Revisited.
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

COFE: A Scalable Method for Feature Extraction from Complex Objects.
Proceedings of the Data Warehousing and Knowledge Discovery, 2000

1999
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
SIAM J. Comput., 1999

Efficient Algorithms for Inverting Evolution.
J. ACM, 1999

Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Evaluation of Algorithms for Local Register Allocation.
Proceedings of the Compiler Construction, 8th International Conference, 1999

1998
Optimal Parallel Two Dimensional Text Searching on a CREW PRAM.
Inf. Comput., 1998

String Matching in Lempel-Ziv Compressed Strings.
Algorithmica, 1998

Overcoming the Memory Bottleneck in Suffix Tree Construction.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Sparse Dynamic Programming for Evolutionary-Tree Comparison.
SIAM J. Comput., 1997

Recognizing Circular Decompossible Metrics.
J. Comput. Biol., 1997

Numerical Taxonomy on Data: Experimental Results.
J. Comput. Biol., 1997

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model.
J. Comput. Biol., 1997

Optimal Two-Dimensional Compressed Matching.
J. Algorithms, 1997

Optimal Parallel Randomized Renaming.
Inf. Process. Lett., 1997

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Group testing problems with sequences in experimental molecular biology.
Proceedings of the Compression and Complexity of SEQUENCES 1997, 1997

Numerical taxonomy on data (abstract): experimental results.
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

DNA Strand Separation Prediction: A Parallel Implementation.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1997

Optimal Suffix Tree Construction with Large Alphabets.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Nearly Tight Bounds on the Learnability of Evolution.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Two dimensional matching.
Proceedings of the Pattern Matching Algorithms, 1997

1996
Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files.
J. Comput. Syst. Sci., 1996

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Optimal Logarithmic Time Randomized Suffix Tree Construction.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

The Structure of Circular Decomposable Metrics.
Proceedings of the Algorithms, 1996

Perfect Hashing for Strings: Formalization and Algorithms.
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995
Improved Dynamic Dictionary Matching
Inf. Comput., June, 1995

Efficient 2-Dimensional Approximate Matching of Half-Rectangular Figures
Inf. Comput., April, 1995

On the Agreement of Many Trees.
Inf. Process. Lett., 1995

Fast Comparison of Evolutionary Trees.
Inf. Comput., 1995

A Robust Model for Finding Optimal Evolutionary Trees.
Algorithmica, 1995

Optimal Parallel Dictionary Matching and Compression (Extended Abstract).
Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, 1995

On the Entropy of DNA: Algorithms and Measurements Based on Memory and Rapid Convergence.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Computing the Agreement of Trees with Bounded Degrees.
Proceedings of the Algorithms, 1995

1994
An Alphabet Independent Approach to Two-Dimensional Pattern Matching.
SIAM J. Comput., 1994

Dynamic Dictionary Matching.
J. Comput. Syst. Sci., 1994

Alphabet Dependence in Parameterized Matching.
Inf. Process. Lett., 1994

An Efficient Algorithm for Dynamic Text Indexing.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Optimal Parallel Two Dimensional Pattern Matching.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

1992
Two-Dimensional Dictionary Matching.
Inf. Process. Lett., 1992

Alphabet Independent Two Dimensional Matching
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Efficient Randomized Dictionary Matching Algorithms (Extended Abstract).
Proceedings of the Combinatorial Pattern Matching, Third Annual Symposium, 1992

1991
Optimal Superprimitivity Testing for Strings.
Inf. Process. Lett., 1991

Efficient matching of nonrectangular shapes.
Ann. Math. Artif. Intell., 1991

Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Adaptive Dictionary Matching
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1989
Generating plausible diagnostic hypotheses with self-processing causal networks.
J. Exp. Theor. Artif. Intell., 1989


  Loading...