STOC Conference 2022 Conference Paper
On the optimal time/space tradeoff for hash tables
- Michael A. Bender
- Martín Farach-Colton
- John Kuszmaul
- William Kuszmaul
- Mingmou Liu
Author name cluster
Mingmou Liu
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2STOC Conference 2020 Conference Paper
Lower bound for succinct range minimum query
- Mingmou Liu
- Huacheng Yu
Given an integer array A [1. n ], the Range Minimum Query problem (RMQ) asks to preprocess A into a data structure, supporting RMQ queries: given a , b ∈ [1, n ], return the index i ∈[ a , b ] that minimizes A [ i ], i.e., argmin i ∈[ a , b ] A [ i ]. This problem has a classic solution using O ( n ) space and O (1) query time by Gabow, Bentley, Tarjan (STOC, 1984) and Harel, Tarjan (SICOMP, 1984). The best known data structure by Fischer, Heun (SICOMP, 2011) and Navarro, Sadakane (TALG, 2014) uses 2 n + n /(log n / t ) t +Õ( n 3/4 ) bits and answers queries in O ( t ) time, assuming the word-size is w =Θ(log n ). In particular, it uses 2 n + n / poly log n bits of space as long as the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that 2 n + n / poly log n space is necessary for constant query time. In general, we show that if the data structure has query time O ( t ), then it must use at least 2 n + n /(log n ) Õ( t 2 ) space, in the cell-probe model with word-size w =Θ(log n ).