Source author record

Honghao Lin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Machine Learning quant-ph

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Learning Augmented Binary Search Trees

A treap is a classic randomized binary search tree data structure that is easy to implement and supports O(\log n) expected time access. However, classic treaps do not take advantage of the input distribution or patterns in the input. Given recent advances in algorithms with predictions, we propose pairing treaps with machine advice to form a learning-augmented treap. We are the first to propose a learning-augmented data structure that supports binary search tree operations such as range-query and successor functionalities. With the assumption that we have access to advice from a frequency estimation oracle, we assign learned priorities to the nodes to better improve the treap's structure. We theoretically analyze the learning-augmented treap's performance under various input distributions and show that under those circumstances, our learning-augmented treap has stronger guarantees than classic treaps and other classic tree-based data structures. Further, we experimentally evaluate our learned treap on synthetic datasets and demonstrate a performance advantage over other search tree data structures. We also present experiments on real world datasets with known frequency estimation oracles and show improvements as well.

preprint2022arXiv

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise; these are powerful and standard techniques in randomized numerical linear algebra. With this recognition, we are able to employ the large body of work in numerical linear algebra to obtain algorithms for these problems that are simpler or faster (or both) than existing approaches. Our experiments demonstrate that the proposed data structures also work well on real-world datasets.

preprint2022arXiv

Streaming Algorithms with Large Approximation Factors

We initiate a broad study of classical problems in the streaming model with insertions and deletions in the setting where we allow the approximation factor $α$ to be much larger than $1$ . Such algorithms can use significantly less memory than the usual setting for which $α= 1+ε$ for an $ε\in (0,1)$ . We study large approximations for a number of problems in sketching and streaming and the following are some of our results. For the $\ell_p$ norm/quasinorm $\|x\|_p$ of an $n$ -dimensional vector $x$ , $0 < p \le 2$ , we show that obtaining a $\poly(n)$-approximation requires the same amount of memory as obtaining an $O(1)$ -approximation for any $M = n^{Θ(1)}$ . For estimating the $\ell_p$ norm, $p > 2$ , we show an upper bound of $O(n^{1-2/p} (\log n \allowbreak \log M)/α^{2})$ bits for an $α$ -approximation, and give a matching lower bound, for almost the full range of $α\geq 1$ for linear sketches. For the $\ell_2$ -heavy hitters problem, we show that the known lower bound of $Ω(k \log n\log M)$ bits for identifying $(1/k)$ -heavy hitters holds even if we are allowed to output items that are $1/(αk)$ -heavy, for almost the full range of $α$ , provided the algorithm succeeds with probability $1-O(1/n)$ . We also obtain a lower bound for linear sketches that is tight even for constant probability algorithms. For estimating the number $\ell_0$ of distinct elements, we give an $n^{1/t}$ -approximation algorithm using $O(t\log \log M)$ bits of space, as well as a lower bound of $Ω(t)$ bits, both excluding the storage of random bits.

preprint2022arXiv

Triangle and Four Cycle Counting with Predictions in Graph Streams

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, (Hsu 2018) and (Jiang 2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms that did not use oracles. In this paper, we explore the power of a "heavy edge" oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.

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.

Honghao Lin

Research overview

Is this your work?

4 publications

Learning Augmented Binary Search Trees

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

Streaming Algorithms with Large Approximation Factors

Triangle and Four Cycle Counting with Predictions in Graph Streams

See the researcher in context

Building this map preview