LFCS seminar: Mayank Goswami:Distance sensitive Bloom filters without false negatives
What 


When 
Aug 29, 2017 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
Abstract: In the membership problem one is given a set S of elements from some universe U to be preprocessed, in order to answer queries on an element q of the form: is q in S? Exact solutions require roughly O(S
log U
) bits, which can be prohibitive, and so in many applications one solves the approximate version. Here, if q is in S, a data structures always answers yes, and if q is not in S, the data structures answers no with probability at least 1epsilon, where epsilon is called the false positive rate. Bloom Filters provide such a guarantee, use S
log (1/epsilon) bits and for this reason are popular in databases, networking and file storage systems.
However, in many applications (computer vision, machine learning, databases, cryptography, etc.) one instead wants to answer the query: is q "close to" an element of S? This decision query generalizes the membership query. In this talk we will see the first filters that solve this problem using sublinear (not storing the set explicitly) space. We call them DistanceSensitive Bloom Filters, or Similarity Filters.
The talk is based on a paper of the same title at ACMSIAM Symposium on Discrete Algorithms, 2017.
Speaker's Bio: Mayank Goswami is an Assistant Profesor at Queens College in the City University of New York (CUNY). Prior to moving to New York in 2016, he was a researcher at the MaxPlanck Institute for Informatics in Germany, hosted by Prof. Kurt Mehlhorn. He completed his Bachelors in pure mathematics from the Indian Statistical Institute in 2007, and received his doctorate in applied mathematics from Stony Brook University in 2013 under the supervision of Prof. Joseph S. B. Mitchell. His main research areas are algorithms for databases and external memory models, networks, computational geometry and its applications to computer graphics and vision.