Source author record

Younan Gao

Younan Gao 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

Catalog footprint

What is connected

2works

1topics

2close 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

Computing Matching Statistics on Repetitive Texts

Computing the {\em matching statistics} of a string $P[1..m]$ with respect to a text $T[1..n]$ is a fundamental problem which has application to genome sequence comparison. In this paper, we study the problem of computing the matching statistics upon highly repetitive texts. We design three different data structures that are similar to LZ-compressed indexes. The space costs of all of them can be measured by $γ$, the size of the smallest string attractor [STOC'2018] and $δ$, a better measure of repetitiveness [LATIN'2020].

preprint2020arXiv

Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing

Under the word RAM model, we design three data structures that can be constructed in $O(n\sqrt{\lg n})$ time over $n$ points in an $n \times n$ grid. The first data structure is an $O(n\lg^ε n)$-word structure supporting orthogonal range reporting in $O(\lg\lg n+k)$ time, where $k$ denotes output size and $ε$ is an arbitrarily small constant. The second is an $O(n\lg\lg n)$-word structure supporting orthogonal range successor in $O(\lg\lg n)$ time, while the third is an $O(n\lg^ε n)$-word structure supporting sorted range reporting in $O(\lg\lg n+k)$ time. The query times of these data structures are optimal when the space costs must be within $O(n\ polylog\ n)$ words. Their exact space bounds match those of the best known results achieving the same query times, and the $O(n\sqrt{\lg n})$ construction time beats the previous bounds on preprocessing. Previously, among 2d range search structures, only the orthogonal range counting structure of Chan and Pǎtraşcu (SODA 2010) and the linear space, $O(\lg^ε n)$ query time structure for orthogonal range successor by Belazzougui and Puglisi (SODA 2016) can be built in the same $O(n\sqrt{\lg n})$ time. Hence our work is the first that achieve the same preprocessing time for optimal orthogonal range reporting and range successor. We also apply our results to improve the construction time of text indexes.