Gad M. Landau
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Gad M. Landau has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Oren Weimann
University of Haifa
11 shared publications - Philip Bille
Technical University of Denmark
6 shared publications - Danny Hermelin
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
5 shared publications - Inge Li Gørtz
Technical University of Denmark
5 shared publications - Paweł Gawrychowski
Institute of Informatics University of Warsaw Poland
3 shared publications - Amihood Amir
Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel
2 shared publications
Latest Publications
- 20 August 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (12) , 3602-3628
Top Tree Compression of Tries
- 20 August 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (12) , 3602-3628
Top Tree Compression of Tries
- Open Access
Top Tree Compression of Tries
We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preprocess a set of strings of total length $n$ over an alphabet of size $\sigma$ into a compressed data structure of worst-case optimal size $O(n/\log_\sigma n)$ that given a pattern string $P$ of length $m$ determines if $P$ is a prefix of one of the strings in time $O(\min(m\log \sigma,m + \log n))$. We show that this query time is in fact optimal regardless of the size of the data structure. Existing solutions either use $\Omega(n)$ space or rely on word RAM techniques, such as tabulation, hashing, address arithmetic, or word-level parallelism, and hence do not work on a pointer machine. Our result is the first solution on a pointer machine that achieves worst-case $o(n)$ space. Along the way, we develop several interesting data structures that work on a pointer machine and are of independent interest. These include an optimal data structures for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem.Open AccessTop Tree Compression of Tries
We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preprocess a set of strings of total length $n$ over an alphabet of size $\sigma$ into a compressed data structure of worst-case optimal size $O(n/\log_\sigma n)$ that given a pattern string $P$ of length $m$ determines if $P$ is a prefix of one of the strings in time $O(\min(m\log \sigma,m + \log n))$. We show that this query time is in fact optimal regardless of the size of the data structure. Existing solutions either use $\Omega(n)$ space or rely on word RAM techniques, such as tabulation, hashing, address arithmetic, or word-level parallelism, and hence do not work on a pointer machine. Our result is the first solution on a pointer machine that achieves worst-case $o(n)$ space. Along the way, we develop several interesting data structures that work on a pointer machine and are of independent interest. These include an optimal data structures for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem. - 1 February 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 710, 66-73
The nearest colored node in a tree
- 1 February 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 710, 66-73
The nearest colored node in a tree
- 1 February 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 710, 2-18
Period recovery of strings over the Hamming and edit distances
- 1 February 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 710, 2-18
Period recovery of strings over the Hamming and edit distances
- Open Access
String Cadences
We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. We give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences.
Open AccessString Cadences
We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. We give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences.
- Open Access
Longest Common Extensions in Trees
The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a string into a compact data structure that supports fast LCE queries. In this paper we generalize the LCE problem to trees and suggest a few applications of LCE in trees to tries and XML databases. Given a labeled and rooted tree $T$ of size $n$, the goal is to preprocess $T$ into a compact data structure that support the following LCE queries between subpaths and subtrees in $T$. Let $v_1$, $v_2$, $w_1$, and $w_2$ be nodes of $T$ such that $w_1$ and $w_2$ are descendants of $v_1$ and $v_2$ respectively. \begin{itemize} \item $\LCEPP(v_1, w_1, v_2, w_2)$: (path-path $\LCE$) return the longest common prefix of the paths $v_1 \leadsto w_1$ and $v_2 \leadsto w_2$. \item $\LCEPT(v_1, w_1, v_2)$: (path-tree $\LCE$) return maximal path-path LCE of the path $v_1 \leadsto w_1$ and any path from $v_2$ to a descendant leaf. \item $\LCETT(v_1, v_2)$: (tree-tree $\LCE$) return a maximal path-path LCE of any pair of paths from $v_1$ and $v_2$ to descendant leaves. \end{itemize} We present the first non-trivial bounds for supporting these queries. For $\LCEPP$ queries, we present a linear-space solution with $O(\log^{*} n)$ query time. For $\LCEPT$ queries, we present a linear-space solution with $O((\log\log n)^{2})$ query time, and complement this with a lower bound showing that any path-tree LCE structure of size $O(n \polylog(n))$ must necessarily use $\Omega(\log\log n)$ time to answer queries. For $\LCETT$ queries, we present a time-space trade-off, that given any parameter $\tau$, $1 \leq \tau \leq n$, leads to an $O(n\tau)$ space and $O(n/\tau)$ query-time solution. This is complemented with a reduction to the the set intersection problem implying that a fast linear space solution is not likely to exist.Open AccessLongest Common Extensions in Trees
The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a string into a compact data structure that supports fast LCE queries. In this paper we generalize the LCE problem to trees and suggest a few applications of LCE in trees to tries and XML databases. Given a labeled and rooted tree $T$ of size $n$, the goal is to preprocess $T$ into a compact data structure that support the following LCE queries between subpaths and subtrees in $T$. Let $v_1$, $v_2$, $w_1$, and $w_2$ be nodes of $T$ such that $w_1$ and $w_2$ are descendants of $v_1$ and $v_2$ respectively. \begin{itemize} \item $\LCEPP(v_1, w_1, v_2, w_2)$: (path-path $\LCE$) return the longest common prefix of the paths $v_1 \leadsto w_1$ and $v_2 \leadsto w_2$. \item $\LCEPT(v_1, w_1, v_2)$: (path-tree $\LCE$) return maximal path-path LCE of the path $v_1 \leadsto w_1$ and any path from $v_2$ to a descendant leaf. \item $\LCETT(v_1, v_2)$: (tree-tree $\LCE$) return a maximal path-path LCE of any pair of paths from $v_1$ and $v_2$ to descendant leaves. \end{itemize} We present the first non-trivial bounds for supporting these queries. For $\LCEPP$ queries, we present a linear-space solution with $O(\log^{*} n)$ query time. For $\LCEPT$ queries, we present a linear-space solution with $O((\log\log n)^{2})$ query time, and complement this with a lower bound showing that any path-tree LCE structure of size $O(n \polylog(n))$ must necessarily use $\Omega(\log\log n)$ time to answer queries. For $\LCETT$ queries, we present a time-space trade-off, that given any parameter $\tau$, $1 \leq \tau \leq n$, leads to an $O(n\tau)$ space and $O(n/\tau)$ query-time solution. This is complemented with a reduction to the the set intersection problem implying that a fast linear space solution is not likely to exist. - 27 November 2014
- Published by Springer Nature in Algorithmica
- Vol. 73 (3) , 571-588
Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
- 27 November 2014
- Published by Springer Nature in Algorithmica
- Vol. 73 (3) , 571-588
Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
- Open Access
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
In binary jumbled pattern matching we wish to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of size $i$ and has exactly $j$ 1-bits. The problem naturally generalizes to node-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an ${n^2}/{2^{\Omega(\log n/\log \log n)^{1/2}}}$ time solution for both strings and trees. This odd-looking time complexity improves the state of the art $O(n^2/\log^2 n)$ solutions by more than any poly-logarithmic factor. It originates from the recent seminal algorithm of Williams for min-plus matrix multiplication. We obtain the result by giving a black box reduction from trees to strings. This is then combined with a reduction from strings to min-plus matrix multiplications.Open AccessBinary Jumbled Pattern Matching via All-Pairs Shortest Paths
In binary jumbled pattern matching we wish to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of size $i$ and has exactly $j$ 1-bits. The problem naturally generalizes to node-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an ${n^2}/{2^{\Omega(\log n/\log \log n)^{1/2}}}$ time solution for both strings and trees. This odd-looking time complexity improves the state of the art $O(n^2/\log^2 n)$ solutions by more than any poly-logarithmic factor. It originates from the recent seminal algorithm of Williams for min-plus matrix multiplication. We obtain the result by giving a black box reduction from trees to strings. This is then combined with a reduction from strings to min-plus matrix multiplications. - Open Access
Tree Compression with Top Trees
We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as opposed to the classical DAG compression that only exploits rooted subtree repeats) while also supporting fast navigational queries directly on the compressed representation. We show that the new compression scheme achieves close to optimal worst-case compression, can compress exponentially better than DAG compression, is never much worse than DAG compression, and supports navigational queries in logarithmic time.
Open AccessTree Compression with Top Trees
We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as opposed to the classical DAG compression that only exploits rooted subtree repeats) while also supporting fast navigational queries directly on the compressed representation. We show that the new compression scheme achieves close to optimal worst-case compression, can compress exponentially better than DAG compression, is never much worse than DAG compression, and supports navigational queries in logarithmic time.