Guy Feigenblat

AAAI Conference 2021 System Paper

KAAPA: Knowledge Aware Answers from PDF Analysis

• Nicolas Fauceglia
• Mustafa Canim
• Alfio Gliozzo
• Jennifer J Liang
• Nancy Xin Ru Wang
• Douglas Burdick
• Nandana Mihindukulasooriya
• Vittorio Castelli

We present KaaPa (Knowledge Aware Answers from Pdf Analysis), an integrated solution for machine reading comprehension over both text and tables extracted from PDFs. KaaPa enables interactive question refinement using facets generated from an automatically induced Knowledge Graph. In addition it provides a concise summary of the supporting evidence for the provided answers by aggregating information across multiple sources. KaaPa can be applied consistently to any collection of documents in English with zero domain adaptation effort. We showcase the use of KaaPa for QA on scientific literature using the COVID-19 Open Research Dataset.

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

Corrigendum to “The frequent items problem, under polynomial decay, in the streaming model” [Theoret. Comput. Sci. 411(34–36) (2010) 3048–3054]

• Guy Feigenblat
• Ofra Itzhaki
• Ely Porat

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

TCS Journal 2010 Journal Article

The frequent items problem, under polynomial decay, in the streaming model

• Guy Feigenblat
• Ofra Itzhaki
• Ely Porat

We consider the problem of estimating the frequency count of data stream elements under polynomial decay functions. In these settings every element in the stream is assigned with a time-decreasing weight, using a non-increasing polynomial function. Decay functions are used in applications where older data is less significant, less interesting or even less reliable than recent data. Consider a data stream of N elements drawn from a universe U. We propose three poly-logarithmic algorithms for the problem. The first one, deterministic, uses O ( 1 ϵ 2 log N ( log log N + log U ) ) bits, where ϵ ∈ ( 0, 1 ) is the approximation parameter. The second one, probabilistic, uses O ( 1 ϵ 2 log N δ log 1 ϵ ) bits or O ( 1 ϵ 2 log N δ log N ) bits, depending on the decay function parameter, where δ ∈ ( 0, 1 ) is the probability of failure. The third one, deterministic in the stochastic model, uses O ( 1 ϵ log U ) bits or O ( 1 ϵ 2 log N ) bits, also depending on the decay parameter as will be described in this paper. This variant of the problem is important and has many applications. To our knowledge, it has never been studied before.