Ariel Shiftan

I&C Journal 2016 Journal Article

Addendum to ‘Exponential time improvement for min-wise based algorithms’ [Information and Computation 209 (2011) 737–747]

• Guy Feigenblat
• Ely Porat
• Ariel Shiftan

TCS Journal 2016 Journal Article

Set Intersection and Sequence Matching with mismatch counting

• Ariel Shiftan
• Ely Porat

In the classical pattern-matching problem, one is given a text and a pattern both of which are sequences of letters. The requirement is to find all occurrences of the pattern in the text. We studied two modifications of the classical problem, where each letter in the text and pattern is a set (Set Intersection Matching problem) or a sequence (Sequence Matching problem). Two “letters” are found to match if the intersection of the corresponding sets is not empty or if the two sequences have a common element in the same index. We first show that the two problems are similar by establishing a linear time reduction between them. We then show the first known non-trivial and efficient algorithms for these problems, when the maximum set/sequence size d is small. The first is a Monte Carlo randomized algorithm for Set Intersection Matching, that takes Θ ( 4 d n log ⁡ n log ⁡ m ) time, where n and m are the lengths of the text and the pattern, respectively; the failure probability is less than 1 n 2. This algorithm can also be used, with slight modifications, when up to k mismatches is allowed. In addition, it can be used to maintain an approximation of factor 1 ± ϵ of the mismatch count in Θ ( 1 ϵ 2 4 d n log ⁡ n log ⁡ m ) time; the failure probability is bounded by 1 n. The second is a deterministic algorithm for Set Intersection Matching that can be used to count the number of matches at each index of the text in a total running time Θ ( ∑ i = 1 d ( σ i ) n log ⁡ m ) = O ( σ d n log ⁡ m ), where σ is the size of the alphabet. The third algorithm, also deterministic, solves the Sequence Matching problem in Θ ( 4 d n log ⁡ m ) time.

I&C Journal 2011 Journal Article

Exponential time improvement for min-wise based algorithms

• Guy Feigenblat
• Ely Porat
• Ariel Shiftan

In this paper we extend the notion of min-wise independent family of hash functions by defining a k-min-wise independent family of hash functions. Informally, under this definition, all subsets of size k of any fixed set X have an equal chance to have the minimal hash values among all the elements in X, when the probability is over the random choice of hash function from the family. This property measures the randomness of the family, as choosing a truly random function, obviously, satisfies the definition for k =∣X∣. We define and give an efficient time and space construction of approximately k-min-wise independent family of hash functions by extending Indyk’s construction of approximately min-wise independent. The number of words needed to represent each function is O ( k log log ( 1 ϵ ) + log ( 1 ϵ ) ), which is only suboptimal by a factor of O ( log log ( 1 ϵ ) ), where ϵ ∈(0, 1) is the desired error bound. This construction is the first applicable for sampling bottom-k sketches out of the universe. In addition, we introduce a general and novel technique that utilizes our construction, and can be used to improve many min-wise based algorithms. As an example we show how to apply it for similarity estimation over data streams, and reduce exponentially the run time of the current known result [5]. In addition, we also discuss improvements of known algorithms for estimating rarity and entropy of random walk over graphs.

SODA Conference 2011 Conference Paper

Exponential Time Improvement for min-wise Based Algorithms

• Guy Feigenblat
• Ely Porat
• Ariel Shiftan