Document Open Access Logo

Succinct Filters for Sets of Unknown Sizes

Authors Mingmou Liu, Yitong Yin, Huacheng Yu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.79.pdf
  • Filesize: 0.53 MB
  • 19 pages

Document Identifiers

Author Details

Mingmou Liu
  • State Key Laboratory for Novel Software Technology, Nanjing University, China
Yitong Yin
  • State Key Laboratory for Novel Software Technology, Nanjing University, China
Huacheng Yu
  • Princeton University, NJ, USA

Funding

  • Liu, Mingmou: Part of the research was done when Mingmou Liu was visiting the Princeton University. Mingmou Liu is supported by National Key R&D Program of China 2018YFB1003202 and NSFC under Grant Nos. 61722207 and 61672275.
  • Yin, Yitong: Yitong Yin is supported by National Key R&D Program of China 2018YFB1003202 and NSFC under Grant Nos. 61722207 and 61672275.

Cite AsGet BibTex

Mingmou Liu, Yitong Yin, and Huacheng Yu. Succinct Filters for Sets of Unknown Sizes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 79:1-79:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.79

Abstract

The membership problem asks to maintain a set S ⊆ [u], supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that computes exact answers is called a dictionary. When a (small) false positive rate ε is allowed, the data structure is called a filter. The space usages of the standard dictionaries or filters usually depend on the upper bound on the size of S, while the actual set can be much smaller. Pagh, Segev and Wieder [Pagh et al., 2013] were the first to study filters with varying space usage based on the current |S|. They showed in order to match the space with the current set size n = |S|, any filter data structure must use (1-o(1))n(log(1/ε)+(1-O(ε))log log n) bits, in contrast to the well-known lower bound of N log(1/ε) bits, where N is an upper bound on |S|. They also presented a data structure with almost optimal space of (1+o(1))n(log(1/ε)+O(log log n)) bits provided that n > u^0.001, with expected amortized constant insertion time and worst-case constant lookup time. In this work, we present a filter data structure with improvements in two aspects: - it has constant worst-case time for all insertions and lookups with high probability; - it uses space (1+o(1))n(log (1/ε)+log log n) bits when n > u^0.001, achieving optimal leading constant for all ε = o(1). We also present a dictionary that uses (1+o(1))nlog(u/n) bits of space, matching the optimal space in terms of the current size, and performs all operations in constant time with high probability.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Bloom filters
  • Data structures
  • Approximate set membership
  • Dictionaries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Paulo Sérgio Almeida, Carlos Baquero, Nuno M Preguiça, and David Hutchison. Scalable bloom filters. Information Processing Letters, 101(6):255-261, 2007. Google Scholar
  2. Yuriy Arbitman, Moni Naor, and Gil Segev. De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In International Colloquium on Automata, Languages, and Programming, pages 107-118. Springer, 2009. Google Scholar
  3. Yuriy Arbitman, Moni Naor, and Gil Segev. Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 787-796. IEEE, 2010. Google Scholar
  4. Michael A Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, and Shikha Singh. Bloom filters, adaptivity, and the dictionary problem. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.01616.
  5. Michael A Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, and Shikha Singh. Bloom filters, adaptivity, and the dictionary problem. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 182-193. IEEE, 2018. Google Scholar
  6. Ioana O Bercea and Guy Even. Fully-dynamic space-efficient dictionaries and filters with constant number of memory accesses. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.05060.
  7. Andrei Broder and Michael Mitzenmacher. Using multiple hash functions to improve ip lookups. In Proceedings IEEE INFOCOM, volume 3, pages 1454-1463. IEEE, 2001. Google Scholar
  8. Larry Carter, Robert Floyd, John Gill, George Markowsky, and Mark Wegman. Exact and approximate membership testers. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 59-65, 1978. Google Scholar
  9. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A distributed storage system for structured data. ACM Trans. Comput. Syst., 26(2), June 2008. Google Scholar
  10. Tobias Christiani, Rasmus Pagh, and Mikkel Thorup. From independence to expansion and back again. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 813-820. ACM, 2015. Google Scholar
  11. Erik D Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pǎtraşcu. De dictionariis dynamicis pauco spatio utentibus. In Latin American Symposium on Theoretical Informatics, pages 349-361. Springer, 2006. Google Scholar
  12. Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert Endre Tarjan. Dynamic perfect hashing: Upper and lower bounds. In 29th Annual Symposium on Foundations of Computer Science, pages 524-531. IEEE, 1988. Google Scholar
  13. Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In International Colloquium on Automata, Languages, and Programming, pages 6-19. Springer, 1990. Google Scholar
  14. O. Erdogan and Pei Cao. Hash-av: fast virus signature scanning by cache-resident filters. In GLOBECOM '05. IEEE Global Telecommunications Conference, 2005., volume 3, pages 6 pp.-, November 2005. URL: https://doi.org/10.1109/GLOCOM.2005.1577953.
  15. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with 0(1) worst case access time. J. ACM, 31(3):538-544, 1984. Google Scholar
  16. Deke Guo, Jie Wu, Honghui Chen, and Xueshan Luo. Theory and network applications of dynamic bloom filters. In Proceedings IEEE INFOCOM, pages 1-12. IEEE, 2006. Google Scholar
  17. Mai Jiang, Chunsheng Zhao, Zaifeng Mo, and Jing Wen. An improved algorithm based on bloom filter and its application in bar code recognition and processing. EURASIP Journal on Image and Video Processing, 2018(1):139, December 2018. URL: https://doi.org/10.1186/s13640-018-0375-6.
  18. Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113-133, 2009. Google Scholar
  19. Adam Kirsch and Michael Mitzenmacher. Using a queue to de-amortize cuckoo hashing in hardware. In Proceedings of the Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing, volume 75, 2007. Google Scholar
  20. Paul C Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In Annual International Cryptology Conference, pages 104-113. Springer, 1996. Google Scholar
  21. Richard J Lipton and Jeffrey F Naughton. Clocked adversaries for hashing. Algorithmica, 9(3):239-252, 1993. Google Scholar
  22. Yi Liu, Xiongzi Ge, David Hung-Chang Du, and Xiaoxia Huang. Par-bf: A parallel partitioned bloom filter for dynamic data sets. The International Journal of High Performance Computing Applications, 30(3):259-275, 2016. URL: https://doi.org/10.1177/1094342015618452.
  23. Shachar Lovett and Ely Porat. A lower bound for dynamic approximate membership data structures. In IEEE 51st Annual Symposium on Foundations of Computer Science, pages 797-804, 2010. Google Scholar
  24. Bruce M. Maggs and Ramesh K. Sitaraman. Algorithmic nuggets in content delivery. SIGCOMM Comput. Commun. Rev., 45(3):52–66, July 2015. URL: https://doi.org/10.1145/2805789.2805800.
  25. Moni Naor and Eylon Yogev. Bloom filters in adversarial environments. ACM Transactions on Algorithms (TALG), 15(3):1-30, 2019. Google Scholar
  26. Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures: the case of aes. In Cryptographers’ track at the RSA conference, pages 1-20. Springer, 2006. Google Scholar
  27. Anna Pagh, Rasmus Pagh, and S Srinivasa Rao. An optimal bloom filter replacement. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 823-829, 2005. Google Scholar
  28. Rasmus Pagh, Gil Segev, and Udi Wieder. How to approximate a set without knowing its size in advance. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 80-89. IEEE, 2013. Google Scholar
  29. Rajeev Raman and Satti Srinivasa Rao. Succinct dynamic dictionaries and trees. In International Colloquium on Automata, Languages, and Programming, pages 357-368. Springer, 2003. Google Scholar
  30. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. Google Scholar
  31. Mikkel Thorup. Simple tabulation, fast expanders, double tabulation, and high independence. In 54th Annual Symposium on Foundations of Computer Science, pages 90-99. IEEE, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact