We might be able to save some bandwidth by using Cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
