Source author record

Mingmou Liu

Mingmou Liu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity

Catalog footprint

What is connected

3works

2topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Nearly Tight Lower Bounds for Succinct Range Minimum Query

Given an array of distinct integers $A[1\ldots n]$, the Range Minimum Query (RMQ) problem requires us to construct a data structure from $A$, supporting the RMQ query: given an interval $[a,b]\subseteq[1,n]$, return the index of the minimum element in subarray $A[a\ldots b]$, i.e. return $\text{argmin}_{i\in[a,b]}A[i]$. The fundamental problem has a long history. The textbook solution which uses $O(n)$ words of space and $O(1)$ time by Gabow, Bentley, Tarjan (STOC 1984) and Harel, Tarjan (SICOMP 1984) dates back to 1980s. The state-of-the-art solution is presented by Fischer, Heun (SICOMP 2011) and Navarro, Sadakane (TALG 2014). The solution uses $2n-1.5\log n+n/\left(\frac{\log n}{t}\right)^t+\tilde{O}(n^{3/4})$ bits of space and $O(t)$ query time, where the additive $\tilde{O}(n^{3/4})$ is a pre-computed lookup table used in the RAM model, assuming the word-size is $Θ(\log n)$ bits. On the other hand, the only known lower bound is proved by Liu and Yu (STOC 2020). They show that any data structure which solves RMQ in $t$ query time must use $2n-1.5\log n+n/(\log n)^{O(t^2\log^2t)}$ bits of space, assuming the word-size is $Θ(\log n)$ bits. In this paper, we prove nearly tight lower bound for this problem. We show that, for any data structure which solves RMQ in $t$ query time, $2n-1.5\log n+n/(\log n)^{O(t\log^2t)}$ bits of space is necessary in the cell-probe model with word-size $Θ(\log n)$ bits. We emphasize that, in terms of time complexity, our lower bound is tight up to a polylogarithmic factor.

preprint2020arXiv

Succinct Filters for Sets of Unknown Sizes

The membership problem asks to maintain a set $S\subseteq[u]$, supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that computes exact answers is called a dictionary. When a (small) false positive rate $ε$ is allowed, the data structure is called a filter. The space usages of the standard dictionaries or filters usually depend on the upper bound on the size of $S$, while the actual set can be much smaller. Pagh, Segev and Wieder (FOCS'13) were the first to study filters with varying space usage based on the current $|S|$. They showed in order to match the space with the current set size $n=|S|$, any filter data structure must use $(1-o(1))n(\log(1/ε)+(1-O(ε))\log\log n)$ bits, in contrast to the well-known lower bound of $N\log(1/ε)$ bits, where $N$ is an upper bound on $|S|$. They also presented a data structure with almost optimal space of $(1+o(1))n(\log(1/ε)+O(\log\log n))$ bits provided that $n>u^{0.001}$, with expected amortized constant insertion time and worst-case constant lookup time. In this work, we present a filter data structure with improvements in two aspects: - it has constant worst-case time for all insertions and lookups with high probability; - it uses space $(1+o(1))n(\log (1/ε)+\log\log n)$ bits when $n>u^{0.001}$, achieving optimal leading constant for all $ε=o(1)$. We also present a dictionary that uses $(1+o(1))n\log(u/n)$ bits of space, matching the optimal space in terms of the current size, and performs all operations in constant time with high probability.

preprint2016arXiv

Randomized approximate nearest neighbor search with limited adaptivity

We study the fundamental problem of approximate nearest neighbor search in $d$-dimensional Hamming space $\{0,1\}^d$. We study the complexity of the problem in the famous cell-probe model, a classic model for data structures. We consider algorithms in the cell-probe model with limited adaptivity, where the algorithm makes $k$ rounds of parallel accesses to the data structure for a given $k$. For any $k\ge 1$, we give a simple randomized algorithm solving the approximate nearest neighbor search using $k$ rounds of parallel memory accesses, with $O(k(\log d)^{1/k})$ accesses in total. We also give a more sophisticated randomized algorithm using $O(k+(\frac{1}{k}\log d)^{O(1/k)})$ memory accesses in $k$ rounds for large enough $k$. Both algorithms use data structures of size polynomial in $n$, the number of points in the database. For the lower bound, we prove an $Ω(\frac{1}{k}(\log d)^{1/k})$ lower bound for the total number of memory accesses required by any randomized algorithm solving the approximate nearest neighbor search within $k\le\frac{\log\log d}{2\log\log\log d}$ rounds of parallel memory accesses on any data structures of polynomial size. This lower bound shows that our first algorithm is asymptotically optimal for any constant round $k$. And our second algorithm approaches the asymptotically optimal tradeoff between rounds and memory accesses, in a sense that the lower bound of memory accesses for any $k_1$ rounds can be matched by the algorithm within $k_2=O(k_1)$ rounds. In the extreme, for some large enough $k=Θ\left(\frac{\log\log d}{\log\log\log d}\right)$, our second algorithm matches the $Θ\left(\frac{\log\log d}{\log\log\log d}\right)$ tight bound for fully adaptive algorithms for approximate nearest neighbor search due to Chakrabarti and Regev.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint