Publications with Michael Mitzenmacher
- Wear minimization for cuckoo hashing: how not to throw a lot of
eggs into one basket.
D. Eppstein, M. T. Goodrich, M .Mitzenmacher, and P. Pszona.
arXiv:1404.0286.
Proc. 13th International Symposium on Experimental Algorithms (SEA 2014), Copenhagen, Denmark, 2014.
Springer, Lecture Notes in Comp. Sci. 8504, pp. 162–173, 2014.We study cuckoo hashing data structures in a model of flash memory in which each memory cell has a limited number of times it can be changed, so the goal is to prevent hot spots that change many times.
- Models and algorithms for graph watermarking.
D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres.
arXiv:1605.09425.
Proc. 19th Information Security Conference (ISC 2016), Honolulu, Hawaii.
Springer, Lecture Notes in Comp. Sci. 9866 (2016), pp. 283–301.We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.
- 2-3 cuckoo filters for faster triangle listing and set intersection.
D. Eppstein, M. T. Goodrich, M. Mitzenmacher, and M. Torres.
Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), Chicago, 2017, pp. 247–260.
We show that bit-parallel algorithm design techniques, on a machine of word size w, can speed up the time for sparse set intersection by a factor of log w/w. The main data structure underlying our algorithms is the cuckoo filter, a variant of cuckoo hash tables that has operations similar to a Bloom filter but outperforms Bloom filters in several respects.