CS 269S, Winter 2014: Theory Seminar
Bren Hall, Room 1423, 1pm
March 7, 2014:

Set-Difference Range Queries

Joe Simons

We introduce the problem of performing set-difference range queries, where answers to queries are set-theoretic symmetric differences between sets of items in two geometric ranges. We describe a general framework for answering such queries based on a novel use of data streaming sketches we call signed symmetric-difference sketches. We show that such sketches can be realized using invertible Bloom filters (IBFs), which can be composed, differenced, and searched so as to solve set-difference range queries in a wide variety of scenarios.