28 Result(s)

Chapter and Conference Paper

On Suffix Tree Detection

A suffix tree is a fundamental data structure for string processing and information retrieval, however, its structure is still not well understood. The suffix trees reverse engineering problem, which its research...

Amihood Amir, Eitan Kondratovsky… in String Processing and Information Retrieval (2023)

Chapter and Conference Paper

Reconstructing Parameterized Strings from Parameterized Suffix and LCP Arrays

Reconstructing input from a data structure entails determining whether an instance of the data structure is in fact valid or not, and if valid, discovering the underlying data that it represents. In this paper...

Amihood Amir, Concettina Guerra… in String Processing and Information Retrieval (2022)

Chapter and Conference Paper

Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction

We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biolog...

Ramtin Afshar, Amihood Amir… in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Approximating the Anticover of a String

The k-anticover of a string S is a set of distinct k-length substrings such that every index in S is contained in one of these substrings. The existence of an anticover indicates a lack of structure in S. It was ...

Amihood Amir, Itai Boneh, Eitan Kondratovsky in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Multidimensional Period Recovery

Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...

Amihood Amir, Ayelet Butman… in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Searching for a Modified Pattern in a Changing Text

Much attention has been devoted recently to the dynamic model of pattern matching. In this model the input is updated or changed locally. One is interested in obtaining the appropriate search result in time th...

Amihood Amir, Eitan Kondratovsky in String Processing and Information Retrieval (2018)

Chapter and Conference Paper

Longest Common Factor After One Edit Operation

It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that...

Amihood Amir, Panagiotis Charalampopoulos… in String Processing and Information Retrieval (2017)

Reference Work Entry In depth

Two-Dimensional Scaled Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Similarity Between Compressed Strings

** Wook Kim, Amihood Amir, Gad M. Landau, Kunsoo Park in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Multidimensional Compressed Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2016)

Chapter

Hypertext Searching - A Survey

The idea of hypertext has been successfully used in Jewish literature. Its importance has been steadily growing over the last two decades. Internet and other information systems use hypertext format, with data...

Amihood Amir, Moshe Lewenstein… in Language, Culture, Computation. Computing … (2014)

Chapter and Conference Paper

Detecting Approximate Periodic Patterns

Given ε ∈ [0, 1), the ε-Relative Error Periodic Pattern Problem (REPP) is the following:

Amihood Amir, Alberto Apostolico, Estrella Eisenberg… in Design and Analysis of Algorithms (2012)

Chapter and Conference Paper

Blocked Pattern Matching Problem and Its Applications in Proteomics

Matching a mass spectrum against a text (a key computational task in proteomics) is slow since the existing text indexing algorithms (with search time independent of the text size) are not applicable in the domai...

Julio Ng, Amihood Amir, Pavel A. Pevzner in Research in Computational Molecular Biology (2011)

Chapter

String Rearrangement Metrics: A Survey

A basic assumption in traditional pattern matching is that the order of the elements in the given input strings is correct, while the description of the content, i.e. the description of the elements, may be er...

Amihood Amir, Avivit Levy in Algorithms and Applications (2010)

Chapter and Conference Paper

Cycle Detection and Correction

Assume that a natural cyclic phenomenon has been measured, but the data is corrupted by errors. The type of corruption is application-dependent and may be caused by measurements errors, or natural features of ...

Amihood Amir, Estrella Eisenberg, Avivit Levy… in Automata, Languages and Programming (2010)

Reference Work Entry In depth

Multidimensional Compressed Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2008)

Reference Work Entry In depth

Two-Dimensional Scaled Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2008)

Reference Work Entry In depth

Similarity between Compressed Strings

** Wook Kim, Amihood Amir, Gad M. Landau, Kunsoo Park in Encyclopedia of Algorithms (2008)

Chapter and Conference Paper

Efficient Computations of ℓ₁ and ℓ_∞ Rearrangement Distances

Recently, a new pattern matching paradigm was proposed, pattern matching with address errors. In this paradigm approximate string matching problems are studied, where the content is unaltered and only the locatio...

Amihood Amir, Yonatan Aumann, Piotr Indyk… in String Processing and Information Retrieval (2007)