Author name cluster

Estrella Eisenberg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

I&C Journal 2015 Journal Article

Approximate periodicity

Amihood Amir
Estrella Eisenberg
A. Levy

Finding an approximate period in a given string S of length n is defined as follows. Let S ′ be a periodic string closest to S under some distance metric, find the smallest period of S ′. This period is called an approximate period of S under the given metric. Let the distance between the input string S and a closest periodic string under the Hamming distance S ′ be k. We develop algorithms that construct an approximate period of S under the Hamming distance in time O ( n k log ⁡ log ⁡ n ) and under the swap distance in time O ( n 2 ). Finally, we show an O ( n log ⁡ n ) algorithm for finite alphabets, and an O ( n log 3 ⁡ n ) algorithm for infinite alphabets, that approximate the minimum number of mismatches between the input string and a closest periodic string under the Hamming distance.

Details DOI

TCS Journal 2014 Journal Article

Closest periodic vectors in L p spaces

Amihood Amir
Estrella Eisenberg
Avivit Levy
Noa Lewenstein

The problem of finding the period of a vector V is central to many applications. Let V ′ be a periodic vector closest to V under some metric. We seek this V ′, or more precisely we seek the smallest period that generates V ′. In this paper we consider the problem of finding the closest periodic vector in L p spaces. The measures of “closeness” that we consider are the metrics in the different L p spaces. Specifically, we consider the L 1, L 2 and L ∞ metrics. In particular, for a given n-dimensional vector V, we develop O ( n 2 ) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic n-dimensional vector V ′. We call that vector the closest periodic vector of V under the appropriate metric. We also show (three) O ˜ ( n ) time constant approximation algorithms for the period of the approximate closest periodic vector.

Details DOI

TCS Journal 2014 Journal Article

Detecting approximate periodic patterns

Amihood Amir
Alberto Apostolico
Estrella Eisenberg
Gad M. Landau
Avivit Levy
Noa Lewenstein

Given ϵ ∈ [ 0, 1 ), the ϵ-Relative Error Periodic Pattern Problem (REPP) is the following: INPUT: An n-long sequence S of numbers s i ∈ N in increasing order. OUTPUT: The longest ϵ-relative error periodic pattern, i. e. , the longest subsequence s i 1, s i 2, …, s i k of S, for which there exists a number p such that the absolute difference between any two consecutive numbers in the subsequence is at least p and at most p ( 1 + ϵ ). The best known algorithm for this problem has O ( n 3 ) time complexity. This bound is too high for large inputs in practice. In this paper we give a new algorithm for finding the longest ϵ-relative error periodic pattern (the REPP problem). Our method is based on a transformation of the input sequence into a different representation: the ϵ-active maximal intervals list L, defined in this paper. We show that the transformation of S to the list L can be done efficiently (quadratic in n and linear in the size of L) and prove that our algorithm is linear in the size of L. This enables us to prove that our algorithm works in sub-cubic time on inputs for which the best known algorithm works in O ( n 3 ) time. Moreover, though it may happen that our algorithm would still be cubic, it is never worse than the known O ( n 3 ) -algorithm and in many situations its complexity is O ( n 2 ) time.

Details DOI

TCS Journal 2011 Journal Article

Approximate string matching with stuck address bits

Amihood Amir
Estrella Eisenberg
Orgad Keller
Avivit Levy
Ely Porat

A string S ∈ Σ m can be viewed as a set of pairs { ( s i, i ) ∣ s i ∈ S, i ∈ { 0, …, m − 1 } }. We follow the recent work on pattern matching with address errors and consider approximate pattern matching problems arising from the setting where errors are introduced to the location component ( i ), rather than the more traditional setting, where errors are introduced to the content itself ( s i ). Specifically, we continue the work on string matching in the presence of address bit errors. In this paper, we consider the case where bits of i may be stuck, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution.

Details DOI