ML p(r)ior | Deterministic sub-linear space LCE data structures with efficient construction

Deterministic sub-linear space LCE data structures with efficient construction

2016-01-28
Given a string $S$ of $n$ symbols, a longest common extension query $\mathsf{LCE}(i,j)$ asks for the length of the longest common prefix of the $i$th and $j$th suffixes of $S$. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015: 65-76) described several data structures for answering LCE queries that offers a space-time trade-off between data structure size and query time. In particular, for a parameter $1 \leq \tau \leq n$, their best deterministic solution is a data structure of size $O(n/\tau)$ which allows LCE queries to be answered in $O(\tau)$ time. However, the construction time for all deterministic versions of their data structure is quadratic in $n$. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of $O(\tau\min\{\log\tau,\log\frac{n}{\tau}\})$ query time using $O(n/\tau)$ space, but significantly improve the construction time to $O(n\tau)$.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2017-12-13
1712.04886 | cs.DS

We propose algorithms that, given the input string of length $n$ over integer alphabet of size $\sig… show more
PDF

Highlights - Most important sentences from the article

2019-04-08
1904.04228 | cs.DS

Burrows-Wheeler transform (BWT) is an invertible text transformation that, given a text $T$ of lengt… show more
PDF

Highlights - Most important sentences from the article

2018-11-03
1811.01248 | cs.DS

Given $d$ strings over the alphabet $\{0,1,\ldots,\sigma{-}1\}$, the classical Aho--Corasick data st… show more
PDF

Highlights - Most important sentences from the article

2019-02-14
1902.05224 | cs.DS

Converting a compressed format of a string into another compressed format without an explicit decomp… show more
PDF

Highlights - Most important sentences from the article

2019-01-30

Palindromes are important objects in strings which have been extensively studied from combinatorial,… show more
PDF

Highlights - Most important sentences from the article

2018-11-05
1811.02078 | cs.DS

Given an $n$-bit array $A$, the succinct rank data structure problem asks to construct a data struct… show more
PDF

Highlights - Most important sentences from the article

2018-12-02
1812.00359 | cs.DS

We consider two closely related problems of text indexing in a sub-linear working space. The first p… show more
PDF

Highlights - Most important sentences from the article

2018-09-08

Indexing highly repetitive texts --- such as genomic databases, software repositories and versioned … show more
PDF

Highlights - Most important sentences from the article

2018-06-05
1806.01804 | cs.DS

We present the first solution to $\tau$-majorities on tree paths. Given a tree of $n$ nodes, each wi… show more
PDF

Highlights - Most important sentences from the article

2017-12-22

In the longest common substring problem, we are given two strings of length $n$ and must find a subs… show more
PDF

Highlights - Most important sentences from the article

2018-04-23

In the longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length … show more
PDF

Highlights - Most important sentences from the article

2019-01-30

A maximal repetition, or run, in a string, is a periodically maximal substring whose smallest period… show more
PDF

Highlights - Most important sentences from the article

2015-01-10
1501.02309 | cs.CG

Given a set $P$ of $n$ uncertain points on the real line, each represented by its one-dimensional pr… show more
PDF

Highlights - Most important sentences from the article

2018-06-26

The nearest neighbor problem is defined as follows: Given a set $P$ of $n$ points in some metric spa… show more
PDF

Highlights - Most important sentences from the article

2012-03-06
1203.1080 | cs.CC

In this paper we investigate the problem of building a static data structure that represents a strin… show more
PDF

Highlights - Most important sentences from the article

2013-07-25
1307.6789 | cs.DS

Let $\mathcal{D}$ be a collection of $D$ documents, which are strings over an alphabet of size $\sig… show more
PDF

Highlights - Most important sentences from the article