3 papers
cs.DS2010
On the hardness of distance oracle for sparse graph
Hagai Cohen, Ely Porat
In this paper we show that set-intersection is harder than distance oracle on sparse graphs. Given a collection of total size n which consists of m sets drawn from universe U, the…
cs.DS2009
Fast Set Intersection and Two Patterns Matching
Hagai Cohen, Ely Porat
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 se…
cs.DS2009
Range Non-Overlapping Indexing
Hagai Cohen, Ely Porat
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-overlappin…