290 research outputs found
Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing
No full textThis 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, multidimensional points, multiple-precision numbers, multikey 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 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 construction can be done in worst case time per input symbol (as opposed to amortized time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves worst case time per input symbol. Searching for a pattern of length in the resulting suffix tree takes time, where is the number of occurrences of the pattern. The paper also describes more applications and shows how to obtain alternative methods for dealing with suffix sorting, dynamic lowest common ancestors, and order maintenance. The technical features of the proposed technique for a given data structure are the following ones. The new data structure is obtained from by augmenting the latter with an oracle for strings, extending the functionalities of the Dietz--Sleator list for order maintenance [P. F. Dietz and D. D. Sleator, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 365--372; A. Tsakalidis, Acta Inform., 21 (1984), pp. 101--112]. The space complexity of is memory cells for storing keys, where denotes the space complexity of . Then, each operation involving keys taken from requires time, where denotes the time complexity of the corresponding operation originally supported in . Each operation involving a key not stored in takes time, where denotes the length of . For the special case where the oracle handles suffixes of a string, the achieved insertion time is
Front Matter, Table of Contents, Preface
No full textFront Matter, Table of Contents, Preface, List of Author
Parameterized matching with mismatches
No full textThe problem of approximate parameterized string searching consists of ¯nding, for a
given text t = t1t2:::tn and pattern p = p1p2:::pm over respective alphabets §t and §p,
the injection ¼i from §p to §t maximizing the number of matches between ¼i(p) and
titi+1:::ti+m¡1 (i = 1; 2; :::n¡m+1). We examine the special case where both strings are
run-length encoded, and further restrict to the case where one of the alphabets is binary.
For this case, we give a construction working in time O(n + (rp £ rt) ®(rt) log(rt)),
where rp and rt denote the number of runs in the corresponding encodings for y and x,
respectively, and ® is the inverse of the Ackermann's function
Space-Efficient String Indexing for Wildcard Pattern Matching
No full textIn 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^e(n)) bits for any e>0 and reports all occ occurrences of a wildcard string in O(m+s^g.M(n)+occ) time, where M(n)=o(log(log(log(n)))), s 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+s^g+occ).log^e(n)) query time and an O(n{log(log(n))}^2)-bit index with O((m+s^g+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
Improved Space-Time Tradeoffs for kSUM
No full textIn the kSUM problem we are given an array of numbers a_1,a_2,...,a_n and we are required to determine if there are k different elements in this array such that their sum is 0. This problem is a parameterized version of the well-studied SUBSET-SUM problem, and a special case is the 3SUM problem that is extensively used for proving conditional hardness. Several works investigated the interplay between time and space in the context of SUBSET-SUM. Recently, improved time-space tradeoffs were proven for kSUM using both randomized and deterministic algorithms.
In this paper we obtain an improvement over the best known results for the time-space tradeoff for kSUM. A major ingredient in achieving these results is a general self-reduction from kSUM to mSUM where m1. (iv) An algorithm for 6SUM running in O(n^4) time using just O(n^{2/3}) space. (v) A solution to 3SUM on random input using O(n^2) time and O(n^{1/3}) space, under the assumption of a random read-only access to random bits
Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms
No full textRahmann S. Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms. In: Lewenstein M, Valiente G, eds. Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings. Lecture Notes in Computer Science. Vol 4009. Berlin: Springer; 2006: 153-164.We investigate combinatorial enumeration problems related to subsequences of strings; in contrast to substrings, subsequences need not be contiguous. For a finite alphabet Sigma, the following three problems are solved. (1) Number of distinct subsequences: Given a sequence s is an element of Sigma(n) and a nonnegative integer k = 1 and rho >= 1, how many distinct sequences in Sigma(k) contain no single nucleotide repeat longer than rho and can be written as s(1)(r1)... s(n)(rn) with 0 = 1, determine the number of sequences in Sigma(n) whose longest strictly increasing subsequence has length k, where 0 <= k <= K. This has applications to significance computations for chaining algorithms
Orthogonal Vectors Indexing
No full textIn the recent years, intensive research work has been dedicated to prove conditional lower bounds in order to reveal the inner structure of the class P. These conditional lower bounds are based on many popular conjectures on well-studied problems. One of the most heavily used conjectures is the celebrated Strong Exponential Time Hypothesis (SETH). It turns out that conditional hardness proved based on SETH goes, in many cases, through an intermediate problem - the Orthogonal Vectors (OV) problem.
Almost all research work regarding conditional lower bound was concentrated on time complexity. Very little attention was directed toward space complexity. In a recent work, Goldstein et al.[WADS '17] set the stage for proving conditional lower bounds regarding space and its interplay with time. In this spirit, it is tempting to investigate the space complexity of a data structure variant of OV which is called OV indexing. In this problem n boolean vectors of size clogn are given for preprocessing. As a query, a vector v is given and we are required to verify if there is an input vector that is orthogonal to it or not.
This OV indexing problem is interesting in its own, but it also likely to have strong implications on problems known to be conditionally hard, in terms of time complexity, based on OV. Having this in mind, we study OV indexing in this paper from many aspects. We give some space-efficient algorithms for the problem, show a tradeoff between space and query time, describe how to solve its reporting variant, shed light on an interesting connection between this problem and the well-studied SetDisjointness problem and demonstrate how it can be solved more efficiently on random input
String Factorization via Prefix Free Families
No full textA factorization of a string S is a partition of w into substrings u_1,… ,u_k such that S = u_1 u_2 ⋯ u_k. Such a partition is called equality-free if no two factors are equal: u_i ≠ u_j, ∀ i,j with i ≠ j. The maximum equality-free factorization problem is to find for a given string S, the largest integer k for which S admits an equality-free factorization with k factors.
Equality-free factorizations have lately received attention because of their applications in DNA self-assembly. The best approximation algorithm known for the problem is the natural greedy algorithm, that chooses iteratively from left to right the shortest factor that does not appear before. This algorithm has a √n approximation ratio (SOFSEM 2020) and it is an open problem whether there is a better solution.
Our main result is to show that the natural greedy algorithm is a Θ(n^{1/4}) approximation algorithm for the maximum equality-free factorization problem. Thus, we disprove one of the conjectures of Mincu and Popa (SOFSEM 2020) according to which the greedy algorithm is a Θ(√n) approximation.
The most challenging part of the proof is to show that the greedy algorithm is an O(n^{1/4}) approximation. We obtain this algorithm via prefix free factor families, i.e. a set of non-overlapping factors of the string which are pairwise non-prefixes of each other. In the paper we show the relation between prefix free factor families and the maximum equality-free factorization. Moreover, as a byproduct we present another approximation algorithm that achieves an approximation ratio of O(n^{1/4}) that we believe is of independent interest and may lead to improved algorithms. We then show that the natural greedy algorithm has an approximation ratio that is Ω(n^{1/4}) via a clever analysis which shows that the greedy algorithm is Θ(n^{1/4}) for the maximum equality-free factorization problem
Wilson Fermions and Axion Electrodynamics in Optical Lattices
No full textWe show that ultracold Fermi gases in optical superlattices can be used as quantum simulators of relativistic lattice fermions in 3+1 dimensions. By exploiting laser-assisted tunneling, we find an analogue of the so-called naive Dirac fermions, and thus provide a realization of the fermion doubling problem. Moreover, we show how to implement Wilson fermions, and discuss how their mass can be inverted by tuning the laser intensities. In this regime, our atomic gas corresponds to a phase of matter where Maxwell electrodynamics is replaced by axion electrodynamics: a 3D topological insulator. © 2010 The American Physical Society.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
No full textIn Gapped String Indexing, the goal is to compactly represent a string S of length n such that for any query consisting of two strings P₁ and P₂, called patterns, and an integer interval [α, β], called gap range, we can quickly find occurrences of P₁ and P₂ in S with distance in [α, β]. Gapped String Indexing is a central problem in computational biology and text mining and has thus received significant research interest, including parameterized and heuristic approaches. Despite this interest, the best-known time-space trade-offs for Gapped String Indexing are the straightforward (n) space and (n+ occ) query time or Ω(n²) space and Õ(|P₁| + |P₂| + occ) query time. We break through this barrier obtaining the first interesting trade-offs with polynomially subquadratic space and polynomially sublinear query time. In particular, we show that, for every 0 ≤ δ ≤ 1, there is a data structure for Gapped String Indexing with either Õ(n2-δ/3) or Õ(n3-2δ) space and Õ(|P₁| + |P₂| + nδ⋅ (occ+1)) query time, where occ is the number of reported occurrences. As a new fundamental tool towards obtaining our main result, we introduce the Shifted Set Intersection problem: preprocess a collection of sets S₁, …, Sk of integers such that for any query consisting of three integers i,j,s, we can quickly output YES if and only if there exist a ∈ Si and b ∈ Sj with a+s = b. We start by showing that the Shifted Set Intersection problem is equivalent to the indexing variant of 3SUM (3SUM Indexing) [Golovnev et al., STOC 2020]. We then give a data structure for Shifted Set Intersection with gaps, which entails a solution to the Gapped String Indexing problem. Furthermore, we enhance our data structure for deciding Shifted Set Intersection, so that we can support the reporting variant of the problem, i.e., outputting all certificates in the affirmative case. Via the obtained equivalence to 3SUM Indexing, we thus give new improved data structures for the reporting variant of 3SUM Indexing, and we show how this improves upon the state-of-the-art solution for Jumbled Indexing [Chan and Lewenstein, STOC 2015] for any alphabet of constant size σ > 5
- …
