Source author record

Moshe Lewenstein

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

Catalog footprint

Research overview

10works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Longest Common Extensions in Sublinear Space

The longest common extension problem (LCE problem) is to construct a data structure for an input string $T$ of length $n$ that supports LCE $(i,j)$ queries. Such a query returns the length of the longest common prefix of the suffixes starting at positions $i$ and $j$ in $T$ . This classic problem has a well-known solution that uses $O(n)$ space and $O(1)$ query time. In this paper we show that for any trade-off parameter $1 \leq τ\leq n$ , the problem can be solved in $O(\frac{n}τ)$ space and $O(τ)$ query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound.

preprint2014arXiv

On Hardness of Jumbled Indexing

Jumbled indexing is the problem of indexing a text $T$ for queries that ask whether there is a substring of $T$ matching a pattern represented as a Parikh vector, i.e., the vector of frequency counts for each character. Jumbled indexing has garnered a lot of interest in the last four years. There is a naive algorithm that preprocesses all answers in $O(n^2|Σ|)$ time allowing quick queries afterwards, and there is another naive algorithm that requires no preprocessing but has $O(n\log|Σ|)$ query time. Despite a tremendous amount of effort there has been little improvement over these running times. In this paper we provide good reason for this. We show that, under a 3SUM-hardness assumption, jumbled indexing for alphabets of size $ω(1)$ requires $Ω(n^{2-ε})$ preprocessing time or $Ω(n^{1-δ})$ query time for any $ε,δ>0$ . In fact, under a stronger 3SUM-hardness assumption, for any constant alphabet size $r\ge 3$ there exist describable fixed constant $ε_r$ and $δ_r$ such that jumbled indexing requires $Ω(n^{2-ε_r})$ preprocessing time or $Ω(n^{1-δ_r})$ query time.

preprint2014arXiv

Space-Efficient String Indexing for Wildcard Pattern Matching

In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(n\log^{\varepsilon}n)$ bits for any $\varepsilon>0$ and reports all $\mathrm{occ}$ occurrences of a wildcard string in $O(m+σ^g \cdotμ(n) + \mathrm{occ})$ time, where $μ(n)=o(\log\log\log n)$ , $σ$ is the alphabet size, $m$ is the number of alphabet symbols and $g$ is the number of wildcard symbols in the query string. We also present an $O(n)$ -bit index with $O((m+σ^g+\mathrm{occ})\log^{\varepsilon}n)$ query time and an $O(n(\log\log n)^2)$ -bit index with $O((m+σ^g+\mathrm{occ})\log\log n)$ query time. These are the first non-trivial data structures for this problem that need $o(n\log n)$ bits of space.

preprint2014arXiv

Weighted ancestors in suffix trees

The classical, ubiquitous, predecessor problem is to construct a data structure for a set of integers that supports fast predecessor queries. Its generalization to weighted trees, a.k.a. the weighted ancestor problem, has been extensively explored and successfully reduced to the predecessor problem. It is known that any solution for both problems with an input set from a polynomially bounded universe that preprocesses a weighted tree in O(n polylog(n)) space requires Ω(loglogn) query time. Perhaps the most important and frequent application of the weighted ancestors problem is for suffix trees. It has been a long-standing open question whether the weighted ancestors problem has better bounds for suffix trees. We answer this question positively: we show that a suffix tree built for a text w[1..n] can be preprocessed using O(n) extra space, so that queries can be answered in O(1) time. Thus we improve the running times of several applications. Our improvement is based on a number of data structure tools and a periodicity-based insight into the combinatorial structure of a suffix tree.

preprint2013arXiv

Finding the Minimum-Weight k-Path

Given a weighted $n$ -vertex graph $G$ with integer edge-weights taken from a range $[-M,M]$ , we show that the minimum-weight simple path visiting $k$ vertices can be found in time $\tilde{O}(2^k \poly(k) M n^ω) = O^*(2^k M)$. If the weights are reals in $[1,M]$ , we provide a $(1+\varepsilon)$ -approximation which has a running time of $\tilde{O}(2^k \poly(k) n^ω(\log\log M + 1/\varepsilon))$. For the more general problem of $k$ -tree, in which we wish to find a minimum-weight copy of a $k$ -node tree $T$ in a given weighted graph $G$ , under the same restrictions on edge weights respectively, we give an exact solution of running time $\tilde{O}(2^k \poly(k) M n^3) $ and a $(1+\varepsilon)$ -approximate solution of running time $\tilde{O}(2^k \poly(k) n^3(\log\log M + 1/\varepsilon))$. All of the above algorithms are randomized with a polynomially-small error probability.

preprint2013arXiv

Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing

This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data structure that handles unbounded-length keys whose comparison cost is not a constant. Examples of these keys are strings, multi-dimensional points, multiple-precision numbers, multi-key data (e.g.~records), XML paths, URL addresses, etc. The technique is more general than what has been done in previous work as no particular exploitation of the underlying structure of is required. The only requirement is that the insertion of a key must identify its predecessor or its successor. Using the proposed technique, online suffix tree can be constructed in worst case time $O(\log n)$ per input symbol (as opposed to amortized $O(\log n)$ time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves $O(\log n)$ worst case time per input symbol. Searching for a pattern of length $m$ in the resulting suffix tree takes $O(\min(m\log |Σ|, m + \log n) + tocc)$ time, where $tocc$ is the number of occurrences of the pattern. The paper also describes more applications and show how to obtain alternative methods for dealing with suffix sorting, dynamic lowest common ancestors and order maintenance.

preprint2013arXiv

Succinct data structures for representing equivalence classes

Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. -- Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of (\sum_{i=1}^n \lfloor {n \over i} \rfloor) is necessary and sufficient. In other words, \lg n + \lg \lg n + O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \lceil \lg n \rceil for the label length, if each vertex need not get a unique label. --Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set {1, 2, ...n}, we first show that Θ(\sqrt n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(\lg n) time in the standard word RAM model. We then develop structures resulting in one where the queries can be supported in constant time using O({\sqrt n} \lg n) bits of space. We also develop space efficient structures where union operation along with the equivalence query can be answered fast.

preprint2013arXiv

Suffix Trays and Suffix Trists: Structures for Faster Text Indexing

Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially sized alphabets. However, when it comes to answering queries with worst-case deterministic time bounds, the prior does so in $O(m\log|Σ|)$ time, where $m$ is the query size, $|Σ|$ is the alphabet size, and the latter does so in $O(m+\log n)$ time, where $n$ is the text size. If one wants to output all appearances of the query, an additive cost of $O(occ)$ time is sufficient, where $occ$ is the size of the output. We propose a novel way of combining the two into, what we call, a {\em suffix tray}. The space and construction time remain linear and the query time improves to $O(m+\log|Σ|)$ for integer alphabets from a linear range, i.e. $Σ\subset \{1,\cdots, cn\}$ , for an arbitrary constant $c$ . The construction and query are deterministic. Here also an additive $O(occ)$ time is sufficient if one desires to output all appearances of the query. We also consider the online version of indexing, where the text arrives online, one character at a time, and indexing queries are answered in tandem. In this variant we create a cross between a suffix tree and a suffix list (a dynamic variant of suffix array) to be called a {\em suffix trist}; it supports queries in $O(m+\log|Σ|)$ time. The suffix trist also uses linear space. Furthermore, if there exists an online construction for a linear-space suffix tree such that the cost of adding a character is worst-case deterministic $f(n,|Σ|)$ ( $n$ is the size of the current text), then one can further update the suffix trist in $O(f(n,|Σ|)+\log |Σ|)$ time. The best currently known worst-case deterministic bound for $f(n,|Σ|)$ is $O(\log n)$ time.

preprint2010arXiv

Fast, precise and dynamic distance queries

We present an approximate distance oracle for a point set S with n points and doubling dimension λ. For every ε>0, the oracle supports (1+ε)-approximate distance queries in (universal) constant time, occupies space [ε^{-O(λ)} + 2^{O(λ log λ)}]n, and can be constructed in [2^{O(λ)} log3 n + ε^{-O(λ)} + 2^{O(λ log λ)}]n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel. Furthermore, the oracle can be made fully dynamic with expected O(1) query time and only 2^{O(λ)} log n + ε^{-O(λ)} + 2^{O(λ log λ)} update time. This is the first fully dynamic (1+ε)-distance oracle.

preprint2010arXiv

Restricted Common Superstring and Restricted Common Supersequence

The {\em shortest common superstring} and the {\em shortest common supersequence} are two well studied problems having a wide range of applications. In this paper we consider both problems with resource constraints, denoted as the Restricted Common Superstring (shortly \textit{RCSstr}) problem and the Restricted Common Supersequence (shortly \textit{RCSseq}). In the \textit{RCSstr} (\textit{RCSseq}) problem we are given a set $S$ of $n$ strings, $s_1$ , $s_2$ , $\ldots$ , $s_n$ , and a multiset $t = \{t_1, t_2, \dots, t_m\}$ , and the goal is to find a permutation $π: \{1, \dots, m\} \to \{1, \dots, m\}$ to maximize the number of strings in $S$ that are substrings (subsequences) of $π(t) = t_{π(1)}t_{π(2)}...t_{π(m)}$ (we call this ordering of the multiset, $π(t)$ , a permutation of $t$ ). We first show that in its most general setting the \textit{RCSstr} problem is {\em NP-complete} and hard to approximate within a factor of $n^{1-ε}$ , for any $ε> 0$ , unless P = NP. Afterwards, we present two separate reductions to show that the \textit{RCSstr} problem remains NP-Hard even in the case where the elements of $t$ are drawn from a binary alphabet or for the case where all input strings are of length two. We then present some approximation results for several variants of the \textit{RCSstr} problem. In the second part of this paper, we turn to the \textit{RCSseq} problem, where we present some hardness results, tight lower bounds and approximation 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.

Moshe Lewenstein

Research overview

Is this your work?

10 publications

Longest Common Extensions in Sublinear Space

On Hardness of Jumbled Indexing

Space-Efficient String Indexing for Wildcard Pattern Matching

Weighted ancestors in suffix trees

Finding the Minimum-Weight k-Path

Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing

Succinct data structures for representing equivalence classes

Suffix Trays and Suffix Trists: Structures for Faster Text Indexing

Fast, precise and dynamic distance queries

Restricted Common Superstring and Restricted Common Supersequence

See the researcher in context

Building this map preview