• Authors:

• Bin Fan

  Carnegie Mellon University, Pittsburgh, PA, USA

  ,

• Dave G. Andersen

  Carnegie Mellon University, Pittsburgh, PA, USA

  ,

• Michael Kaminsky

  Intel Corp., Pittsburgh, PA, USA

  ,

• Michael D. Mitzenmacher

  Harvard University, Cambridge, PA, USA

1. CityHash. https://code.google.com/p/cityhash/.Google Scholar
2. M. A. Bender, M. Farach-Colton, R. Johnson, R. Kraner, B. C. Kuszmaul, D. Medjedovic, P. Montes, P. Shetty, R. P. Spillane, and E. Zadok. Don’t thrash: How to cache your hash on flash. PVLDB, 5(11):1627–1637, 2012. Google ScholarDigital Library
3. B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970. Google ScholarDigital Library
4. F. Bonomi, M. Mitzenmacher, and R. Panigrahy. Beyond Bloom filters: From approximate membership checks to approximate state machines. In Proc. ACM SIGCOMM, Pisa, Italy, Aug. 2006. Google ScholarDigital Library
5. F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. An improved construction for counting bloom filters. In 14th Annual European Symposium on Algorithms, LNCS 4168, pages 684–695, 2006. Google ScholarDigital Library
6. A. Broder, M. Mitzenmacher, and A. Broder. Network Applications of Bloom Filters: A Survey. In Internet Mathematics, volume 1, pages 636–646, 2002.Google Scholar
7. B. Chazelle, J. Kilian, R. Rubinfeld, A. Tal, and O. Boy. The Bloomier filter: An efficient data structure for static support lookup tables. In Proceedings of SODA, pages 30–39, 2004. Google ScholarDigital Library
8. J. G. Cleary. Compact Hash Tables Using Bidirectional Linear Probing. IEEE Transactions on Computer, C-33(9), Sept. 1984. Google ScholarDigital Library
9. S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor. Longest prefix matching using Bloom filters. In Proc. ACM SIGCOMM, Karlsruhe, Germany, Aug. 2003. Google ScholarDigital Library
10. M. Dietzfelbinger and C. Weidling. Balanced allocation and dictionaries with tightly packed constant size bins. Theoretical Computer Science, 380(1):47–68, 2007. Google ScholarDigital Library
11. B. Fan, D. G. Andersen, and M. Kaminsky. MemC3: Compact and concurrent memcache with dumber caching and smarter hashing. In Proc. 10th USENIX NSDI, Lombard, IL, Apr. 2013. Google ScholarDigital Library
12. L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: A scalable wide-area Web cache sharing protocol. In Proc. ACM SIGCOMM, Vancouver, BC, Canada, Sept. 1998. Google ScholarDigital Library
13. N. Fountoulakis, M. Khosla, and K. Panagiotou. The multipleorientability thresholds for random hypergraphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1222–1236. SIAM, 2011. Google ScholarDigital Library
14. N. Hua, H. C. Zhao, B. Lin, and J. J. Xu. Rank-Indexed Hashing: A Compact Construction of Bloom Filters and Variants. In Proc. of IEEE Int’l Conf. on Network Protocols (ICNP) 2008, Orlando, Florida, USA, Oct. 2008. Google ScholarDigital Library
15. P. Jokela, A. Zahemszky, C. Esteve Rothenberg, S. Arianfar, and P. Nikander. Lipsin: Line speed publish/subscribe internetworking. In Proc. ACM SIGCOMM, Barcelona, Spain, Aug. 2009. Google ScholarDigital Library
16. A. Kirsch and M. Mitzenmacher. Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms, 33(2):187–218, 2008. Google ScholarDigital Library
17. H. Lim, B. Fan, D. G. Andersen, and M. Kaminsky. SILT: A memory-efficient, high-performance key-value store. In Proc. 23rd ACM Symposium on Operating Systems Principles (SOSP), Cascais, Portugal, Oct. 2011. Google ScholarDigital Library
18. M. Mitzenmacher, A. W. Richa, and R. Sitaraman. The power of two random choices: A survey of techniques and results. In Handbook of Randomized Computing, pages 255–312. Kluwer, 2000.Google Scholar
19. M. Mitzenmacher and B. Vocking. The asymptotics of selecting the shortest of two, improved. In Proc. the Annual Allerton Conference on Communication Control and Computing, volume 37, pages 326–327, 1999.Google Scholar
20. A. Pagh, R. Pagh, and S. S. Rao. An optimal bloom filter replacement. In Proc. ASM-SIAM Symposium on Discrete Algorithms, SODA, 2005. Google ScholarDigital Library
21. R. Pagh and F. Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122–144, May 2004. Google ScholarDigital Library
22. F. Putze, P. Sanders, and S. Johannes. Cache-, hash- and space efficient bloom filters. In Experimental Algorithms, pages 108–121. Springer Berlin / Heidelberg, 2007. Google ScholarDigital Library
23. D. Sanchez, L. Yen, M. D. Hill, and K. Sankaralingam. Implementing signatures for transactional memory. In Proc. the 40th Annual IEEE/ACM International Symposium on Microarchitecture, pages 123–133, Washington, DC, USA, 2007. Google ScholarDigital Library
24. H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood. Fast hash table lookup using extended bloom filter: An aid to network processing. In Proc. ACM SIGCOMM, pages 181–192, Philadelphia, PA, Aug. 2005. Google ScholarDigital Library
25. M. Yu, A. Fabrikant, and J. Rexford. BUFFALO: Bloom filter forwarding architecture for large organizations. In Proc. CoNEXT, Dec. 2009. Google ScholarDigital Library
26. D. Zhou, B. Fan, H. Lim, D. G. Andersen, and M. Kaminsky. Scalable, High Performance Ethernet Forwarding with CuckooSwitch. In Proc. 9th International Conference on emerging Networking EXperiments and Technologies (CoNEXT), Dec. 2013. Google ScholarDigital Library

Index Terms

1. Cuckoo Filter: Practically Better Than Bloom