Michael Bender

About

Michael A. Bender is the John L. Hennessy Chaired Professor of Computer Science at Stony Brook University. He has a distinguished background in algorithms, data structures, cache and I/O-efficient computing, parallel computing, databases, storage, and scheduling. Bender is the founder and former Chief Scientist of Tokutek, Inc, an enterprise database company acquired by Percona in 2014. His research encompasses both pure and applied aspects of algorithms and data structures, with over 200 publications and involvement as PI or co-PI in 40 grants. He has received numerous awards for his contributions to research and education, including fellowships in the IEEE, AAAS, and EATCS, as well as awards for teaching excellence and distinguished papers.

Research topics

• Computer Science
• Mathematics
• Algorithm
• Theoretical computer science
• Computer vision
• Programming language
• Computer network
• Parallel computing
• Operating system
• Combinatorics

Selected publications

• Vector Quotient Filters

  Proceedings of the 2022 International Conference on Management of Data · 2021 · 38 citations

  Today's filters, such as quotient, cuckoo, and Morton, have a trade-off between space and speed; even when moderately full (e.g., 50%-75% full), their performance degrades nontrivially. The result is that today's systems designers are forced to choose between speed and space usage. In this paper, we present the vector quotient filter (VQF). Locally, the VQF is based on Robin Hood hashing, like the quotient filter, but uses power-of-two-choices hashing to reduce the variance of runs, and thus off…

  DOI

• On the optimal time/space tradeoff for hash tables

  2022 · 20 citations

  1st authorCorresponding

  For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If keys/values are Θ(logn) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglogn) bits of space per key when compared to the information-theoretic optimum—this bound has been proven to be optimal for a number of closel…

  DOI

• Paging and the Address-Translation Problem

  2021 · 11 citations

  1st authorCorresponding

  The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In prac…

  PublisherDOI

• Tiny Pointers

  Society for Industrial and Applied Mathematics eBooks · 2023 · 10 citations

  1st authorCorresponding

  This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional log n-bit pointers can be replaced with o(log n)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e.,…

  PublisherDOI

• Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention Resolution

  2024-06-05 · 5 citations

  articleOpen access1st authorCorresponding

  Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet transmission can be made in any slot. A packet is successfully sent if no other packet is also transmitted during that slot. If two or more packets are sent in the same slot, then these packets collide and fail. Listening on the channel during a slot provides ternary feedback, indicating whether that slot had (0) silence, (1) a successful…

  PublisherDOI

Recent grants

• AF: Small: Collaborative Research: Maintaining Order

  NSF · $210k · 2016–2021

• CSR: Medium: Collaborative Research: FTFS: A Read/Write-Optimized Fractal Tree File System

  NSF · $624k · 2014–2019

• Collaborative Research: High-Performance Data Access through Memory Abstraction

  NSF · $150k · 2006–2011

Frequent coauthors

• Martı́n Farach-Colton

  125 shared

• Rob Johnson

  47 shared

• Esther M. Arkin

  Hangzhou Dianzi University

  47 shared

• Joseph S. B. Mitchell

  43 shared

• William Kuszmaul

  40 shared

• Jeremy T. Fineman

  Georgetown University

  40 shared

• Erik D. Demaine

  36 shared

• Seth Gilbert

  35 shared

Awards & honors

• Fellow of the Institute of Electrical and Electronics Engine…
• SPAA Distinguished Paper Award, 2025
• ACM SIGMOD Research Highlight Award, 2024
• Fellow of the American Association for the Advancement of Sc…
• Fellow of the European Association of Theoretical Computer S…

Similar researchers at Stony Brook University

• Wei Xuh-65
• Yoon Seok Yangh-64
• Xianfeng Guh-58