CGGC Seminar: 2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection

Speaker:
Michael T. Goodrich (University of California, Irvine)
Date:
Monday, 23.10.2017, 14:30
Place:
Room 337 Taub Bld.

We introduce new dynamic set intersection data structures, which we call 2-3 cuckoo filters and hash tables. These structures differ from the standard cuckoo hash tables and cuckoo filters in that they choose two out of three locations to store each item, instead of one out of two, ensuring that any item in an intersection of two structures will have at least one common location in both structures. We demonstrate the utility of these structures by using them in improved algorithms for listing triangles and answering set intersection queries.

Bio:
Prof. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. He is a Chancellor's Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. He was a professor in the Department of Computer Science at Johns Hopkins University from 1987-2001. Dr. Goodrich's research is directed at the design of high performance algorithms and data structures with applications to information assurance and security, the Internet, machine learning, and geometric computing. He is an ACM Distinguished Scientist, a Fellow of the American Association for the Advancement of Science (AAAS), a Fulbright Scholar, a Fellow of the IEEE, and a Fellow of the ACM.

Back to the index of events