Personal tools
You are here: Home LFCS seminar: Mayank Goswami:Distance sensitive Bloom filters without false negatives

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

— filed under: ,

  • LFCS Seminar
  • Upcoming events
When Aug 29, 2017
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal

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 1-epsilon, 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 Distance-Sensitive Bloom Filters, or Similarity Filters.

The talk is based on a paper of the same title at ACM-SIAM 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 Max-Planck 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.

Document Actions