Fast Set Intersection and Two Patterns Matching (2009)
In this paper we present a new problem, the fast set intersection problem, which is to preprocess a collection of sets in order to efficiently report the intersection of any two sets in the...
Range Non-Overlapping Indexing (2009)
We study the non-overlapping indexing problem: Given a text T, preprocess it so that you can answer queries of the form: given a pattern P, report the maximal set of non-overlapping occurrences of P...
Efficient One Dimensional Real Scaled Matching (2009)
Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur
Real Scaled Matching is the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Real scaled matching is an...
Pattern matching with don't cares and few errors (2009)
Clifford, Raphael, Efremo, Klim, Porat, Ely, Rotschild, Amir
We present solutions for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols and a bound k, our algorithms find...
Explicit Non-Adaptive Combinatorial Group Testing Schemes (2009)
Group testing is a long studied problem in combinatorics: A small set of r ill people should be identified out of the whole (n people) by using only queries (tests) of the form "Does set X contain an...
Approximate Subset Matching with Don't Cares (2008)
Amihood Amir, Moshe Lewenstein, Ely Porat
The Subset Matching problem was recently introduced by Cole and Hariharan. The input of the problem is a text array of n sets totaling s elements and a pattern array of m sets totaling s0 elements....
Improved algorithms for Polynomial-Time Decay and Time-Decay with additive error (2008)
Abstract. We consider the problem of maintaining polynomial and exponential decay aggregates of a data stream, where the weight of values seen from the stream diminishes as time elapses. These types...
Efficient One Dimensional Real Scaled Matching (2008)
Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur
Real Scaled Matching is the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Real scaled matching is an...
Approximate Matching in the L ∞ Metric (2008)
Abstract. Let a text T = t0,..., tn−1 and a pattern P = p0,..., pm−1, strings of natural numbers, be given. In the Approximate Matching in the L ∞ metric problem the output is, for every text...
An Optimal Bloom Filter Replacement Based on Matrix Solving (2008)
We suggest a method for holding a dictionary data structure, which maps keys to values, in the spirit of Bloom Filters. The space requirements of the dictionary we suggest are much smaller than those...
Bar-Ilan University Bar-Ilan University Bar-Ilan University Bar-Ilan University (2008)
Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat
We present problems in three different application areas: identifying similar code where global register reallocation and spill code minimization were done (programming languages); protein threading...
Approximating General Metric Distances Between a Pattern and a Text (2008)
Let $T=t_0 ... t_{n-1}$ be a text and $P = p_0 ... p_{m-1}$ a pattern taken from some finite alphabet set $\Sigma$, and let $\dist$ be a metric on $\Sigma$. We consider the problem of calculating the...
Finding the position of the k-mismatch and approximate (2008)
Haim Kaplan, Ely Porat, Nira Shafrir
tandem repeats.
Approximate Matching in Weighted Sequences Amihood Amir \Lambda (2008)
Costas Iliopoulos, Oren Kapah, Ely Porat
Abstract Weighted sequences have been recently introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is a...
Improved Deterministic Length Reduction (2008)
Amir, Amihood, Efremenko, Klim, Kapah, Oren, Porat, Ely, Rothschild, Amir
This paper presents a new technique for deterministic length reduction. This technique improves the running time of the algorithm presented in \cite{LR07} for performing fast convolution in sparse...
Approximating General Metric Distances Between a Pattern and a Text (2008)
Let T = t0... tn−1 be a text and P = p0... pm−1 a pattern taken from some finite alphabet set Σ, and let d be a metric on Σ. We consider the problem of calculating the sum of distances between...
Explicit Non-Adaptive Combinatorial Group Testing Schemes (2007)
Group testing is a long studied problem in combinatorics: A small set of $r$ ill people should be identified out of the whole ($n$ people) by using only queries (tests) of the form "Does set X...
z Bar-Ilan University Bar-Ilan University Bar-Ilan University (2007)
Amihood Amir, Moshe Lewenstein, Ely Porat
Let a text string T of n symbols and a pattern string P of m symbols from alphabet \Sigma be given. A swapped version P 0 of P is a length m string derived from P by a series of local swaps, (i.e. p 0
Deterministic length reduction: Fast convolution in sparse data and applications (2007)
Amihood Amir, Oren Kapah, Ely Porat
In this paper a deterministic algorithm for the length reduction problem is presented. This algorithm enables a new tool for performing fast convolution in sparse data. While the regular fast...
Improved sketching of hamming distance with error (2007)
We address the problem of sketching the hamming distance of data streams. We present a new notion of sketching technique, Fixable sketches and we show that using such sketch not only we reduce the...
Efficient pebbling for list traversal synopses (2003)
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using $O(\log n)$ memory for a list of size $n$, the...
Efficient Pebbling for List Traversal Synopses (2002)
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lg n) memory for a list of size n, the...
Efficient Pebbling for List Traversal Synopses (2002)
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(log n) memory for a list of size n, the...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Approximate subset matching with don’t cares (2001)
Amihood Amir, Moshe Lewenstein, Ely Porat
The need for the general task of "pattern matching" is ubiquitous. However, the combinatorial model of the problem varies with the different application domain.
Faster algorithms for string matching with k mismatches (2000)
Amihood Amir, Moshe Lewenstein, Ely Porat
The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length m and every length m substring of the text T. Currently, the fastest algorithms...
Faster algorithms for string matching with k mismatches (2000)
Amihood Amir, Moshe Lewenstein, Ely Porat
The string matching with mismatches problem is that of finding the number of mismatches between pattern P of length m and every length m substring of the text T. Currently, the best algorithms for...
Faster Algorithms for String Matching with k Mismatches (2000)
Amihood Amir, Moshe Lewenstein, Ely Porat
The string matching with mismatches problem is that of finding the number of mismatches between pattern P of length m and every length m substring of the text T . Currently, the best algorithms for...